初等數(shù)論同余

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

2、 同余和整除有密切關(guān)系,可相互轉(zhuǎn)化, 有下面定理.).(modmba ).(modmba 定理定理1：整數(shù)a,b對模同余的充分與必要條件是： m| a-b, 即 a=b+mt, t是整數(shù)。證明：設(shè)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 ,則 證:性質(zhì)5顯然.).(modmba ).(modmkbkak ).(modmba ).(moddmdbda)(|11badm)( |, 1),(11

3、bamdm性質(zhì)性質(zhì)6 若 則證：由已知m|a-b,又d|m,所以d|a-b性質(zhì)性質(zhì)7 d|(a,b),(d,m)=1 則證： 因為 ，(d,m)=1 ，所以有0,),(moddmdmba).(moddba ).(modmba ).(modmdbda)(|dbdadmdbdam|性質(zhì)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).性質(zhì)9 若 則證：由已知 ,即a-b是所有 的公倍數(shù)，而最小公倍數(shù)整除所有公倍數(shù)，即有).(modmba ).,

4、(mod21kmmmba,3 , 2 , 1).(modkimbai).,(mod21kmmmbakjbamj2 , 1,|jm例1：證明13|42n+1+3n+2證：42n+1+3n+2416n+93n 3n (4+9)133n0(13) 13|42n+1+3n+2注：整除問題和同余問題是相互可以轉(zhuǎn)化的把整除問題轉(zhuǎn)化為同余問題是一種常用的方法.例2：證明5y+3=x2無解證明：若5y+3=x2有解，則兩邊關(guān)于模5同余有5y+3x2(mod 5)即3x2(mod 5) 而任一個平方數(shù)x20,1,4(mod 5) 3 0,1,4(mod 5)，不可能 即得矛盾，即5y+3=x2無解注：在證明方程

5、無解時，經(jīng)常用不同余就不相等的方法。 2 同余的應(yīng)用1、算術(shù)中的整除規(guī)律(1)個位數(shù)是偶數(shù)的數(shù)能被整除；(2)個位數(shù)是或的數(shù)能被整除；(3)末兩位數(shù)能被（或）整除的數(shù)能被（或）整除；(4)末三位數(shù)能被（或）整除的數(shù)能被（或）整除；5)各位數(shù)字之和能被（或）整除的數(shù)能被（或）整除；6)奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差能被整除的數(shù)能被整除。7)設(shè)b=7（11，13），則b|a的充分必要條件是b| 注:整除規(guī)律一方面給出了整除的判定.另一方面也給出了求余數(shù)的方法.上述性質(zhì)的證明差不多,我們證明其中的(6)(7)二條作一示范.niiia0) 1(0110001000aaaann規(guī)律(6)的證明證:設(shè)

6、因為 兩邊分別乘以 然后相加有即奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差能被11整除的數(shù)能被11整除.0111010aaaannnn)11(mod) 1(10)11(mod110)11(mod110)11(mod112nnia)11(mod) 1(210aaaaann規(guī)律(7)的證明證：一般地有兩邊同乘 有并對n+1個式子相加得 即有7|a的充要條件是 7|對模11和13同理可證。注：這里用的是1000進制。)7(mod11000),7(mod110000niii, 1 , 0),7(mod) 1(1000niiiaa0)7(mod) 1(niiia0) 1(ia例1:123456789101120

7、05除以3的余數(shù)是多少.解:因為一個數(shù)除以3的余數(shù),即其各位數(shù)字和除以3 的余數(shù).所以所求余數(shù) 所以余數(shù)為1.)3(mod1500220051098765432150021101987654321例2：設(shè)數(shù)62XY427是99的倍數(shù)，求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）因為0 X，Y 9，所以有21 21+X+Y 39，4 X-Y+13 22，由此可知21+X+Y=27，X-Y+13=11或21+X+Y=36，X-Y+13=22X

8、+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。5011150111例4：求 被50除的余數(shù)解： 所以余數(shù)是29。2633)46257(26332633)47()46257(26162)4)7(7(552626)3(33)47(225)7(73)7(3)50(mod2921例5:證明: 是合數(shù).證:因為由整除規(guī)律性,一個數(shù)被11整除的充要條件是它的奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差能被11整除.而 的奇數(shù)位數(shù)字之和與偶數(shù)位數(shù)字之和的差為0,所以能被11整除.即為合數(shù). 0

9、200001100個 0200001100個3 剩余類及完全剩余系剩余類及完全剩余系 若m是一個給定的正整數(shù)，由帶余數(shù)除法則對任意的整數(shù)a= qm+r則全部整數(shù)可分成m個集合，k0 ,k1,km-1, 其中 (r=0,1,2m-1) (1) (2) (3) ,|ZxrmqxxKrrmrKZ10)(jiKKjiiKba,)(modmiba2 棄九法利用相等必同余，同余未必相等，不同余肯定不相等,取模9,可判斷一些式子是否正確在出現(xiàn)9時,用 可把9去掉,這就是棄九法.例:判斷28997*39495=1145236415是否正確?解:若正確,則兩邊關(guān)于9同余,則有8*3 5,不成立所以錯誤.注:棄九

10、法只能檢查出一些錯誤.不能檢查出所有錯誤.看下面的例.)9(mod09 例判斷28997*39495=11154236415是否正確解:兩邊關(guān)于9同余,則有8*3 6,成立此時不能判定,有可能正確,也可能錯誤,需作進一步判定.若正確,進一步取模為11,則有1*5 3(mod11)不成立,所以錯誤.例判斷28997*39495=11145236415是否正確解:兩邊關(guān)于9同余,則有8*3 5,不成立所以錯誤.例判斷28997*39495=11145236415是否正確解:兩邊關(guān)于9同余,則有8*3 5,不成立所以錯誤.定義定義：稱k0 ,k1,km-1叫做模m的剩余類，設(shè)a0,a1am-1是m個

11、整數(shù)，并且其中任何兩數(shù)都不在一個剩余類里，則a0,a1am-1叫做模m的一個完全剩余系(簡稱完系)推論推論：m個整數(shù)成為模的一個完全剩余系的充分與必要條件是:兩兩對模m不同余。注:一組數(shù)成為模m的完系的充要條件是(1)個數(shù)=m(2)兩兩關(guān)于模m不同余常見模m的完全剩余系(簡稱完系）0,1,2,m-1做模m的最小非負完全剩余系；當m是雙數(shù)時， 或當是m單數(shù)時， ,叫做模m的絕對最小完全剩余系121 , 0 , 1,2mm21 , 0 , 1, 12mm211 , 0 , 121mm定理定理1：設(shè)m是正整數(shù)，(a,m)=1,b是任意整數(shù)。若x通過模m的一個完系，則ax+b也通過模m的完系，即若a0

12、,a1am-1是模m的完系，則aa0+b,aa1+baam-1+b也是模m的完系。證：首先因x通過模m的一個完系，所以ax+b有m個數(shù)，若 , 則有這與x通過m的完系矛盾，所以ax+b中任意兩個數(shù)不同余，即ax+b也通過模m的完系。)(modmbaxbaxji)(modmxxji定理定理2：若m1,m2是互質(zhì)的兩個正整數(shù)，x1,x2分別通過模m1,m2的完全剩余系， 則 通過模m1m2的完全剩余系。注:定理2給出了如何用m1,m2的完全剩余系構(gòu)造m1m2完全剩余系的方法.2112xmxm例：3的完系是1，2，3；2的完系是1，2則6的完系是21+ 31, 21+ 32,22+ 31, 22+

13、32, 23+ 31,23+ 32,即為5,2,1,4,3,0下面給出定理的證明.證：首先 一共通過了 個數(shù)，下證這 個數(shù)關(guān)于模 是兩兩不同余的。設(shè) 則有 由已知m1,m2是互質(zhì)，所以有與題設(shè)矛盾. 所以這 個數(shù)關(guān)于模 是兩兩不同余的 即 通過模m1,m2的完系。2112xmxm21mm21mm)(mod21, ,21, ,12,21,12mmxmxmxmxm)(mod1,12,12mxmxm，)(mod2,21,21mxmxm，)(mod1, ,1,1mxx )(mod2, ,2,2mxx 21mm21mm2112xmxm21mm4 簡化剩余系與歐拉函數(shù)簡化剩余系與歐拉函數(shù)定義定義1：歐拉函

14、數(shù)(a)是定義在正整數(shù)上的函數(shù)，定義為序列0,1,2,a-1中與a互質(zhì)的數(shù)個數(shù)。約定約定(1)=1，顯然(p)=p-1定義定義2：如果一個模m的剩余類里面的數(shù)與m互質(zhì)，就把它叫做一個與模m互質(zhì)的剩余類。 在與模m互質(zhì)的全部剩余類中，從每一類各任取一數(shù)所作成的元數(shù)的集合，叫做模m的一個簡化剩余系（簡稱簡系）。一組數(shù)是m的一個簡系的條件為(1）元素個數(shù)為(m)(2)兩兩不同余關(guān)于模m(3)每一個元素x,有(x,m)=1定理定理1 若(a,m)=1，x通過模m的簡化剩余系，則ax通過模m的簡化剩余系。證：ax有(m)個數(shù)，因(a,m)=1， (x,m)=1所以（ax，m）=1，若 ,則 ，這與已知矛

15、盾。所以ax通過模m的簡化剩余系。)(mod21maxax )(mod21mxx 定理定理2：若m1,m2是兩個互質(zhì)的正整數(shù)， x1,x2分別通過模m1,m2的簡化剩余系，則m2x1+m1x2通過模m1m2的簡化剩余系。證證:(1) 設(shè)設(shè)x1,x2分別通過模m1,m2的完全剩余系，則m2x1+m1x2通過模m1m2的完全剩余系。(2) (m2x1+m1x2， m1m2)=1(m2x1+m1x2， m1m2)=1有(m2x1+m1x2， m2)=1有(m1x2， m2)=1有(x2， m2)=1,同理有 反之也對。所以當x1,x2分別通過模m1,m2的簡化剩余系，則m2x1+m1x2通過模m1m

16、2的簡化剩余系。1,(1,(2211），）mxmx1,(11）mx推論推論：若m1,m2是兩個互質(zhì)的正整數(shù)，則(m1m2) = (m1 ). (m2)例：由定義有設(shè) 因為 = =1)(pppkkpppa2121, 1),(jijipp)()()()(2121kkpppa)()(11221112211kkkkpppppp)11 ()11)(11 (21kpppa推論1：推論2:證：所以 =mppp)()() 1 (mdmd|)(iikkpppd0 ,2121kkkkmdpppd00201|)()()()(2221115 歐拉定理歐拉定理 費爾馬定理費爾馬定理（歐拉定理歐拉定理）設(shè)m是大于1的整數(shù)

17、，(a,m)=11(modm).a(m)注:歐拉定理是數(shù)論中最重要的一個定理 例:因為(7,2005)=1,所以有說明歐拉定理的用處之大,下面給出定理的證明.1(mod2005)771600(2005)證：讓通過模的簡系：設(shè)為r1,r2,r(m)，則也通過的簡系,為a r1,ar2,ar(m) 于是有對任意的i,有j使得 i=1,2 (m)把上面(m)同余式逐項相乘，得 即由性質(zhì)有 ,所以有1(modm).a(m)(modmararji)(mod)(21)(21mrrrarararmm)(mod)(21)(21)(mrrrrrrammm1),)(21mrrrm（推論:若d是 成立的最小正整數(shù),

18、且 則d|n.)(mod1mad)(mod1man證明:假設(shè)結(jié)論不成立,則n=dq+r,0r2，則2P-1的質(zhì)因數(shù)一定是2pk+1形。證：設(shè)q是2-1的質(zhì)因數(shù)，由于2-1為奇數(shù)， q2， （2q）=1,由條件q|2p-1,即21（mod q）又 （q,2）=1， 2p 1（mod q）設(shè)i是使得2x 1（mod p）成立最小正整數(shù)若1ip，則有i|p則與p為素數(shù)矛盾 i=p, p|q-1又 q-1為偶數(shù)，2|q-1, 2p|q-1,q-1=2pk,即q=2pk+1例4：證明相鄰兩個整數(shù)的立方之差不能被5整除. 證明： 因為 所以只需證明 對任意的n關(guān)于5都不同余零。而我們知道模5的完全剩余系由

19、-2,-1,0,1,2構(gòu)成,所以這只需將n=0,1,2對于模5代入有 ，而1，2，4 不同余0，所以有相鄰兩個整數(shù)的立方之差不能被5整除. 133) 1(233nnnn)5(mod4 , 2 , 11332 nn1332 nn1332 nn例5:若 為素數(shù),則有1999|pp5 , 2p證:因為(P,2)=1,(P,5)=1,所以有 (P,10)=1由歐拉定理有即即110|1pp)(mod1101pp1999|pp 循環(huán)小數(shù)和分數(shù)的互化 定義：如果對于一個無限小數(shù)0.a1a2an(an是0,1,29之中的一個數(shù)碼，并且從任何一位以后不全是0)能找到兩個整數(shù)s，t使得as+i=as+kt+i,i=1,2,t; k=0,1,2我們就稱它為循環(huán)小數(shù)，并簡單地把它記作0.a1a2asas+1as+t.對于循環(huán)小數(shù)而言，具有上述性質(zhì)的s及t是不只一個的，如果找到的t是最小的，我們就稱as