一次同余方程的解法及在中学数学竞赛中的应用初探

1、 (2014)届本科生学年论文题 目一次同余方程的解法及在中学数学竞赛中的应用初探 专 业 数学与应用数学 院 系 数学与计算机科学学院 学 号 姓 名 彭莎 任莎莎 胡益梅 指 导 教 师 唐再良 教授 目录1. 同余的基本理论知识 11.1同余的定义. 11.2同余的定理. 12.一次同余方程的几种解法2 2.1验根法.2 2.2利用二元一次不定方程 2 2.3利用辗转相除降模33.同余理论在数学竞赛中的应用.4 3.1分类法.4 3.2奇偶分析法.4 3.3构造法.53.4枚举法.73.5反证法.8参考文献.10一次同余方程的解法及在中学数学竞赛中的应用初探【摘要】：介绍一次同余方程的几

2、种解法，并了解一次同余方程的解法在中学数学竞赛中的应用。【关键词】：一次同余方程 解法 数学竞赛中的应用1.同余的基本理论知识1.1同余的定义定义1：设为整数，是一个正整数且（mod），则称为模的一次同余方程。 定义2：若是使成立的一个整数，则（mod）称为一次同余方程的一个解。 1.2同余的定理定理：一次同余方程，（mod）有解的充要条件,且有解时解数为。 一次同余方程的理论各初等数论教材都作了详细的论述（见1）、2、3），但对它的具体解法介绍的较少。笔者在初等数论教学实践中，针对该方程总结了几种解法，并通过各种解法优劣的比较，探讨了在不同情况所应采用的不同方法，这对学生学习初等数论，特别是

3、解一次同余方程具有一定的指导作用。2.一次同余方程的几种解法2.1：验根法由定义2可以看出，求一次同余方程，有几个解，有哪些解，只需取模m 的一个完全剩余系（如0,1,2，m-1）中的每一个数，将其代入同余方程中逐一验证，即可求出其全部解。例：解同余方程解：取模8的最小非负数完全剩余系0,1,2,7,分别代入同余方程中知 满足同余方程。故原同余方程的解为： 。 分析：验根法需对模m完全剩余系中的数逐一验证，因而当模m比较小的时适用于此法。 2.2：利用二元一次不定方程满足xb（modm）的x和满足二元一次不定方程x-my=b方程x-my=b的x相同，因而解xb（modm）可利用二元一次不定方程

4、x-my=b来求。例：解同余方程12x30（mod45）. 解：先解不定方程12x-45y=30，即4x-15y=10。用观察法或辗转相除法可得其一组解为 x0=40,y0=10.所以不定方程12x-45y=30的所有解为 y=10+tx=40+15t t=0,1,2, 满足12x30（mod45）的所有整数位x=40+15t (t=0,1,2) 故原同余方程的解为：x10,25,40(mod45).2.3：利用辗转相除法降模例：解同余方程.解：.这表明最后一个同余方程有3个解逐次反向推导得出关于对模12有3个解： 关于对模45有3个解： 即原同余方程解：分析：这种方法适用于所有一次同余方程，

5、且如果方程无解，则在某一步可直接看出，不用求a与m 的最大公约数。但要注意利用同余式性质化简用余方程时，若改变同余方程的模，则要注意方程的解数。3同余理论在数学竞赛中应用数学奥林匹克竞赛中的初等数论问题，着重考察富于创造性、灵活性的方法技巧：分类法、奇偶分析法、构造法、枚举法、反证法等下面我们通过一些典型的例题来探讨用同余理论解答数学奥林匹克竞赛的题目3.1分类法分类法是将题中符合条件的情况合理分类讨论，分别得出结果，再将结果汇总得到最终结论的方法。例1求使2n+1能被3整除的一切自然数n. 解：因为2-1(mod3)，所以2n(1)n(mod3). 则2n+11n+1mod3， 所以当n为奇

6、数时，2n+1能被3整除; 当n为偶数时，2n+1不能被3整除3.2奇偶分析法整数可以分为两类：奇数与偶数利用奇数与偶数的分类及其特殊性质，可以简单快捷地求解一些与整数有关的问题，我们把这种通过分析整数的奇偶性，分情况讨论，从而解决问题的方法称为奇偶分析法例6设是三个整数，证明在三个数，中至少有一个是的倍数思路分析本题要证明三个数中至少有一个是的倍数，可以分解为，且，又因为均为整数，则必有两个数奇偶性相同，那么可以假设奇偶性相同，由此利用数的奇偶性来分情况讨论，由此解答题目证明因为均为整数，则必有两个数奇偶性相同，不妨设奇偶性相同下面证明因为且，因此只须证明 且若中至少有一个是的倍数时，则有；

7、若均不是的倍数，则是用除余数分别为和当，则，从而；当同余时，则，则因此对任意整数均有若均为偶数时，显然；当均为奇数时，显然，均为偶数，且用除，余数分别为和，当，则；当时，则，所以综上所述，当奇偶性相同时，即三数，中至少有一个是的倍数3.3构造法解数学题时，根据问题的性质和结构特征，联想与此有关的数学知识，精心地设计一些特殊的“构造”（辅助模型），通过对这个辅助模型的的研究，便可把陌生的问题转化为熟悉的问题，把未解决的问题转化为已解决的问题，从而使问题获得解决这种解决问题的方法就叫做构造法构造思想贵在“创新”，解题时要打破常规，另辟蹊径，表现出简捷、明快、精巧等特点例7求的末尾两位数思路分析本题

8、看上去十分繁琐，让人无从下手题意要求的末尾两位数，即求与关于模同余的数，模又可分解为，可以先求与关于模同余的数，再逐步求出与关于模同余的数，然后利用同余的性质，求得最后答案解令，欲求的末尾两位数，即求，使得，由于，则，由于，故，则对于，当为奇数时，的个位数字为；当为偶数时，的个位数字为同理的个位数字应为故可设，从而得到：，即由得，代入得，从而有，于是，所以，的末尾两位数是3.4枚举法在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法特点：将问题的所有可能的答案列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃例8 对

9、于模，找出一组由奇数组成的完全剩余系和一组由偶数组成的完全剩余系对于模，找出一组由奇数组成的简化剩余系和一组由偶数组成的简化剩余系思路分析本题的考查目的比较单一，就是考查剩余类和剩余系的定理” 设为正整数，是任意整数，若通过模的一个完全剩余系，则也通过模的完全剩余系”，列出完全剩余系之后，再采用枚举法令取适当的值，即可求得符合题意的剩余系解因是模的一个完全剩余系，取，则，则，即是模的一组由奇数组成的完全剩余系同理，取，则，即是模的一组由偶数组成的完全剩余系因是模的一组非负最小简化剩余系，取，则有，即为模的一组由偶数作成的简化剩余系又因是模的一组完全剩余系，从中找出与互素的所有数，为，则此为模的一组由奇数组成的简化剩余系3.5反证法证明一个命题，如果把原结论的相反结论纳入到原命题条件中，由此经过正确推理，推导出和已知证明的定理、公理、题设等相矛盾的结果，或以两个不同的角度进行推理所得出的结论之间相互矛盾，那么即可肯定原来的结论成立，这种间接证明命题的方法叫做反证法例9求证不定方程无整数解思路分析如果直接求不定方程无整数解，会比较繁琐，那么就从本题的反面来思考，如果不定方程有整数解，那么带入原方程就应该成立，再通过一系列证明，即可得出矛盾，从而得证解设是方程的整数解，若，则；若，则显然有，与矛盾因此，此方程无整