初等數(shù)論同余

1、在日常生活中，我們常接觸到一些周期為正整數(shù)性的問(wèn)題.例如：?jiǎn)柣疖?chē)下午2點(diǎn)從金華出發(fā),30小時(shí)后到廣州,則到廣州是幾點(diǎn)?就是24去除30所得的余數(shù)6加2,即晚上8點(diǎn)到廣州,這就是同余問(wèn)題.今天是星期一,問(wèn)過(guò)了100天后是星期幾等……．,現(xiàn)在同余理論已發(fā)展成為初等數(shù)論中內(nèi)容豐富，應(yīng)用廣泛的一個(gè)分支．,第三章 同余§1 同余的概念及其基本性質(zhì),定義：給定一個(gè)正整數(shù)m，我們把它叫做模，如果用m去除任意兩個(gè)整數(shù)a與b所得的余數(shù)相同，

2、我們就說(shuō)a,b 對(duì)模m同余，記作 如果余數(shù)不同，我們就說(shuō)a,b對(duì)模m不同余，記作 注1：上面所說(shuō)的模m>1,因?yàn)閙=1對(duì)所有整數(shù)就都同余了。注2: 同余和整除有密切關(guān)系,可相互轉(zhuǎn)化, 有下面定理.,,,定理1：整數(shù)a,b對(duì)模同余的充分與必要條件是： m| a-b, 即 a=b+mt, t是整數(shù)。證明：設(shè)a=mq1+r1,b=mq2+r2, 若

3、 則r1=r2 ,有a-b=m(q1-q2). 即m|a-b反之若m| a-b,則m| m(q1- q2)+(r1-r2),因此m |r1-r2, 但|r1-r2|<m, 故 r1=r2下面我們來(lái)討論同余的性質(zhì).,性質(zhì)1: (1) (2)

4、 則 (3) 則注3：a. 性質(zhì)1說(shuō)明同余是一種等價(jià)關(guān)系。b. 由同余的定義可知: 相等必同余，同余未必相等，不同余肯定不相等,這是一種很好的方法，尤其在證明不相等時(shí)非常有用。,性質(zhì)2: (1)若 則 證：由定理

5、 , 因此有 ,即 (2)若 則證：由（1）因?yàn)?, 即得。注4：性質(zhì)2相當(dāng)于等式中的兩個(gè)等式相加和移項(xiàng).結(jié)合前二條性質(zhì),我們來(lái)看幾個(gè)例子.,例1:對(duì)任意整數(shù)

6、a,8a+7不可能是三個(gè)整數(shù)的平方.,證:因?yàn)閷?duì)任意的整數(shù) 有所以對(duì)任意的有兩邊不同余.所以不相等.即對(duì)任意整數(shù)a,8a+7不可能是三個(gè)整數(shù)的平方.,例2證明 沒(méi)有整數(shù)解.,證:因?yàn)橐粋€(gè)平方數(shù)除以4的余數(shù)能為0或者1所以左邊除以4的余數(shù)只能是0,1,或3,而右邊除以4的余數(shù)為2不同余,所以不定方程無(wú)解.,,性質(zhì)3、若

7、 則有 特別地，若 則 設(shè) 若 則有,性質(zhì)4 若a=a1d, b=b1d, (d,m)=1, 則證：由已知,性質(zhì)5 (1)若 k>0 則 (2)若 d|(a,b,m), d>

8、;0 ,則 證:性質(zhì)5顯然.,性質(zhì)6 若 則證：由已知m|a-b,又d|m,所以d|a-b性質(zhì)7 d|(a,b),(d,m)=1 則證： 因?yàn)?，(d,m)=1 ，所以有,性質(zhì)8 若 則 (a,m)=(

9、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).性質(zhì)9 若 則證：由已知 ,即a-b是所有 的公倍數(shù)，而最小公倍數(shù)整除所有公倍數(shù)，即有,,,例1：

10、證明13|42n+1+3n+2證：∵42n+1+3n+2≡4·16n+9·3n ≡3n (4+9)≡13×3n·≡0(13)∴ 13|42n+1+3n+2注：整除問(wèn)題和同余問(wèn)題是相互可以轉(zhuǎn)化的把整除問(wèn)題轉(zhuǎn)化為同余問(wèn)題是一種常用的方法.,例2：證明5y+3=x2無(wú)解證明：若5y+3=x2有解，則兩邊關(guān)于模5同余有5y+3≡x2(mod 5)即3≡x2(mod 5) 而任一個(gè)平方數(shù)

11、x2≡0,1,4(mod 5) ∴ 3 ≡ 0,1,4(mod 5)，不可能∴ 即得矛盾，即5y+3=x2無(wú)解注：在證明方程無(wú)解時(shí)，經(jīng)常用不同余就不相等的方法。,§2 同余的應(yīng)用1、算術(shù)中的整除規(guī)律(1)個(gè)位數(shù)是偶數(shù)的數(shù)能被２整除；(2)個(gè)位數(shù)是０或５的數(shù)能被５整除；(3)末兩位數(shù)能被４（或２５）整除的數(shù)能被４（或２５）整除；(4)末三位數(shù)能被８（或１２５）整除的數(shù)能被８（或１２５）整除；,,5)各位數(shù)字之和

12、能被３（或９）整除的數(shù)能被３（或９）整除；6)奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差能被１１整除的數(shù)能被１１整除。7)設(shè)b=7（11，13），則b|a的充分必要條件是b| 注:整除規(guī)律一方面給出了整除的判定.另一方面也給出了求余數(shù)的方法.上述性質(zhì)的證明差不多,我們證明其中的(6)(7)二條作一示范.,規(guī)律(6)的證明,證:設(shè)因?yàn)?

13、 兩邊分別乘以 然后相加有即奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差能被11整除的數(shù)能被11整除.,規(guī)律(7)的證明證：一般地有兩邊同乘 有并對(duì)n+1個(gè)式子相加得 即有7|a的充要條件是 7|對(duì)模11和13同理可證。注：這里用的是1000進(jìn)制。,例1:1234567891011…2005

14、除以3的余數(shù)是多少.,解:因?yàn)橐粋€(gè)數(shù)除以3的余數(shù),即其各位數(shù)字和除以3 的余數(shù).所以所求余數(shù) 所以余數(shù)為1.,例2：設(shè)數(shù)62XY427是99的倍數(shù)，求X，Y解：因?yàn)?9=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）,因?yàn)? X，Y 9，所以有21 21+X

15、+Y 39，4 X-Y+13 22，由此可知21+X+Y=27，X-Y+13=11或21+X+Y=36，X-Y+13=22X+Y=6，X-Y=-2，或X+Y=15，X-Y=9，解得X=2，Y=4。,例3 ：求 被7除的余數(shù)。解：∵111111被7整除，∴ ≡11（mod 7）≡4（mod 7）即余數(shù)為4。,例4：求

16、 被50除的余數(shù)解： 所以余數(shù)是29。,例5:證明: 是合數(shù).,證:因?yàn)橛烧?guī)律性,一個(gè)數(shù)被11整除的充要條件是它的奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差能被11整除.而 的奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差為0,所以能被11整除.即為合數(shù).,,§3 剩余類(lèi)及完全剩余系,若m是一個(gè)給定的正整數(shù)，由帶余數(shù)除法則對(duì)任意的整數(shù)a= qm+r則全部整數(shù)

17、可分成m個(gè)集合，k0 ,k1,…km-1, 其中 (r=0,1,2…m-1) (1) (2) (3),2 棄九法,利用相等必同余，同余未必相等，不同余肯定不相等,取模9,可判斷一些式子是否正確在出現(xiàn)9時(shí),用 可把9去掉,這就是棄九法.例:判斷28997*39495=1145236415是否正確?解:

18、若正確,則兩邊關(guān)于9同余,則有8*3 5,不成立所以錯(cuò)誤.注:棄九法只能檢查出一些錯(cuò)誤.不能檢查出所有錯(cuò)誤.看下面的例.,例判斷28997*39495=11154236415是否正確,解:兩邊關(guān)于9同余,則有8*3 6,成立此時(shí)不能判定,有可能正確,也可能錯(cuò)誤,需作進(jìn)一步判定.若正確,進(jìn)一步取模為11,則有1*5 3(mod11)不成立,所以錯(cuò)誤.,例判斷28997*39495=11145236415是否正

19、確,解:兩邊關(guān)于9同余,則有8*3 5,不成立所以錯(cuò)誤.,例判斷28997*39495=11145236415是否正確,解:兩邊關(guān)于9同余,則有8*3 5,不成立所以錯(cuò)誤.,,定義：稱(chēng)k0 ,k1,…km-1叫做模m的剩余類(lèi)，設(shè)a0,a1…am-1是m個(gè)整數(shù)，并且其中任何兩數(shù)都不在一個(gè)剩余類(lèi)里，則a0,a1…am-1叫做模m的一個(gè)完全剩余系(簡(jiǎn)稱(chēng)完系)推論：m個(gè)整數(shù)成為模的一個(gè)完全剩余系的充分與必要條件是:兩兩對(duì)模m不同余

20、。注:一組數(shù)成為模m的完系的充要條件是(1)個(gè)數(shù)=m(2)兩兩關(guān)于模m不同余,常見(jiàn)模m的完全剩余系(簡(jiǎn)稱(chēng)完系）0,1,2,…m-1做模m的最小非負(fù)完全剩余系；當(dāng)m是雙數(shù)時(shí)， 或當(dāng)是m單數(shù)時(shí)， ,叫做模m的絕對(duì)最小完全剩余系,定理1：設(shè)m是正整數(shù)，(a,m)=1,b是任意整數(shù)。若x通過(guò)模m的一個(gè)完系，則ax+

21、b也通過(guò)模m的完系，即若a0,a1…am-1是模m的完系，則aa0+b,aa1+b…aam-1+b也是模m的完系。證：首先因x通過(guò)模m的一個(gè)完系，所以ax+b有m個(gè)數(shù)，若 , 則有這與x通過(guò)m的完系矛盾，所以ax+b中任意兩個(gè)數(shù)不同余，即ax+b也通過(guò)模m的完系。,定理2：若m1,m2是互質(zhì)的兩個(gè)正整數(shù)，x1,x2分別通過(guò)模m1,m2的完全剩余系，

22、 則 通過(guò)模m1m2的完全剩余系。注:定理2給出了如何用m1,m2的完全剩余系構(gòu)造m1m2完全剩余系的方法.,,例：3的完系是1，2，3；2的完系是1，2則6的完系是2×1+ 3×1, 2×1+ 3×2,2×2+ 3×1, 2×2+ 3×2, 2×3+ 3×1,2

23、×3+ 3×2,即為5,2,1,4,3,0下面給出定理的證明.,證：首先 一共通過(guò)了 個(gè)數(shù)，下證這 個(gè)數(shù)關(guān)于模 是兩兩不同余的。設(shè) 則有 由已知m1,m2是互質(zhì)，所以有與題設(shè)矛盾.

24、所以這 個(gè)數(shù)關(guān)于模 是兩兩不同余的 即 通過(guò)模m1,m2的完系。,§4 簡(jiǎn)化剩余系與歐拉函數(shù)定義1：歐拉函數(shù)φ(a)是定義在正整數(shù)上的函數(shù)，定義為序列0,1,2,…a-1中與a互質(zhì)的數(shù)個(gè)數(shù)。約定φ(1)=1，顯然φ(p)=p-1定義2：如果一個(gè)模m的剩余類(lèi)里面的數(shù)與m互質(zhì)，就把它叫做一個(gè)與模m互質(zhì)的剩余類(lèi)。 在與模m互質(zhì)的全部剩

25、余類(lèi)中，從每一類(lèi)各任取一數(shù)所作成的元數(shù)的集合，叫做模m的一個(gè)簡(jiǎn)化剩余系（簡(jiǎn)稱(chēng)簡(jiǎn)系）。一組數(shù)是m的一個(gè)簡(jiǎn)系的條件為(1）元素個(gè)數(shù)為φ(m)(2)兩兩不同余關(guān)于模m(3)每一個(gè)元素x,有(x,m)=1,定理1 若(a,m)=1，x通過(guò)模m的簡(jiǎn)化剩余系，則ax通過(guò)模m的簡(jiǎn)化剩余系。證：ax有φ(m)個(gè)數(shù)，因(a,m)=1， (x,m)=1所以（ax，m）=1，若 ,則

26、 ，這與已知矛盾。所以ax通過(guò)模m的簡(jiǎn)化剩余系。,定理2：若m1,m2是兩個(gè)互質(zhì)的正整數(shù)， x1,x2分別通過(guò)模m1,m2的簡(jiǎn)化剩余系，則m2x1+m1x2通過(guò)模m1m2的簡(jiǎn)化剩余系。證:(1) 設(shè)x1,x2分別通過(guò)模m1,m2的完全剩余系，則m2x1+m1x2通過(guò)模m1m2的完全剩余系。(2) (m2x1+m1x2， m1m2)=1(m2x1+m1x2， m1m2)=1有(m2x1+m1x2

27、， m2)=1有(m1x2， m2)=1有(x2， m2)=1,同理有 反之也對(duì)。所以當(dāng)x1,x2分別通過(guò)模m1,m2的簡(jiǎn)化剩余系，則m2x1+m1x2通過(guò)模m1m2的簡(jiǎn)化剩余系。,推論：若m1,m2是兩個(gè)互質(zhì)的正整數(shù)，則φ(m1m2) = φ(m1 ). φ(m2)例：由定義有設(shè) 因?yàn)?= =

28、,推論1：推論2:證：所以 =m,§5 歐拉定理 費(fèi)爾馬定理（歐拉定理）設(shè)m是大于1的整數(shù)，(a,m)=1,注:歐拉定理是數(shù)論中最重要的一個(gè)定理 例:因?yàn)?7,2005)=1,所以有說(shuō)明歐拉定理的用處之大,下面給出定理的證明.,證：讓?zhuān)ㄟ^(guò)模ｍ的簡(jiǎn)系：設(shè)為r1,r2,…rΦ(m)，則ａｘ也通過(guò)ｍ的簡(jiǎn)系,為a r1,ar2,…arΦ(m) 于是有對(duì)任意的i,有j使得　　　　　　　　

29、 i=1,2… φ(m)把上面φ(m)同余式逐項(xiàng)相乘，得 即由性質(zhì)有 ,所以有,推論:若d是 成立的最小正整數(shù),且 則d|n.,證明

30、:假設(shè)結(jié)論不成立,則n=dq+r,0<r<d則有這與d的最小性矛盾.所以假設(shè)錯(cuò)誤即有d|n.,費(fèi)爾馬定理 若p是素?cái)?shù)，則證：若p|a,則 ,即 若p ?a,則(p,a)=1,由歐拉定理知 兩邊同乘a即得,例1：求3406的末二位數(shù)。解：∵ （3，100）=1，φ(100)= (22·52)=40, ∴ 340≡1(mol 100)∴340

31、6=(340)10·36≡(32)2·32≡-19×9≡- 171≡29(mod 100)∴ 末二位數(shù)為29。,例2：證明（a+b）p≡ap+bp(mod p)證：由費(fèi)爾馬小定理知對(duì)一切整數(shù)有ap≡a（p）bp≡b(P)，由同余性質(zhì)知有ap+bp≡a+b(p)又由費(fèi)爾馬小定理有（a+b）p≡a+b (p)（a+b）p≡ap+bp(p),,,例3：設(shè)素?cái)?shù)p>2，則2P-1的質(zhì)因數(shù)一定是

32、2pk+1形。證：設(shè)q是2-1的質(zhì)因數(shù)，由于2-1為奇數(shù)，∴ q≠2，∴ （2·q）=1,由條件q|2p-1,即2≡1（mod q）又∵ （q,2）=1， 2p ≡1（mod q）設(shè)i是使得2x ≡1（mod p）成立最小正整數(shù)若1<i<p，則有i|p則與p為素?cái)?shù)矛盾∴ i=p, ∴ p|q-1又∵ q-1為偶數(shù)，2|q-1,∴ 2p|q-1,q-1=2pk,即q=2pk+1,例4：證明相鄰兩個(gè)整數(shù)

33、的立方之差不能被5整除. 證明： 因?yàn)?所以只需證明 對(duì)任意的n關(guān)于5都不同余零。而我們知道模5的完全剩余系由-2,-1,0,1,2構(gòu)成,所以這只需將n=0,±1,±2對(duì)于模5代入有 ，而1，2，4 不同余0，所以有相鄰兩個(gè)整數(shù)的立方之差不能被5整

34、除.,例5:若 為素?cái)?shù),則有,證:因?yàn)?P,2)=1,(P,5)=1,所以有 (P,10)=1由歐拉定理有即即,,循環(huán)小數(shù)和分?jǐn)?shù)的互化 定義：如果對(duì)于一個(gè)無(wú)限小數(shù)0.a1a2…an…(an是0,1,2…9之中的一個(gè)數(shù)碼，并且從任何一位以后不全是0)能找到兩個(gè)整數(shù)s，t使得as+i=as+kt+i,i=1,2,…t; k=0

35、,1,2…我們就稱(chēng)它為循環(huán)小數(shù)，并簡(jiǎn)單地把它記作0.a1a2…asas+1…as+t.對(duì)于循環(huán)小數(shù)而言，具有上述性質(zhì)的s及t是不只一個(gè)的，如果找到的t是最小的，我們就稱(chēng)as+1,as+2…as+t為循環(huán)節(jié)；t稱(chēng)為循環(huán)節(jié)長(zhǎng)度；若最小的s=0,那小數(shù)就叫做純循環(huán)小數(shù)，否則叫做混循環(huán)小數(shù)。,對(duì)有理數(shù)化為小數(shù)有下面的二個(gè)定理定理2:有理數(shù)a/b,0<a<b,(a,b)=1能表成純循環(huán)小數(shù)的充分與必要條件是:(b,10)=1定理

36、3：若a/b是有理數(shù)，其中0<a<b,(a,b)=1,b=2α5βb1, (b1,10)=1, , α,β不全為零，則a/b可以表成混循環(huán)小數(shù)，其中不循環(huán)的位數(shù)是µ=max(α,β )（即α,β中之較大者）證明: 見(jiàn)書(shū)上(因?yàn)橛欣頂?shù)化為小數(shù)是比較方便的)另一方面,小數(shù)化為有理數(shù)更有實(shí)際意義,我們給出其方法,方法如下.,純循環(huán)小數(shù)和混循環(huán)小數(shù)化為分?jǐn)?shù)的方法1、純循環(huán)小數(shù)等于這樣的一個(gè)

37、分?jǐn)?shù)，將循環(huán)部分的數(shù)字作為分子，循環(huán)部分有幾個(gè)數(shù)就定幾個(gè)9用為分母構(gòu)成的分?jǐn)?shù)。2、混循環(huán)小數(shù)等于這樣的一個(gè)分?jǐn)?shù)，將非循環(huán)部分與緊接后一個(gè)循環(huán)部分看成一個(gè)整數(shù)，減去看成一個(gè)整數(shù)的非循環(huán)部分，將差作為分子，然后視循環(huán)部分有幾個(gè)數(shù)就寫(xiě)幾個(gè)9，小數(shù)點(diǎn)后非循環(huán)部分有幾個(gè)數(shù)字，便在9的后面寫(xiě)幾個(gè)0，成為一個(gè)整數(shù)作為分母。,例1：把 化為分?jǐn)?shù)。解：設(shè)b= ， 從而1000b=