初等数论同余PowerPoint 演示文稿

1、1 在日常生活中，我们常接触到一些周期为正整数性的问题.例如：问火车下午2点从金华出发,30小时后到广州,则到广州是几点?就是24去除30所得的余数6加2,即晚上8点到广州,这就是同余问题.今天是星期一,问过了100天后是星期几等,现在同余理论已发展成为初等数论中内容丰富，应用广泛的一个分支 第三章第三章 同余同余1 同余的概念及其基本性质同余的概念及其基本性质2定义定义：给定一个正整数m，我们把它叫做模，如果用m去除任意两个整数a与b所得的余数相同，我们就说a,b 对模m同余，记作 如果余数不同，我们就说a,b对模m不同余，记作 注注1：上面所说的模m1,因为m=1对所有整数就都同余了。注注

2、2: 同余和整除有密切关系,可相互转化, 有下面定理.).(modmba ).(modmba 3定理定理1：整数a,b对模同余的充分与必要条件是： m| a-b, 即 a=b+mt, t是整数。证明：设a=mq1+r1,b=mq2+r2, 若 则r1=r2 ,有a-b=m(q1-q2). 即m|a-b反之若m| a-b,则m| m(q1- q2)+(r1-r2),因此m |r1-r2, 但|r1-r2|0 则 (2)若 d|(a,b,m), d0 ,则 证:性质5显然.).(modmba ).(modmkbkak ).(modmba ).(moddmdbda)(|11badm)( |, 1),

3、(11bamdm10性质性质6 若 则证：由已知m|a-b,又d|m,所以d|a-b性质性质7 d|(a,b),(d,m)=1 则证： 因为 ，(d,m)=1 ，所以有0,),(moddmdmba).(moddba ).(modmba ).(modmdbda)(|dbdadmdbdam|11性质8 若 则 (a,m)=(b,m)证：由已知a=b+mt,故 (a,m)|a, (a,m)|m,有(a,m)|b,所以有 (a,m)|(b,m),同理可证(b,m)|(a,m), 即(a,m)=(b,m).性质9 若 则证：由已知 ,即a-b是所有 的公倍数，而最小公倍数整除所有公倍数，即有).(mod

4、mba ).,(mod21kmmmba,3 , 2 , 1).(modkimbai).,(mod21kmmmbakjbamj2 , 1,|jm12例1：证明13|42n+1+3n+2证：42n+1+3n+2416n+93n 3n (4+9)133n0(13) 13|42n+1+3n+2注：整除问题和同余问题是相互可以转化的把整除问题转化为同余问题是一种常用的方法.13例2：证明5y+3=x2无解证明：若5y+3=x2有解，则两边关于模5同余有5y+3x2(mod 5)即3x2(mod 5) 而任一个平方数x20,1,4(mod 5) 3 0,1,4(mod 5)，不可能 即得矛盾，即5y+3=

5、x2无解注：在证明方程无解时，经常用不同余就不相等的方法。14 2 同余的应用1、算术中的整除规律(1)个位数是偶数的数能被整除；(2)个位数是或的数能被整除；(3)末两位数能被（或）整除的数能被（或）整除；(4)末三位数能被（或）整除的数能被（或）整除；155)各位数字之和能被（或）整除的数能被（或）整除；6)奇数位数字之和与偶数位数字之和的差能被整除的数能被整除。7)设b=7（11，13），则b|a的充分必要条件是b| 注:整除规律一方面给出了整除的判定.另一方面也给出了求余数的方法.上述性质的证明差不多,我们证明其中的(6)(7)二条作一示范.niiia0) 1(0110001000aa

6、aann16规律(6)的证明证:设因为 两边分别乘以 然后相加有即奇数位数字之和与偶数位数字之和的差能被11整除的数能被11整除.0111010aaaannnn)11(mod) 1(10)11(mod110)11(mod110)11(mod112nnia)11(mod) 1(210aaaaann17规律(7)的证明证：一般地有两边同乘 有并对n+1个式子相加得 即有7|a的充要条件是 7|对模11和13同理可证。注：这里用的是1000进制。)7(mod11000),7(mod110000niii, 1 , 0),7(mod) 1(1000niiiaa0)7(mod) 1(niiia0) 1(i

7、a18例1:12345678910112005除以3的余数是多少.解:因为一个数除以3的余数,即其各位数字和除以3 的余数.所以所求余数 所以余数为1.)3(mod150022005109876543215002110198765432119例2：设数62XY427是99的倍数，求X，Y解：因为99=9*11，所以有 9|62XY427所以9|6+2+X+Y+4+2+7，即9|21+X+Y又有11|62XY427，有11 |（7+4+X+6-2-Y-2）即11|（X-Y+13）20因为0 X，Y 9，所以有21 21+X+Y 39，4 X-Y+13 22，由此可知21+X+Y=27，X-Y+1

8、3=11或21+X+Y=36，X-Y+13=22X+Y=6，X-Y=-2，或X+Y=15，X-Y=9，解得X=2，Y=4。21例3 ：求 被7除的余数。解：111111被7整除， 11（mod 7）4（mod 7）即余数为4。5011150111例4：求 被50除的余数解： 所以余数是29。2633)46257(26332633)47()46257(26162)4)7(7(552626)3(33)47(225)7(73)7(3)50(mod292122例5:证明: 是合数.证:因为由整除规律性,一个数被11整除的充要条件是它的奇数位数字之和与偶数位数字之和的差能被11整除.而 的奇数位数字之和

9、与偶数位数字之和的差为0,所以能被11整除.即为合数. 0200001100个 0200001100个233 剩余类及完全剩余系剩余类及完全剩余系 若m是一个给定的正整数，由带余数除法则对任意的整数a= qm+r则全部整数可分成m个集合，k0 ,k1,km-1, 其中 (r=0,1,2m-1) (1) (2) (3) ,|ZxrmqxxKrrmrKZ10)(jiKKjiiKba,)(modmiba242 弃九法利用相等必同余，同余未必相等，不同余肯定不相等,取模9,可判断一些式子是否正确在出现9时,用 可把9去掉,这就是弃九法.例:判断28997*39495=1145236415是否正确?解:

10、若正确,则两边关于9同余,则有8*3 5,不成立所以错误.注:弃九法只能检查出一些错误.不能检查出所有错误.看下面的例.)9(mod09 25例判断28997*39495=11154236415是否正确解:两边关于9同余,则有8*3 6,成立此时不能判定,有可能正确,也可能错误,需作进一步判定.若正确,进一步取模为11,则有1*5 3(mod11)不成立,所以错误.26例判断28997*39495=11145236415是否正确解:两边关于9同余,则有8*3 5,不成立所以错误.27例判断28997*39495=11145236415是否正确解:两边关于9同余,则有8*3 5,不成立所以错误.

11、28定义定义：称k0 ,k1,km-1叫做模m的剩余类，设a0,a1am-1是m个整数，并且其中任何两数都不在一个剩余类里，则a0,a1am-1叫做模m的一个完全剩余系(简称完系)推论推论：m个整数成为模的一个完全剩余系的充分与必要条件是:两两对模m不同余。注:一组数成为模m的完系的充要条件是(1)个数=m(2)两两关于模m不同余29常见模m的完全剩余系(简称完系）0,1,2,m-1做模m的最小非负完全剩余系；当m是双数时， 或当是m单数时， ,叫做模m的绝对最小完全剩余系121 , 0 , 1,2mm21 , 0 , 1, 12mm211 , 0 , 121mm30定理定理1：设m是正整数，

12、(a,m)=1,b是任意整数。若x通过模m的一个完系，则ax+b也通过模m的完系，即若a0,a1am-1是模m的完系，则aa0+b,aa1+baam-1+b也是模m的完系。证：首先因x通过模m的一个完系，所以ax+b有m个数，若 , 则有这与x通过m的完系矛盾，所以ax+b中任意两个数不同余，即ax+b也通过模m的完系。)(modmbaxbaxji)(modmxxji31定理定理2：若m1,m2是互质的两个正整数，x1,x2分别通过模m1,m2的完全剩余系， 则 通过模m1m2的完全剩余系。注:定理2给出了如何用m1,m2的完全剩余系构造m1m2完全剩余系的方法.2112xmxm例：3的完系是

13、1，2，3；2的完系是1，2则6的完系是21+ 31, 21+ 32,22+ 31, 22+ 32, 23+ 31,23+ 32,即为5,2,1,4,3,0下面给出定理的证明.32证：首先 一共通过了 个数，下证这 个数关于模 是两两不同余的。设 则有 由已知m1,m2是互质，所以有与题设矛盾. 所以这 个数关于模 是两两不同余的 即 通过模m1,m2的完系。2112xmxm21mm21mm)(mod21, ,21, ,12,21,12mmxmxmxmxm)(mod1,12,12mxmxm，)(mod2,21,21mxmxm，)(mod1, ,1,1mxx )(mod2, ,2,2mxx 21

14、mm21mm2112xmxm21mm334 简化剩余系与欧拉函数简化剩余系与欧拉函数定义定义1：欧拉函数(a)是定义在正整数上的函数，定义为序列0,1,2,a-1中与a互质的数个数。约定约定(1)=1，显然(p)=p-1定义定义2：如果一个模m的剩余类里面的数与m互质，就把它叫做一个与模m互质的剩余类。 在与模m互质的全部剩余类中，从每一类各任取一数所作成的元数的集合，叫做模m的一个简化剩余系（简称简系）。一组数是m的一个简系的条件为(1）元素个数为(m)(2)两两不同余关于模m(3)每一个元素x,有(x,m)=134定理定理1 若(a,m)=1，x通过模m的简化剩余系，则ax通过模m的简化剩

15、余系。证：ax有(m)个数，因(a,m)=1， (x,m)=1所以（ax，m）=1，若 ,则 ，这与已知矛盾。所以ax通过模m的简化剩余系。)(mod21maxax )(mod21mxx 35定理定理2：若m1,m2是两个互质的正整数， x1,x2分别通过模m1,m2的简化剩余系，则m2x1+m1x2通过模m1m2的简化剩余系。证证:(1) 设设x1,x2分别通过模m1,m2的完全剩余系，则m2x1+m1x2通过模m1m2的完全剩余系。(2) (m2x1+m1x2， m1m2)=1(m2x1+m1x2， m1m2)=1有(m2x1+m1x2， m2)=1有(m1x2， m2)=1有(x2， m

16、2)=1,同理有 反之也对。所以当x1,x2分别通过模m1,m2的简化剩余系，则m2x1+m1x2通过模m1m2的简化剩余系。1,(1,(2211），）mxmx1,(11）mx36推论推论：若m1,m2是两个互质的正整数，则(m1m2) = (m1 ). (m2)例：由定义有设 因为 = =1)(pppkkpppa2121, 1),(jijipp)()()()(2121kkpppa)()(11221112211kkkkpppppp)11 ()11)(11 (21kpppa37推论1：推论2:证：所以 =mppp)()() 1 (mdmd|)(iikkpppd0 ,2121kkkkmdpppd0

17、0201|)()()()(222111385 欧拉定理欧拉定理 费尔马定理费尔马定理（欧拉定理欧拉定理）设m是大于1的整数，(a,m)=11(modm).a(m)注:欧拉定理是数论中最重要的一个定理 例:因为(7,2005)=1,所以有说明欧拉定理的用处之大,下面给出定理的证明.1(mod2005)771600(2005)39证：让通过模的简系：设为r1,r2,r(m)，则也通过的简系,为a r1,ar2,ar(m) 于是有对任意的i,有j使得 i=1,2 (m)把上面(m)同余式逐项相乘，得 即由性质有 ,所以有1(modm).a(m)(modmararji)(mod)(21)(21mrrr

18、arararmm)(mod)(21)(21)(mrrrrrrammm1),)(21mrrrm（40推论:若d是 成立的最小正整数,且 则d|n.)(mod1mad)(mod1man证明:假设结论不成立,则n=dq+r,0r2，则2P-1的质因数一定是2pk+1形。证：设q是2-1的质因数，由于2-1为奇数， q2， （2q）=1,由条件q|2p-1,即21（mod q）又 （q,2）=1， 2p 1（mod q）设i是使得2x 1（mod p）成立最小正整数若1ip，则有i|p则与p为素数矛盾 i=p, p|q-1又 q-1为偶数，2|q-1, 2p|q-1,q-1=2pk,即q=2pk+14

19、5例4：证明相邻两个整数的立方之差不能被5整除. 证明： 因为 所以只需证明 对任意的n关于5都不同余零。而我们知道模5的完全剩余系由-2,-1,0,1,2构成,所以这只需将n=0,1,2对于模5代入有 ，而1，2，4 不同余0，所以有相邻两个整数的立方之差不能被5整除. 133) 1(233nnnn)5(mod4 , 2 , 11332 nn1332 nn1332 nn46例5:若 为素数,则有1999|pp5 , 2p证:因为(P,2)=1,(P,5)=1,所以有 (P,10)=1由欧拉定理有即即110|1pp)(mod1101pp1999|pp47 循环小数和分数的互化 定义：如果对于一个无限小数0.a1a2an(an是0,1,29之中的一个数码，并且从任何一位以后不全是0)能找到两个整数s，t使得as+i=as+kt+i,i=1,2,t; k=0,1,2我们就称它为循环小数，并简单地把它记作0.a1a2asas+1as+t.对于循环小数而言，具有上述性质的s及t是不只一个的，如果找到的t是最小的，我们就称