浅谈同余及其应用.doc

。揭阳职业技术学院 毕 业 论 文（设计） 题 目： 浅谈同余定理及其应用学生姓名 黄 指导教师 某某某系（部） 师范教育系 专 业 数学教育班级 999 班 学号 11211211 提交日期 200 年 月 日 答辩日期 200 年 月 日200 年 月 日 浅谈同余定理及其应用摘 要初等数论是研究数的规律，特别是整数性质的数学分支。它 以算术方法为主要研究方法，在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。同余理论是初等数论中的重要内容之一，其性质及应用研究已引起许多学者的关注。本文归纳总结了同余的若干性质，结合实例，探究了同余性质在检验、判断整除问题、求余数、判断合数、韩信点兵问题等方面的具体应用。体现了用同余性质解决问题的简洁性。关键词：同余 整除 余式 方程绪论初等数论是研究整数性质的一门学科，它是数学中最古老的分支之一，内容极为丰富，曾被数学家说成是数学的皇后。同余问题在当今中小学乃至大学的数学教学中都有涉及，它作为初等数论的核心内容之一，具有很强的应用价值，很多数学问题都要借助同余理论来解决。同余的应用问题分为很多种类型，每种类型的题目又有一定的解题技巧。掌握了这些题型的技巧，可以提高大家解决问题的能力。本文基于对同余理论的理解，将应用同余理论解决的问题具体整理分类，从中分析出一些借助同余理论解题的技巧与规律。现在初等数论中关于同余的内容主要包括：同余的定义及基本性质、剩余类与剩余系、欧拉定理、费马小定理、循环小数、一次同余方程及一次同余方程组。到目前为止，古今中外很多学者与数学家，对同余的应用问题都有了一定的研究。在中国，早在宋代，大数学家秦九韶所著的数书九章中就记载了求解同余方程的“大衍求一术”。还有，著名的古代数学著作孙子算经中也记载能解决“物不知其数”问题的孙子定理，也被称作“中国剩余定理”。以及“韩信点兵”问题的研究，都为解决一次同余方程和同余方程组的问题带来了便利。在西方，除了高斯引入同余的概念之外，欧拉和费马提出的定理也为解决同余的相关问题做出了重要的贡献。希望通过本文的研究能将同余理论的应用问题更加系统全面的展现出来。以便，今后大家在探究同余理论时，能对同余应用问题的类型和解决技巧有一个清晰的认识和理解，更好的解决相关问题。1 相关性质定理1性质1 同余是一种等价关系，即有：（1）反身性 aa（mod m）.（2）对称性 若ab（mod m），则ba（mod m）. （3）传递性 若ab（mod m）， bc（mod m），则ac（mod m）. 性质2 同余式可以相加减,即若 ab（mod m），cd（mod m），则(1) acbd（mod m）.(2) acbd（mod m）. 性质3 同余式可以相乘,即有：(1) 若ab（mod m）， c为自然数, 则acbc（mod m）. (2) 若ab（mod m），cd（mod m），则acbd（mod m）.(3) 若ab（mod m）， n2, 则anbn（mod m）.性质4 若acbc（mod m），且（c，m）=1，则 有ab（mod m）.（其中（c，m）表示c与m的最大公约数）。 定理1 整数a,b对模m同余的充分与必要条件是mab ,即 abmt. (t是整数.)定理2 设a,则a(1)(1)(1)定理3 (Euler) 设m是大于1的整数， (a,m)=1， 则 a1（modm），其中为欧拉函数 定理4 (Fermat) 若p是素数，则apa（modp）. .证明以上三个定理:定理1证明: 设 a=mq1r1, b=mq2r2, 0r1m, 0r2m, 若ab（mod m）, 则r1=r2, 因此ab=mq1q2. 反之, 若 m | ab, 则m |mq1q2r1r2,因此 m | r1r2. 又 | r1r2 |m,故r1=r2定理3证明: 设a1 a2 a, 是modm的一个简化剩余系，且（a,m）=1,aa1 aa2 aa也是modm的一个简化剩余系. a1 a2, a,aa1 aa2 aa (modm）aa1 a2 a（modm）. 因此a1（modm）.定理4证明: 若（a,p）1,则有ap-1a（modp）,因而apa（modp）.若（a,p）1,则p|a,因而ap0（modp）, a0（modp）故apa（modp）2 同余性质的应用2.1 求余数问题 2.1.1 利用同余的性质及定理求余数 例1：将从1开始的连续自然数依次写下来，一直写到2003成为一个多位数，12345620022003，求这个数除以3的余数。解：由连续的3个自然数的和必能被3整除，而3|2001，（2+0+0+2+2+0+0+3）0（mod3）, 所以原多位数除以3余数为0例2：求201022001被3除所得的非负余数.解： 设201022001=3qr, 其中0r3, 故 r201022001（mod3）且0r3.又20102=36702, 所以201022(mod3).从而 22001220002410002(mod3)而 22001220002410002(mod3),41(mod3)故 410001 (mod3) ,4100022 (mod3).从而 r2(mod3). 而0r3, 故r=2.即 201022001除以3所得的余数为2.分析：此类题目解题的关键在于应用同余的乘方性，先求出底数20102对3的余数，再根据性质求出余数的2001次幂对3的余数即可例3：求4373091993被7除的余数。解：4733（mod7）3091（mod7）由同余的可乘性知：43730931（mod7）3（mod7）又因为19935（mod7）所以：437309199335（mod7）15（mod7）1（mod7）即：4373091993被7除余1。分析：此类题目解题的关键在于应用同余的可乘性，分别求出每个因数对于7的余数，在相乘即可简单求出2.1.2 求星期几问题求某年某月某日为星期几时,则令D=第N年m月d日,设D这一天为星期WD ,WD dy2c(mod7)其中c,y满足N100cy,0y100.注意:算出的结果为1 至7,各代表星期一到星期日.例:1949年10月1日是星期几?2.1.3 尾数问题例1：求243402的末三位数？解：因为（243，1000）=1，=10001 ）（1 ）=400由欧拉定理知，243400 1（mod1000），故243402243249（mod1000）所以243402的末三位数为049.例2：求3200172002132003的个位数字？解：应用欧拉定理，（3,10）=1,341（mod10）,则有3200134k13（mod10）；同理，741（mod10）， 7200274k29（mod10）； 1341（mod10），132003134k37（mod10）；因379189，故个位数字为 9 .分析：利用同余的性质，求一个数字的个位数字就是求其除以10所得的余数,同类题型的变换问法：求某数的末两位数字是多少?（模为100）2.2 同余在检验方面的应用2.2.1 检查因数的一些方法1 方法一： 一整数能被3（9）整除的必要且充分的条件是它的十进位数码的和能被3（9）整除. 证明：显然我们只须讨论任一正整数a便可.把a写成十进位数的形式：a=an10nan110n1a110a0 , 0ai10. 因101（mod 3）,故由定理2得aanan1a1a0（mod 3）.由已知性质，即知3a当且仅当ai.同法可得9a当且仅当9ai方法二： 设正整数 a=an1000nan11000n1a11000a0 , 0ai1000.则7（或11，或13）整除a的必要且充分的条件是7（或11或13）整除（a0a2）-（a1a3）=(1)iai证明：因为1000与-1对模7（或11或13）同余，故由定理知a与(1)iai 对模7（或11或13）同余.由已知性质，7（或11或13） 整除a当且仅当7（或11或13）整除(1)iai 2.2.2 弃九法1（假设我们由普遍乘法的运算方法求出整数a，b的乘积是P，并令 a=an10nan110n1a110a0 , 0ai10.b=bm10mbm110m1b110b0 , 0bj10.P=cl10lcl110l1c110c0 , 0ck10.我们说：如果（ai）（bj）不同余于ck（mod9）， 那么所求得的乘积是错误的.因为ab（ai）（bj）（mod9），P ck（mod9）. 若 （ai）（bj）不同余于ck（mod9）， 则ab不同余P（mod9）， 故ab不是P.2.2.3 判定合数 由费马定理可得推论如下 若p是素数，且(a,p) 1，则ap11(modp).利用推论可以判定一个数是否为合数，即若N是我们要检验的数，先取某一个与N互素并比N小的数a，通常合适的是把a取为不能整除N的小素数，如a2, a3或a5 如果N是素数那么由推论它应该满足aN11(modN)，因此如果验算这个同余不成立，我们就断言 N 是合数.例2 判断 N117 是否为合数. 分析 我们根据定理3即费马定理，可以考虑若N是素数， 则有aN11(modN)，N为我们所检验的数.解：选a=2则a与N互素，aN1=2116=26423221624，而28=25622(mod117), 216=28)222216(mod117)， 232=216)216222(mod117)，264=232)222216(mod117)， 故21162642322162416221616321(mod117). 由推论知N是合数，事实上117339.2.3 利用同余的性质解决整除问题 整除问题是数论中的一个重要问题，在初等数学中我们可以直接运用定义和性质解决简单的整除问题，而对于复杂的问题计算则较为麻烦，利用同余良好的性质便可简便的解决复杂的整除问题. 例1 求证1985|3237n632n855n235n,nN.-+ 分析 记A=3237n632n855n235n, nN,由于1985=5397,所以1985|AA0(mod1985)A0 (mod5), A0 (mod397)证明 记A=3237n632n855n235n,nN,根据定理1只要证明A0 (mod1985) 即可，由于1985=5397，故只要证明A0(mod5) 和A0(mod397) 成立. 事实上，由于32372(mod5),6322(mod5),8550(mod5),2350(mod5), 根据性质3，nN,则有 3237n 2n(mod5),632n2n(mod5), 855n0(mod5), 235n0(mod5),所以A2n2n000(mod5). 又由于323761(mod397), 632235(mod397), 85561(mod397), 235235(mod397), 根据性质3, nN 我们有 3237n61n(mod397), 632n235n(mod397), 855n61n(mod397), 235n235n(mod397), 所以A61n235n61n235n0(mod397). 又因为(5,397) 1=，所以A0(mod5397),即A0(mod1985). 根据同余整除关系知nN,必有1985|A,即 1985|3237n632n855n235n3.3 中国古代同余问题3.3.1 中国剩余问题2 孙子算经卷下“物不知数”题说：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？显然，这相当于求不定方程组 N=3x+2，N=5y+3，N=7z+2 的正整数解N，或用现代数论符号表示，等价于解下列的一次同余组： N 2(mod3) N3(mod5) N2(mod7) 孙子算经所给答案是N23。3.3.2 韩信点兵问题曰: 有兵一队,若列成五行纵队,则末行一人,成六行纵队,则末行五人,成七行纵队,则末行四人,成十一行纵队,则末行十人,求兵数.解:由题意有x1(mod5), x5(mod6), x4(mod7), x10(mod11)求得x2111（2310）同余理论是初等数论中最核心的内容之一，由同余定义可知，若ab(modm)，则 a 和 b被 m除后有相同的余数。这里m 为正整数，一般要求 m大于1，称为模，同余这一思想本质上是将整数按模m 分类，然后讨论每一个类中整数所具有的共性及不同类之间的差异。从同余的定理上看，同余和整除实际上是同一回事，故同余还有两个等价的定义：用整除来定义即ma-b。用等号来定义a=b+mt。值得注意a和 b关于m同余个相对的概念。即它是相对于模 m来讲，两个整数 a和 b关于一个整数模m 同余。则对于另一个整数模mi，a 和 b未必会同余。参考文献1闵嗣鹤、严士健： 初等数论,高等教育出版社，2003年第三版。 2 孙