揭阳职业技术学院毕业论文（设计）题目：浅谈同余定理及其应用学生姓名黄指导教师某某某系（部）师范教育系专业数学教育班级 999 班学号 ********提交日期200 年月日答辩日期 200 年月日200 年月日浅谈同余定理及其应用摘要初等数论是研究数的规律，特别是整数性质的数学分支。

它以算术方法为主要研究方法，在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。

同余理论是初等数论中的重要内容之一，其性质及应用研究已引起许多学者的关注。

本文归纳总结了同余的若干性质，结合实例，探究了同余性质在检验、判断整除问题、求余数、判断合数、韩信点兵问题等方面的具体应用。

体现了用同余性质解决问题的简洁性。

关键词：同余整除余式方程绪论初等数论是研究整数性质的一门学科，它是数学中最古老的分支之一，内容极为丰富，曾被数学家说成是数学的皇后。

同余问题在当今中小学乃至大学的数学教学中都有涉及，它作为初等数论的核心内容之一，具有很强的应用价值，很多数学问题都要借助同余理论来解决。

同余的应用问题分为很多种类型，每种类型的题目又有一定的解题技巧。

掌握了这些题型的技巧，可以提高大家解决问题的能力。

本文基于对同余理论的理解，将应用同余理论解决的问题具体整理分类，从中分析出一些借助同余理论解题的技巧与规律。

现在初等数论中关于同余的内容主要包括：同余的定义及基本性质、剩余类与剩余系、欧拉定理、费马小定理、循环小数、一次同余方程及一次同余方程组。

到目前为止，古今中外很多学者与数学家，对同余的应用问题都有了一定的研究。

在中国，早在宋代，大数学家秦九韶所著的《数书九章》中就记载了求解同余方程的“大衍求一术”。

还有，著名的古代数学著作《孙子算经》中也记载能解决“物不知其数”问题的孙子定理，也被称作“中国剩余定理”。

以及“韩信点兵”问题的研究，都为解决一次同余方程和同余方程组的问题带来了便利。

在西方，除了高斯引入同余的概念之外，欧拉和费马提出的定理也为解决同余的相关问题做出了重要的贡献。

希望通过本文的研究能将同余理论的应用问题更加系统全面的展现出来。

以便，今后大家在探究同余理论时，能对同余应用问题的类型和解决技巧有一个清晰的认识和理解，更好的解决相关问题。

1 相关性质定理[1]性质1同余是一种等价关系，即有：（1）反身性 a≡a（mod m）.（2）对称性若a≡b（mod m），则b≡a（mod m）.（3）传递性若a≡b（mod m）， b≡c（mod m），则a≡c（mod m）.性质2同余式可以相加减,即若 a≡b（mod m），c≡d（mod m），则(1) a＋c≡b＋d（mod m）.(2) a－c≡b－d（mod m）.性质3同余式可以相乘,即有：(1) 若a ≡b （mod m ）， c 为自然数, 则ac ≡bc （mod m ）. (2) 若a ≡b （mod m ），c ≡d （mod m ），则ac ≡bd （mod m ）. (3) 若a ≡b （mod m ）， n ≥2, 则a n ≡b n （mod m ）.性质4 若ac ≡bc （mod m ），且（c ，m ）=1，则有a ≡b （mod m ）.（其中（c ，m ）表示c 与m 的最大公约数）。

定理1 整数a,b 对模m 同余的充分与必要条件是m ∣a －b ,即 a ＝b ＋mt. (t 是整数.)定理2 设a ＝11αp 22αp …kk p α,则)a （ϕ＝a(1－11p )(1－21p )…(1－kp 1) 定理3 (Euler) 设m 是大于1的整数， (a,m)=1， 则a )m （ϕ≡1（modm ），其中)m （ϕ为欧拉函数定理4 (Fermat) 若p 是素数，则a p ≡a （modp ）..证明以上三个定理:定理1证明: 设 a=mq 1＋r 1, b=mq 2＋r 2, 0≤r 1＜m, 0≤r 2＜m, 若a ≡b （mod m ）, 则r 1=r 2, 因此a －b=m ﹙q 1－q 2﹚.反之, 若 m | a －b, 则m |m ﹙q 1－q 2﹚＋﹙r 1－r 2﹚,因此 m | r 1－r 2. 又 | r 1－r 2 |＜m ,故r 1=r 2定理3证明: 设a 1 a 2 … a )m （ϕ, 是modm 的一个简化剩余系， 且（a ,m ）=1,aa 1 aa 2 … aa )m （ϕ也是modm 的一个简化剩余系. a 1 a 2,… a )m （ϕ,≡aa 1 aa 2 … aa )m （ϕ (modm ） ＝a )m （ϕa 1 a 2 … a )m （ϕ（modm ）. 因此a )m （ϕ≡1（modm ）.定理4证明: 若（a,p ）＝1,则有a p-1≡a （modp ）,因而a p ≡a （modp ）.若（a,p ）≠1,则p|a ,因而a p ≡0（modp ）, a ≡0（modp ） 故a p ≡a （modp ）2 同余性质的应用2.1 求余数问题2.1.1 利用同余的性质及定理求余数例1：将从1开始的连续自然数依次写下来，一直写到2003成为一个多位数，123456…20022003，求这个数除以3的余数。

解：由连续的3个自然数的和必能被3整除，而3|2001，（2+0+0+2+2+0+0+3）≡0（mod3）, 所以原多位数除以3余数为0例2：求201022001被3除所得的非负余数.解：设201022001=3q＋r, 其中0≤r＜3, 故r≡201022001（mod3）且0≤r＜3.又20102=3×670＋2,所以20102≡2(mod3).从而22001≡22000×2≡41000×2(mod3)而 22001≡22000×2≡41000×2(mod3),4≡1(mod3)故 41000≡1 (mod3) ,41000×2≡2 (mod3).从而 r≡2(mod3). 而0≤r＜3, 故r=2.即 201022001除以3所得的余数为2.分析：此类题目解题的关键在于应用同余的乘方性，先求出底数20102对3的余数，再根据性质求出余数的2001次幂对3的余数即可例3：求437×309×1993被7除的余数。

解：473≡3（mod7）309≡1（mod7）由"同余的可乘性"知：437×309≡3×1（mod7）≡3（mod7）又因为1993≡5（mod7）所以：437×309×1993≡3×5（mod7）≡15（mod7）≡1（mod7）即：437×309×1993被7除余1。

分析：此类题目解题的关键在于应用同余的可乘性，分别求出每个因数对于7的余数，在相乘即可简单求出2.1.2 求星期几问题求某年某月某日为星期几时,则令D=第N年m月d日,,设D这一天为星期WDW D ≡d ＋[51m 13-]＋y ＋[4y ]＋[4c]＋2c(mod7) 其中c,y 满足N ＝100c ＋y,0≤y ≤100.注意:算出的结果为1 至7,各代表星期一到星期日.例:1949年10月1日是星期几?2.1.3 尾数问题例1：求243402的末三位数？解：因为（243，1000）=1，()1000ϕ=1000×﹙1－21）（1－ 51）=400 由欧拉定理知，243400 ≡1（mod1000），故243402≡2432≡49（mod1000） 所以243402的末三位数为049.例2：求32001·72002·132003的个位数字？ 解：应用欧拉定理，（3,10）=1,34≡1（mod10）,则有32001≡34k ＋1≡3（mod10）；同理，74≡1（mod10）， 72002≡74k ＋2≡9（mod10）；134≡1（mod10），132003≡134k ＋3≡7（mod10）； 因3×7×9＝189，故个位数字为 9 .分析：利用同余的性质，求一个数字的个位数字就是求其除以10所得的余数, 同类题型的变换问法：求某数的末两位数字是多少?（模为100）2.2 同余在检验方面的应用2.2.1 检查因数的一些方法[1]方法一： 一整数能被3（9）整除的必要且充分的条件是它的十进位数码的和能被3（9）整除.证明：显然我们只须讨论任一正整数a 便可.把a 写成十进位数的形式：a=a n 10n ＋a n －110n －1＋…＋a 1×10＋a 0 , 0≤a i <10. 因10≡1（mod 3）,故由定理2得a≡a n ＋a n －1＋…＋a 1＋a 0（mod 3）.由已知性质，即知3︱a 当且仅当3︱∑=ni 0a i .同法可得9︱a 当且仅当9︱∑=ni 0a i方法二： 设正整数a=a n 1000n ＋a n －11000n －1＋…＋a 1×1000＋a 0 , 0≤a i <1000.则7（或11，或13）整除a 的必要且充分的条件是7（或11或13）整除（a 0＋a 2＋…）-（a 1＋a 3＋…）=∑=ni 0(﹣1)i a i证明：因为1000与-1对模7（或11或13）同余，故由定理知a 与∑=ni 0(﹣1)i a i 对模7（或11或13）同余.由已知性质，7（或11或13） 整除a 当且仅当7（或11或13）整除∑=ni 1(﹣1)i a i2.2.2 弃九法[1]（假设我们由普遍乘法的运算方法求出整数a ，b 的乘积是P ，并令 a=a n 10n ＋a n －110n －1＋…＋a 1×10＋a 0 , 0≤a i <10.b=b m 10m ＋b m －110m －1＋…＋b 1×10＋b 0 , 0≤b j <10. P=c l 10l ＋c l －110l －1＋…＋c 1×10＋c 0 , 0≤c k <10.我们说：如果（∑=ni 0a i ）（∑=mj 0b j ）不同余于∑=lk c k （mod9），那么所求得的乘积是错误的.因为ab≡（∑=n i 0a i ）（∑=m j 0b j ）（mod9），P≡ ∑=lk c k （mod9）.若 （∑=ni 0a i ）（∑=mj 0b j ）不同余于∑=lk c k （mod9），则ab 不同余P （mod9）， 故ab 不是P.2.2.3 判定合数由费马定理可得推论如下若p 是素数，且(a,p) ＝1，则a p －1≡1(modp).利用推论可以判定一个数是否为合数，即若N 是我们要检验的数，先取某一个与N 互素并比N 小的数a ，通常合适的是把a 取为不能整除N 的小素数，如a ＝2, a ＝3或a ＝5…… 如果N 是素数那么由推论它应该满足a N －1≡1(modN)，因此如果验算这个同余不成立，我们就断言 N 是合数.例2 判断 N ＝117 是否为合数.分析 我们根据定理3即费马定理，可以考虑若N 是素数， 则有a N －1≡1(modN)，N 为我们所检验的数.解：选a=2则a 与N 互素，a N －1=2116=264×232×216×24，而28=256≡22(mod117),216=﹙28)2≡222≡16(mod117)，232=﹙216)2≡162≡22(mod117)，264=﹙232)2≡222≡16(mod117)，故2116≡264×232×216×24≡16×22×16×16≡32≡1(mod117).由推论知N是合数，事实上117＝3×39.2.3 利用同余的性质解决整除问题整除问题是数论中的一个重要问题，在初等数学中我们可以直接运用定义和性质解决简单的整除问题，而对于复杂的问题计算则较为麻烦，利用同余良好的性质便可简便的解决复杂的整除问题.例1 求证1985|3237n－632n－855n＋235n,n∈N﹢.分析记A=3237n－632n－855n＋235n, n∈N﹢,由于1985=5×397,所以1985|A⇔A≡0(mod1985)⇔A≡0 (mod5), A≡0 (mod397)证明记A=3237n－632n－855n＋235n,n∈N﹢,根据定理1只要证明A≡0 (mod1985) 即可，由于1985=5×397，故只要证明A≡0(mod5) 和A≡0(mod397) 成立. 事实上，由于3237≡2(mod5),632≡2(mod5),855≡0(mod5),235≡0(mod5),根据性质3，∀n∈N﹢,则有3237n ≡2n(mod5),632n≡2n(mod5), 855n≡0(mod5), 235n≡0(mod5),所以A≡2n－2n－0＋0≡0(mod5).又由于3237≡61(mod397), 632≡235(mod397),855≡61(mod397), 235≡235(mod397),根据性质3, n∈N﹢我们有3237n≡61n(mod397), 632n≡235n(mod397),855n≡61n(mod397), 235n≡235n(mod397),所以A≡61n－235n－61n＋235n≡0(mod397).又因为(5,397)≡1，所以A≡0(mod5×397),即A≡0(mod1985). 根据同余整除关系知∀n∈N﹢,必有1985|A,即1985|3237n－632n－855n＋235n3.3 中国古代同余问题3.3.1 中国剩余问题[2]《孙子算经》卷下“物不知数”题说：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？显然，这相当于求不定方程组N=3x+2，N=5y+3，N=7z+2 的正整数解N，或用现代数论符号表示，等价于解下列的一次同余组：N≡ 2(mod3) N≡3(mod5) N≡2(mod7)②《孙子算经》所给答案是N＝23。