第二章同余與同余式

1、第二章第二章 同余與同余式同余與同余式 同余的概念與基本性質(zhì)同余方程組的求解方法線性同余方程、高次同余方程的求解原根和指數(shù)應(yīng)用第二章第二章 同余與同余式同余與同余式 在日常生活中,有時我們注意的常常不是某些整數(shù),而是這些整數(shù)用某一個固定的整數(shù)去除所得到的余數(shù).例如本月2日是星期3,那么9日,16日,都是星期3,這是因為它們用7除后得到的余數(shù)都是2在我國古代的干支紀(jì)年也是這樣的,它是以60作為除數(shù)的紀(jì)年法.這樣,在數(shù)學(xué)中就產(chǎn)生了同余的概念.同余概念是Gauss在1800年前后創(chuàng)立的.2.0 2.0 同余定義同余定義和基本性質(zhì)和基本性質(zhì)定義定義1 1 給定一正整數(shù)給定一正整數(shù)m, m, 若用若用m

2、m去除兩個整數(shù)去除兩個整數(shù)a a和和b b所得所得余數(shù)相同余數(shù)相同, , 則稱則稱a a與與b b為對模為對模mm同余同余, , 記作記作a a b(mod m); b(mod m); 若余數(shù)不同若余數(shù)不同, , 則稱則稱 a a與與b b為對模為對模mm不同余。不同余。a a b(mod m) iff m|(a-b).b(mod m) iff m|(a-b).a a 0(mod0(mod m) iff m| a. m) iff m| a.性質(zhì)性質(zhì): : 自反性自反性: : a a a (mod m).a (mod m). 對稱性對稱性: : 若若a a b(mod m), b(mod m),

3、 則則 b b a(mod m).a(mod m). 傳遞性傳遞性: : 若若a a b(mod m), bb(mod m), b c(mod m), c(mod m), 則則: : a a c(mod m).c(mod m).可見可見, , 同余關(guān)系是等價關(guān)系同余關(guān)系是等價關(guān)系. .2.0同余式定義和基本性質(zhì)定理定理1 1 若若a a b(mod m), cb(mod m), c d(mod m), d(mod m), 則則: : ax+cy ax+cy bx+dy(mod m), bx+dy(mod m), 其中其中x x和和y y為任給整數(shù)為任給整數(shù). . ac ac bd(mod m)

4、. bd(mod m). 1) 設(shè)設(shè)a b (modm), c是任意整數(shù)是任意整數(shù).則則 ac bc(modm). 2) 2) 設(shè)設(shè)ai bi (modm)(i =1,2,n, n2),n, n2),則則 a1a2an b1b2bn (modm). a an n b bn n(mod m), (mod m), 其中其中 n n0.0. f(a) f(a) f(b)(mod f(b)(mod m), m), 其中其中f(x)f(x)為任意的一個整系數(shù)多為任意的一個整系數(shù)多項式項式. .同余在算術(shù)里的兩個應(yīng)用：同余在算術(shù)里的兩個應(yīng)用：應(yīng)用應(yīng)用11檢查因數(shù)的一些方法檢查因數(shù)的一些方法 一整數(shù)能被一整

5、數(shù)能被3(9)3(9)整除整除 iff iff 它的十進(jìn)位數(shù)碼的和能被它的十進(jìn)位數(shù)碼的和能被 3(9) 3(9)整除整除. .正整數(shù)正整數(shù)a=a=an1000n+an-11000n-1+ +a0 , 0ai3是一奇素數(shù), S=2, 3, , p-2，aS. 因為(a,p)=1, 存在整數(shù)m和n, 使am+pn=1, 于是am1(mod p). 設(shè)b=m-pq, 即b是p除m的余數(shù), 易知 b1, bp-1, 故 bS, 且 ab1(mod p). 可以證明 ab.定理定理 ( (威爾遜定理威爾遜定理) ) p p為素數(shù)為素數(shù) iffiff (p-l)! (p-l)! -1(mod p).-1(

6、mod p). 假設(shè) a=b, 則有(b-1)(b+1)0(mod p), 而 bl, b p-1, 故(b-1)(b+1)0(mod p)不成立. 可見S中的數(shù)可分成(p-3)/2對, 每一對數(shù)a和b, 滿足 abl(mod p), 故得23(p-2) (mod p), 即可得(p-1)! -1 (mod p).定理定理 ( (威爾遜定理威爾遜定理) ) p p為素數(shù)為素數(shù) iffiff (p-l)! (p-l)! -1(mod p).-1(mod p).充分性充分性: 若(p-1)! = -l (mod p), 則 p為素數(shù). 假設(shè)p是合數(shù), 令 pab, ap. 由題設(shè)條件知, p|(p

7、-1)!+l). 又因 a|p, 則有 a|(p-1)!+1). 但由于 ap-1可得 a|(p-1)!, 從而 a|(p-1)!+1)-(p-1)!), 即a|l, 因而p只有因子1和p, 即p為素數(shù).同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余的應(yīng)用同余的應(yīng)用1：國際圖書標(biāo)準(zhǔn)：國際圖書標(biāo)準(zhǔn)(ISBN編碼編碼) ISBN是是international standard of book number 的縮寫，即國的縮寫，即國際標(biāo)準(zhǔn)圖書編號。際標(biāo)準(zhǔn)圖書編號。ISBN是國際通用的圖書或獨(dú)立的出版物是國際通用的圖書或獨(dú)立的出版物(除定期出版除定期出版的期刊的期刊)代碼。出版社可以

8、通過代碼。出版社可以通過ISBN清晰地辨認(rèn)所有非期刊書籍。一個清晰地辨認(rèn)所有非期刊書籍。一個ISBN只有一個或一份相應(yīng)的出版物與之對應(yīng)。新版本如果在原來舊版只有一個或一份相應(yīng)的出版物與之對應(yīng)。新版本如果在原來舊版的基礎(chǔ)上沒有內(nèi)容上太大的變動，在出版時也不會得到新的的基礎(chǔ)上沒有內(nèi)容上太大的變動，在出版時也不會得到新的ISBN號碼。號碼。當(dāng)平裝本改為精裝本出版時，原來相應(yīng)的當(dāng)平裝本改為精裝本出版時，原來相應(yīng)的ISBN號碼也應(yīng)當(dāng)收回。號碼也應(yīng)當(dāng)收回。 國際標(biāo)準(zhǔn)圖書編號問世后，很快得到推廣，主要是因為它對出版國際標(biāo)準(zhǔn)圖書編號問世后，很快得到推廣，主要是因為它對出版商、書商的工作有很大的益處，體現(xiàn)在商、

9、書商的工作有很大的益處，體現(xiàn)在:國際標(biāo)準(zhǔn)書號是機(jī)讀的編碼，國際標(biāo)準(zhǔn)書號是機(jī)讀的編碼，從圖書的生產(chǎn)到發(fā)行、銷售始終如一，對圖書的發(fā)行系統(tǒng)起了很大的從圖書的生產(chǎn)到發(fā)行、銷售始終如一，對圖書的發(fā)行系統(tǒng)起了很大的作用作用;它的引入使圖書的定購、庫存控制、賬目和輸出過程等任何圖書它的引入使圖書的定購、庫存控制、賬目和輸出過程等任何圖書業(yè)的分支程序都簡化了業(yè)的分支程序都簡化了;國際標(biāo)準(zhǔn)書號也對圖書館和文獻(xiàn)中心的訂購、國際標(biāo)準(zhǔn)書號也對圖書館和文獻(xiàn)中心的訂購、采選、編目和流通程序都有促進(jìn)作用采選、編目和流通程序都有促進(jìn)作用;ISBN系統(tǒng)的引入也服務(wù)于書目信系統(tǒng)的引入也服務(wù)于書目信息的流動和使用，而且為一個國家

10、的圖書生產(chǎn)提供經(jīng)濟(jì)的書目控息的流動和使用，而且為一個國家的圖書生產(chǎn)提供經(jīng)濟(jì)的書目控制制;ISBN對圖書市場更有效率，它能確定國際上出版的任何圖書及其出對圖書市場更有效率，它能確定國際上出版的任何圖書及其出版社。在書業(yè)中習(xí)慣稱版社。在書業(yè)中習(xí)慣稱ISBN為庫藏碼為庫藏碼(Stock Number)，就是因為其被，就是因為其被普遍應(yīng)用于書庫管理。普遍應(yīng)用于書庫管理。同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用10位數(shù)位數(shù)ISBN的結(jié)構(gòu)的結(jié)構(gòu)現(xiàn)行的現(xiàn)行的ISBN由由10位數(shù)字組成，這位數(shù)字組成，這10位數(shù)字由位數(shù)字由4組數(shù)字組成，中間用組數(shù)字組成，中間用“-”相連，每組數(shù)字都有不同的

11、含義。相連，每組數(shù)字都有不同的含義。第一組號碼是地區(qū)號，又叫組號，最短的只有一位數(shù)字，最長的達(dá)五位數(shù)第一組號碼是地區(qū)號，又叫組號，最短的只有一位數(shù)字，最長的達(dá)五位數(shù)字，大體上兼顧文種、國別和地區(qū)。字，大體上兼顧文種、國別和地區(qū)。0、1代表英語，使用這兩個代碼的國代表英語，使用這兩個代碼的國家有家有:澳大利亞、加拿大、愛爾蘭、新西蘭、波多黎各、南非、英國、美澳大利亞、加拿大、愛爾蘭、新西蘭、波多黎各、南非、英國、美國、津巴布韋等國、津巴布韋等;2代表法語，法國、盧森堡以及比利時、加拿大和瑞士的代表法語，法國、盧森堡以及比利時、加拿大和瑞士的法語區(qū)使用該代碼法語區(qū)使用該代碼;3代表德語，德國、奧地

12、利和瑞士德語區(qū)使用該代碼代表德語，德國、奧地利和瑞士德語區(qū)使用該代碼;4是日本出版物的代碼是日本出版物的代碼;5是俄羅斯出版物的代碼是俄羅斯出版物的代碼;7是中國出版物使用的代碼。是中國出版物使用的代碼。第二組第二組: 出版社代碼。由國家或地區(qū)的出版社代碼。由國家或地區(qū)的ISBN中心設(shè)置并分給各個出版社。中心設(shè)置并分給各個出版社。第三組第三組:書序碼。該出版物代碼，是出版者分配給每一個出版物的編號。書序碼。該出版物代碼，是出版者分配給每一個出版物的編號。第四組第四組:計算機(jī)校驗碼。校驗碼是計算機(jī)校驗碼。校驗碼是ISBN號的最后一位數(shù)值，它能夠校驗出號的最后一位數(shù)值，它能夠校驗出ISBN號是否正

13、確。校驗碼只能是號是否正確。校驗碼只能是1位數(shù)，當(dāng)為位數(shù)，當(dāng)為10時，記為羅馬數(shù)字時，記為羅馬數(shù)字X。同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用左圖是左圖是2007實行的新的實行的新的ISBN標(biāo)準(zhǔn)，從標(biāo)準(zhǔn)，從10位升到位升到13位，為了講課方便，我們?nèi)匀晃?，為了講課方便，我們?nèi)匀挥糜?007年以前的年以前的10位標(biāo)準(zhǔn)來講述：位標(biāo)準(zhǔn)來講述：12912910ISBNx ,x ,x ,x +2x9xx (mod11)4,假設(shè)號已經(jīng)選擇前9位則這最后一位校驗位為：1比如：有一本書的前9位為0-619-06213,則其校驗位由以下確定：(1 0+2 6+3 1+4 9+5 0+6 6+

14、7 2+8 1+9 3)(mod11)=136(mod11)(mod11)故該書的校驗碼為4同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用12101210kkiiiiii1234567891012i-1ii 191012iISBNx xxy yyyxkiyxx yxya0a101y2y3y4y5y6y7y8y9y10y1x2x(i1)xiy(i1)x9x10 x1x2x(i1)x定理：通過校驗位可以發(fā)現(xiàn)的單一錯誤。證明：假設(shè)變成，其中（）,。不妨設(shè)，必存在整數(shù)使得。其中。因此-1ii 191010ii 110ii 1123456789101234567891010ixi(-a)(

15、i1)x9x10 xixi(-a)i(-a)mod(11)ix0mod(11)1x2x3x4x5x6x7x8x9xxmod(11)1x2x3x4x5x6x7x8x9x10 x11xmod(11)0mod(1注意到此時，這是因為則必有101210ii 112101)y yyISBNiy0mod(11)i(-a)0mod(11)11 ia1i10 0a10,y yyISBN如果是正確的號，則，由此。則，但是，不可能，故不是正確的號同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用1ij101ji10 xxxxxxxx類似的可以證明如下的定理：定理：通過校驗位可以發(fā)現(xiàn)不等位互換的錯誤。即是

16、形如變成的錯誤。同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余的應(yīng)用同余的應(yīng)用2：驗證信用卡的有效性：驗證信用卡的有效性首先注意到不同的信用卡的標(biāo)識碼的長度和前綴都不一樣，本節(jié)只介首先注意到不同的信用卡的標(biāo)識碼的長度和前綴都不一樣，本節(jié)只介紹國際上比較流行的紹國際上比較流行的Master卡，該卡標(biāo)識碼為卡，該卡標(biāo)識碼為16位，以位，以51，52，53，54或者或者55開頭開頭.比如：比如：5548 3742 7983 0696在在Master卡中，具備如下性質(zhì)：卡中，具備如下性質(zhì)：1.如果第如果第2位為位為1，則第，則第2到到3位表示銀行號。位表示銀行號。2.如果第如果第2位

17、為位為2，則第，則第2到到4位表示銀行號。位表示銀行號。3.如果第如果第2位為位為3，則第，則第2到到5位表示銀行號。位表示銀行號。4.如果第如果第2位為其他值，則第位為其他值，則第2到到6位表示銀行號。位表示銀行號。銀行號后面直到第銀行號后面直到第15位為持卡人賬號，最后一位為校驗位。比如剛才位為持卡人賬號，最后一位為校驗位。比如剛才的例子中，第的例子中，第2位為位為5，則銀行號為，則銀行號為54837，持卡人賬號為，持卡人賬號為427983069同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用1 216Ma aaMSasteraster卡的標(biāo)識碼，確定卡的校驗位，使用以下算法：

18、1.從右邊第2位往左，將每隔一位乘以22.將第1步中的積各位相加。3.將第1步?jīng)]有乘以2的各位相加4.將第2步和第3步的結(jié)果相加5.如果第4步得到的結(jié)果為S，則如果0（mod10），則該卡有效，否則無效同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用:55461997 23355004mod例 假設(shè)信用卡的標(biāo)志碼為，檢查該卡的有效性。解：1.0 2=0 5 2=10 3 2=6 2 2=4 9 2=18 1 2=2 4 2=8 5 2=102.0+1+6+4+9+2+8+1=313.5+6+9+7+3+5+0+4=394.31+39=705.700（10）所以這張卡的標(biāo)志碼有效。2

19、.1 2.1 一次同余式組一次同余式組本節(jié)介紹一次同余式組的解法及其應(yīng)用舉例在公元三世紀(jì)前,孫子算經(jīng)里已提出了下面的同余式組xb1(mod m1), xb2(mod m2), xbk(mod mk) (1)這種形式的問題, 并且很好地解決了它.孫子算經(jīng)里所提出的問題之一如下:“今有物不知其數(shù), 三三數(shù)之剩二, 五五數(shù)之剩三, 七七數(shù)之剩二. 問物幾何？” “答日二十三.”15:51:432.1 2.1 一次同余式組一次同余式組把這個問題的提法用同余式的式子來表達(dá)，它可表示成解同余式組x2(mod 3), x3(mod 5), x2(mod 7)其中x是所求物數(shù).關(guān)于同余式組:xa(mod 3)

20、, xb(mod 5), xb(mod 7) 的一般解為:x 70a+21b+15c (mod 105)15:51:432.1 一次同余式組這個解法, 在明朝程大位的算法統(tǒng)宗(1593)里有下面一首詩歌:三人同行七十稀，三人同行七十稀，五樹梅花甘一枝，五樹梅花甘一枝，七子團(tuán)圓整半月，七子團(tuán)圓整半月，除百零五便得知。除百零五便得知。關(guān)于解同余式組的問題, 在我國古代有極光輝的研究成果. 我國古代數(shù)學(xué)家孫子發(fā)明了下面的中外馳名的定理, 在國外譽(yù)為中國剩余定理, 在國內(nèi)稱為孫子定理.15:51:432.1 一次同余式組定理定理1 1 一次同余式組一次同余式組x x b b1 1(mod m(mod

21、m1 1), x), x b b2 2(mod m(mod m2 2) (1) (1)有解有解 iff (miff (m1 1,m,m2 2)|(b)|(b1 1-b-b2 2), ), 且當(dāng)且當(dāng)(1)(1)有解時對模有解時對模 mm1 1,m,m2 2 有唯一解有唯一解. .證明：證明： 設(shè)(1)有解x0, (m1,m2)=d, 則有:x0b1(mod m1), x0b2(mod m2)m1=dq1, m2=dq2 于是, x0-b1=dq1m1, x0-b2=dq2m2, 因此, d|(b1- b2). 若(m1,m2)|(b1-b2),則因xb1(mod m1)可表示為: x=b1+m1

22、y, 代入xb2(mod m2)得: m1y(b2-b1)(mod m2) (2) 因為(m1,m2)=d, d|(b2-b1), (2)有解, 設(shè)為y0, 且對模m2/d有唯一解:yy0(mod (m2/d),15:51:432.1 一次同余式組證明證明( (續(xù)續(xù)) )：即 y=y0+km2/d, k=0,1, 2, . 因此(1)的全部解為: x=b1+m1y0+m1m2k/d, k=0,1, 2, . 這些解對模m1,m2是同余的, 故(1)的解對模m1,m2唯一.定理定理1 一次同余式組一次同余式組x b1(mod m1), x b2(mod m2) (1)有解有解 iff (m1,m

23、2)|(b1-b2), 且當(dāng)且當(dāng)(1)有解時對模有解時對模m1,m2有唯一解有唯一解.15:51:432.1 2.1 一次同余式組一次同余式組對于一次同余式組對于一次同余式組: : x x b b1 1(mod m(mod m1 1), x), x b b2 2(mod m(mod m2 2), ), x x b bk k(mod m(mod mk k), k), k3 3的情形的情形, , 可先解前兩個得可先解前兩個得x x b b1 1(modm(modm1 1, ,mm2 2) ), , 再與再與x x b b3 3(mod m(mod m3 3) )聯(lián)立解出聯(lián)立解出x x b b3 3

24、(modm(modm1 1, ,mm2 2, ,mm3 3) ). . 如此繼續(xù)如此繼續(xù)下去下去, , 最后可得唯一解最后可得唯一解x x b bk k(modm(modm1 1, ,mm2 2 ,mmk k) ). . 注注 若中間有一步出現(xiàn)無解若中間有一步出現(xiàn)無解, , 則同余式組無解則同余式組無解. .15:51:432.1 一次同余式組定理定理2 (2 (孫子定理孫子定理) )設(shè)設(shè)mm1 1, m, m2 2, , , , mmk k是兩兩互素的是兩兩互素的k k個正整數(shù)個正整數(shù), , k k=2, =2, 并且并且mm m m1 1 m m2 2 mmk k , m= , m=mmi

25、 iMMi i, 1ik, , 1ik, 則同余則同余式組式組(1)(1)有唯一解有唯一解x x b b1 1MM1 1MM1 1+b+b2 2MM2 2MM2 2+b bk kMMk kMMk k(mod m)(2)(mod m)(2)其中其中MMi iMMi i 1(mod m1(mod mi i), 1ik.), 1ik.證明證明: : (mi,mj)=1, ij, 即得(Mi,mi)=1. 對每一Mi, 存在Mi, 使得MiMi 1(mod mmi i) (3)另一方面, 當(dāng)ij時, 則由(mi,mj)=1和mmjMj得到mi|Mj, 所以有:bjMjMj 0(mod mi) (4)1

26、5:51:432.1 一次同余式組由(3)和(4)有即(2)是(1)的解.若y也是(1)的解, 則得:xy(mod mi), 1ik于是, mi|(x-y), 1ik. 由于ml, m2, ,mk兩兩互素. 故m|(x-y), 即xy(mod m). 因此是(1)的唯一解.kimbMMbMMbiiiiikjjjj1),(mod1)(mod1mMMbxkjjjj15:51:432.1 一次同余式組應(yīng)用孫子定理可以證明如下定理.定理定理 3 3 設(shè)設(shè)mm1 1,m,m2 2,m,mk k是兩兩互素的是兩兩互素的 k k個正整數(shù)個正整數(shù), , mmmm1 1mm2 2mmk k , ,則同余式則同余

27、式: :f(x)f(x) 0 (mod m) (1)0 (mod m) (1) 有解有解 iff iff 同余式組同余式組: :f(x)f(x) 0 (mod m0 (mod mi i), 1ik (2), 1ik (2) 的每個同余式有解的每個同余式有解, , 且若用且若用S S表示表示(1)(1)的解數(shù)的解數(shù), , S Si i表示表示(2)(2)的解的解數(shù)數(shù), , 則則: : S SS S1 1S S2 2SSk k. .15:51:432.1一次同余式組證明證明: : 若x0是滿足(1)的整數(shù), 則由f(x0)0(mod m), 可得f(x0)0(mod mi), 1ik. 反之, 若

28、xi滿足(2), 1ik, 因為1ijk, (mi,mj)=1, 由孫子定理, 有唯一的x0, 0 x0m, 滿足x0 xi(mod mi), 1ik, 且f(x0) f(xi)0(mod mi), 1ik. 故f(x0)0(mod m).充要條件得證。 現(xiàn)在設(shè)(2)有Si個不同解是xaiji(mod mi), 0aiji mi, 1ik 1ik , ljiSi, 對其中任一組a1ji, a2ji, akji, 由孫子定理可得唯一的x, 0 xm, 是(1)的解, 且不同的組, 得到(1)的解也不同, 故SS1S2Sk.15:51:43例例1 1 韓信點(diǎn)兵:有兵一隊, 若列成五行縱隊, 則末行

29、一人; 成六行縱隊, 則末行五人; 成七行縱隊,則末行四人; 成十一行縱隊,則末行十人, 求兵數(shù).解：解： 設(shè)x是所求兵數(shù), 則依題意:x1(mod 5), x 5(mod 6)x4(mod 7), x 10(mod 11) 令m1=5,m2=6,m3=7,m4=11,b1=l, b2=5, b3=4, b4=10. 于是m=m1m2m3m4=567 11=2310, M1=2310/5=462, M2=385, M3=330, M4=210. 有M1M11(mod 5), 即1462 M1 2M1(mod 5) ,因此M1=3. 同理可求M2=1, M3=1, M4=1. 故解為:x 134

30、62+15385+14330 + 110210 6731 2111(mod 2310). 即 x=2111+2310k, k=0,1,2,.2.2 2.2 剩余類和剩余系剩余類和剩余系由于同余關(guān)系是等價關(guān)系, 因此對于給定的任一工整數(shù)m, 利用模m同余這個關(guān)系, 可將整數(shù)集劃分成m個等價類, 由于它是一些整數(shù)除m后的余數(shù)形成的, 所以稱它是剩余類或同余類.于是有:定義定義1 1 設(shè)設(shè)mm是一給定的正整數(shù)是一給定的正整數(shù), , 若若 r = i: ir = i: i r(mod m), ir(mod m), i Z, 0rm-1Z, 0rm-1 則稱則稱 r r是是模模mm剩余類剩余類. .設(shè)a

31、是任一整數(shù), 則amq+r, 0rm, 故a恰包含在r中. 若a和b是兩整數(shù), 且在r中, 則amq1+r, b=mq2+r, 故m|(a-b). 反之, m|(a-b), 則由同余定義即知a和b同在某一類r中, 0rm.2.2 2.2 剩余類和剩余系剩余類和剩余系定義定義2 2 在模在模mm剩余類剩余類0, 1, 0, 1, ,m-1,m-1中各取一數(shù)中各取一數(shù)a ar r r, 0rm-1, r, 0rm-1, 該該mm個數(shù)個數(shù)a a0 0,a,a1 1,a,am-1m-1稱為模稱為模mm的一的一完全剩余系完全剩余系. . 若令若令x=ax=a0 0,a,a1 1,a,am-1m-1, ,

32、 則稱則稱x x是過模是過模mm的的完全剩余系完全剩余系. .由此定義得以下定理.定理定理1 1 m m個整數(shù)構(gòu)成模個整數(shù)構(gòu)成模mm的一完全剩余系的一完全剩余系 iff iff 兩兩兩兩對模對模 mm不同余不同余最常用的完全剩余系0,1,2,m-1, 稱為模m的非負(fù)最小完全剩余系1,2 ,m, 稱為模m的最小完全正剩余系2.2 2.2 剩余類和剩余系剩余類和剩余系定理定理2 2 設(shè)設(shè)a a0 0,a,a1 1,a,am-1m-1是模是模mm的一完全剩余系的一完全剩余系, , b b是一整數(shù)是一整數(shù), , 則則a a0 0+b,a+b,a1 1+b, ,a+b, ,am-1m-1+ +b b也是

33、模也是模mm的一完全剩余系的一完全剩余系. .證明：證明： 假設(shè)(ai+b)(aj+b)(mod m), 0i2, an2, a1 1b b1 1,a,a2 2b b2 2,a,an nb bn n 則不是模則不是模n n的一完全剩余的一完全剩余系系. .證明證明 讀者可參見有關(guān)書籍的證明2.2 剩余類和剩余系下面介紹歐拉函數(shù)與簡化剩余系定義定義3 3 小于或等于小于或等于mm且與且與mm互素的正整數(shù)個數(shù)，記為中互素的正整數(shù)個數(shù)，記為中 ( (m), m), 稱為稱為歐拉歐拉( (Euler)Euler)函數(shù)函數(shù). .由定義知, (1)=1, (2)=1, , (3)=2, (4)=2, (5

34、)=4, (6)=2, (7)=6, (8)=4, (9)=6,.當(dāng)p是素數(shù)時, ( (p p)=p-1.)=p-1.2.2 剩余類和剩余系定理定理7 7 設(shè)設(shè)p p是一素數(shù)是一素數(shù), , k k是一正整數(shù)是一正整數(shù), , 則則: : ( (p pk k)=p)=pk-1k-1(p-1)(p-1)證明證明 因為小于或等于pk且與pk不互素的正整數(shù)恰是p的各個倍數(shù):1p,2p,3p,(pk-1)p顯然共有pk-1個. 而小于或等于pk的正整數(shù)總共有pk個, 于是: (pk)= pk pk-1= pk-1 (p-1).2.2 剩余類和剩余系定義定義4 4 若模若模mm剩余類中的數(shù)與剩余類中的數(shù)與m

35、m互素互素, , 則稱它為與模則稱它為與模mm互素互素的剩余類的剩余類, , 在與模在與模mm互素的所有剩余類中互素的所有剩余類中, , 各取一數(shù)所組成各取一數(shù)所組成的集合的集合, , 稱為模稱為模mm的一個的一個簡化剩余系（縮系）簡化剩余系（縮系）. .由上面定義, 顯然有下面二定理:定理定理8 8 模模mm簡化剩余系含有中簡化剩余系含有中 ( (m)m)個數(shù)個數(shù). .定理定理9 9 若若a a1 1,a,a2 2,a,a (m)(m)是中是中 (m)(m)個與個與mm互素的整數(shù)互素的整數(shù), , a a1 1,a,a2 2,a,a (m)(m)是模是模mm的一簡化剩余系的一簡化剩余系 iff

36、 iff 它們兩兩對模它們兩兩對模mm不同余不同余. .2.2 剩余類和剩余系定理定理 10 10 若若( (a,m)=1, ra,m)=1, rl l,r ,r2 2,r,r (m)(m)是模是模 mm的一簡化剩余系的一簡化剩余系, , 則則ararl l,ar,ar2 2,ar,ar (m)(m)也是模也是模mm的一簡化剩余系的一簡化剩余系. .證明：證明： 只需證明arl,ar2,ar(m) 互不同余,且都與m互素即可. 假設(shè)ariarj(mod m), 其中1i, j (m). 由于(a,m)=1, 故有rirj(mod m), 這與rl,r2,r(m)是模 m的一簡化剩余系矛盾, 故

37、ariarj(mod m), 即: arl,ar2,ar(m)兩兩互不同余. 假設(shè)p是m和某ari的公共素因數(shù), 其中1i(m), 因p是素數(shù), 故p|a或p|ri. 因此, p是a和m的公因數(shù), 或是ri和m的公因數(shù), 這與(a,m)=(ri,m)=l矛盾, (ari,m)=l, li(m) .即ari與m互素.2.2 剩余類和剩余系定理定理11 11 ( (歐拉定理歐拉定理) )設(shè)設(shè)mm2, 2, 且且( (a,m)=1,a,m)=1,則則: :a a (m)(m) 1(mod m).1(mod m).證明證明: : 設(shè)rl,r2,r(m)是模m的一簡化剩余系, 則由定理10知, rl,r

38、2,r(m)也是模m的一簡化剩余系. 故 (arl)(ar2)(ar(m)rlr2r(m) (mod m). 即 a(m) rlr2r(m) rlr2r(m) (mod m). 由于(ri,m)=1, 10, ai是整數(shù), 0in, 則f(x)0(mod m) (1)稱為模 m同余式. 若 an0(mod m), 稱n是(1)的次數(shù). 若 x0滿足 f(x)0(mod m), 則 xx0(mod m)稱為(1)的解. 注注：不同解是指互不同余的解.niiixaxf0)(2.4 一次同余式注意, 若x0是(1)的解, 則模m的剩余類x0, 即全部整數(shù)x0+km, k=0, 1, 2,中每一個都是

39、滿足(1), 而x0是x0非負(fù)最小整數(shù), 即是非負(fù)最小剩余.由定義可知, 要求(1)的解, 只要逐個把0,1, 2, ,(m-1)代人(1)中進(jìn)行驗算即可.但當(dāng)m大時, 計算量往往太大.下面就來討論一元一次同余式的解的問題.2.4 一次同余式定理定理 1111 設(shè)設(shè)( (a,m)=1, m0, a,m)=1, m0, 則則axax b(mod m) (2)b(mod m) (2) 恰有一解恰有一解, , 且且 x x baba (m)-1(m)-1(mod m)(mod m)證明證明 因為0,1,m-1是模m的一完全剩余系, (a,m)=1, 故0,a,2a,(m-1)a也是模m的一完全剩余系

40、, 所以其中恰有一整數(shù), 設(shè)為ka, 滿足ka b(mod m), 即k滿足(2)，因而xk(mod m)是(2)的唯一解.由歐拉定理，立即可得xba (m)-1(mod m).2.4 一次同余式定理定理2 2 設(shè)設(shè)( (a,m)=d, m0, a,m)=d, m0, 則則axax b(mod m) (3)b(mod m) (3) 有解有解 iff d|biff d|b證明證明 若(3)有解, 則由d|a, d|m, 推出d|b. 若d|b,則因(a/d,m/d)=1. 故由定理 1知: (a/d)x (b/d)(mod (m/d)有解, 即(3)有解.2.4 一次同余式定理定理 3 3 設(shè)設(shè)

41、( (a,m)=d,m0,d|b,a,m)=d,m0,d|b,則則axax b(mod m) (4)b(mod m) (4) 恰有恰有d d個解個解. .證明證明 由d|b和定理2知(4)有解.顯然, c為(4)的解 iff c也是:(a/d)x (b/d)(mod (m/d) (5) 的解. 令c滿足(5), 則(5)有唯一解:x c(mod (m/d), 即整數(shù)c+k(m/d), k=0, 1, 2,.對于模m來說,恰可選出d個互不同余的整數(shù):c, c+m/d, c+2m/d, c+(d-1)m/d定理定理 3 3 設(shè)設(shè)( (a,ma,m)=)=d,md,m0,d|b,0,d|b,則則 a

42、xax b b(mod m) (4)(mod m) (4) 恰有恰有d d個解個解. .證明證明( (續(xù)續(xù)) )： 這是因為對c+km/d, 令k=qd+r, 0rd, 代入c+km/d=c+(qd+r)m/dc+rm/d(mod m). 又若0ed, 0f0, n0, a an n 0(0(mod p), mod p), 則同余式則同余式f(x)f(x) 0(mod p) (1)0(mod p) (1) 最多有最多有n n個解個解證明證明 對n進(jìn)行歸納. 當(dāng)n=1時, 設(shè)一次同余式為a1x+a0 ( (mod p), p不能整除a1; 由于p不能整除a1; 故恰有一解. 現(xiàn)在, 假設(shè)定理對次

43、數(shù)為n-1(n2)的同余式真, 欲證(1)最多有n個解.當(dāng)np時結(jié)論顯然成立, 故可設(shè)np-1. 用反證法, 假設(shè)同余式(1)有n+1個解: x0,x1,xn, xixj(模)(mod p), 0ijn, 這將導(dǎo)致矛盾.niiixa1因為其中g(shù)(x)是首項系數(shù)為an的n-1次整數(shù)多項式,因此有但若k0, xk-x00(mod p), 故n-1次同余式g(x)0(mod p)有n個解, 與歸納假設(shè)矛盾.nkkkkxgxxxxaxfxf1000)()()()()()(mod0)()()()(00pxgxxxfxfkkk2.5 高次同余方程應(yīng)用拉格朗日定理可得下面定理.定理定理2 2 設(shè)同余式設(shè)同余

44、式 的解的個數(shù)大于的解的個數(shù)大于 n, n, 其中其中p p是素數(shù)是素數(shù), , a ak k是整數(shù)是整數(shù),0,0kn, kn, 則則p|ap|ak k. .證明：證明： 若某些系數(shù)不被p整除, 令其最大下標(biāo)為k, 則k n. k次同余式: 的解的個數(shù)大于k, 這與定理5矛盾.)(mod0)(0pxaxfnkkk)(mod00pxankkk2.5 高次同余方程定理定理3 3 對于任給素數(shù)對于任給素數(shù)p, p, 多項式多項式f(x)=(x-1)(x-2)f(x)=(x-1)(x-2)(x-p+1)-xx-p+1)-xp-1p-1+1+1的的所有系數(shù)被所有系數(shù)被p p整除整除. .證明證明 令g(x

45、)=(x-1)(x-2)(x-p+1), 則1,2,p-1是同余式g(x)=0(mod p)的p-1個解. 由費(fèi)馬定理知, 1,2,p-1也是同余式 h(x)=xp-1-10(mod p)的p-1個解. 故同余式f(x)=g(x)-h(x)(mod p)有p-1個解, 而f(x)是p-2次多項式, 由定理6知, 其所有系數(shù)被p整除.注意注意: : 本定理中f(0)=(-1)p-1(p-1)!+1, 而所有系數(shù)均被p整除, 故f(x)=(-1)p-1(p-1)!+10(mod p), 即有(p-1)! -1(mod p). 這又一次證明了威爾遜定理.2.5 高次同余方程下面對模 的同余方程做進(jìn)一

46、步討論。 容易看出，若 是同余方程 f(x) 0 (mod ) (1) 的解，則它必是方程 f(x) 0 (mod ) (2) 的解，因此，必有與 相應(yīng)的方程(2)的某個解 ，使 此處， 是某個適當(dāng)?shù)恼麛?shù)。這提示我們：可以從方程(2)的解中去求方程(1)的解。于是，現(xiàn)在的問題是，對于方程(2)的每個解 ，是否必有方程(1)的解 與之對應(yīng)？若有，如何去確定它？p0 xp1p0 x1x0110110),(modtpxxpxx0t1x0 x2.5 高次同余方程2.5 高次同余方程2.5 高次同余方程2.5 高次同余方程2.5 高次同余方程2.6 原根本節(jié)圍繞的是解高指數(shù)方程 xk a (mod m)

47、 主要利用的是歐拉定理 歐拉定理的不足： 26 1 (mod 7) 同時23 1 (mod 7) )(mod1)(mam2.6.1 指數(shù)與原根 對xk 1 (mod m) ，肯定有解，但最小解？定義定義1 1 設(shè) ,m 1,(a, m) = 1，則使 a d 1 (mod m) (1)成立的最小的正整數(shù)d，稱為a對模m的指數(shù)指數(shù)，記為ordm(a)，在不致誤會的情況下，簡記為ord(a)。指數(shù)也稱為階階。Zma,2.6.1 指數(shù)與原根例如： ordm(1)=1, ord2(-1)=1, ordm(-1)=2(m2), ord17(3)=16注意：如果（a,m）1，則規(guī)定ordm(a)=0在談到

48、a對模m的指數(shù)時，總假定m1，(a, m) = 1。 有的使用ordm (a)等同的符號是 m(a)， (a)，但ordm (a)更常用2.6.1 指數(shù)與原根模7的指數(shù)表 11 1(mod 7) 23 1(mod 7) 36 1(mod 7) 43 1(mod 7) 56 1(mod 7) 62 1(mod 7)觀察： 2與4的指數(shù)同，3與5的指數(shù)同 所有的指數(shù)都是6的因數(shù)a123456ord7(a)1363622.6.1 指數(shù)與原根模10的指數(shù)表 11 1(mod 10) 34 1(mod 10) 74 1(mod 10) 92 1(mod 10) 觀察： 3與7的指數(shù)同,是9的指數(shù)的2倍

49、所有的指數(shù)都是4的因數(shù),4是什么？a1379ord10(a)14422.6.1 指數(shù)與原根定理定理1 1 指數(shù)的基本性質(zhì) a n 1 (mod m)的充要條件是的充要條件是ordm( (a)|n)|n 分析：設(shè)n= ordm(a)q+r, 0r ordm(a), q,rZ，則： a n a ord(a)q+r a r 1 (mod m)， 因為ordm(a) 最小，所以r=0。推論：推論： ordm(a)| (m)定義定義2 2 若ordm (a)= (m)稱a是模m的原根原根（也寫作元根） 如，3和5是模7的原根，3和7是模10的原根原根也可能沒有，如模15、8沒有原根2.6.1 指數(shù)與原根

50、例例 證明：5是模3與模6的原根，也是模32，2* 32的原根(3)=2， (6)=(3)(2)=2(32)=9-3=6, (2*32)=(2)(32)=65-1(mod 3) 521(mod 3) 5是模3的原根5-1(mod 6) 521(mod 6) 5是模6的原根55(mod 9) 52-2(mod 9) 53-1(mod 9)544(mod 9) 552(mod 9) 561(mod 9) 5是模32原根55(mod 18) 527(mod 18) 53-1(mod 18)54-5(mod 18) 55-7(mod 18) 561(mod 18) 5是模2* 32原根2.6.1 指數(shù)

51、與原根解：解： (17)=16,所以只需計算5的1、2、4、8、16次方55(mod 17) 528(mod 17) 5413(mod 17) 5816-1(mod 17) 5161(mod 17) 所以ord17(5)=16，5是模17的原根。例例 計算5模17的指數(shù)ord17(5)=？ 2.6.1 指數(shù)與原根定理定理1 1 指數(shù)的基本性質(zhì) 若若a b (mod m)，(a, m) = 1，則則ordm( (a)= )= ordm(b) 分析： a ord(a) b ord(b) a ord(b) b ord(a) 1 (mod m), 所以ordm(a)| ordm(b), ordm(b)

52、| ordm(a) 所以ordm(a)=ordm(b)a-1a 1(mod m)，則則ordm( (a)= )= ordm(a-1) 分析： (a-1a ) n 1(mod m)則 (a-1) n 1(mod m) a n 1(mod m) 2.6.1 指數(shù)與原根解：解： ord17(39)=ord17(5)=167*5=1(mod 17) ord17(7)=ord17(5)=16例例 計算39、7模17的指數(shù)2.6.1 指數(shù)與原根定理定理1 1 指數(shù)的基本性質(zhì)記記n n= ordm( (a) ) , ,則則a0, a1, , a n 1對模對模m兩兩不同余兩兩不同余。 分析：反證法.若0 i

53、 j n 1,使a i a j (mod m)， 則由(a, m) = 1 得到 a j i 1 (mod m)， 這與j-in = ordm(a) ,與指數(shù)的定義矛盾 所以定理成立. 特別的：特別的：g是原根是原根g0, g1, , g (m) 1是模是模m的縮系的縮系思路：g1,g2,g (m) 這 (m)個數(shù)兩兩不同余，所以一定組成縮系;另一方面,g1,g2,g (m)是縮系，所以當(dāng)1l0, 0, ordm( (a i)=)=s s ，則則 。 分析： (a i)s 1 (mod m) n= ordm(a) |is 則最小的s= 。注：注： 當(dāng)（i,n）=1時，冪后指數(shù)不變，此時i的個數(shù)

54、為 （n）。 所以，有 （n）個與a 同指數(shù), n= ordm(a) 。 所以，如果m有原根，則原根個數(shù)為 ( (m)。),( nins sniinin),(|),(snin|),(),(nin2.6.1 指數(shù)與原根例例 觀察模7的所有縮系元素的指數(shù)ord7(2) =ord7(9)= ord = ord7(3) /(2, ord7(2) )=3ord7(4)= ord7(2)/(ord7(2),2) =3/(2,3)=3ord7(8)= 3/(3,3)=1ord7(16)=3/(4,3)=3a123456ord7(a)136362)3 (272.6.1 指數(shù)與原根例例 觀察模7的所有縮系元素的

55、指數(shù)7的原根(7)=(6)=2個，6有因子1、2、3、6所以存在：3指數(shù)的(3)=2個2指數(shù)的(2)=1個1指數(shù)的(1)=1個a123456ord7(a)1363622.6.1 指數(shù)與原根解：解： 模7的原根的個數(shù)為 (7)=(6)=2，由前例， 3是模7的原根,6的縮系元素有1，5。所以35(mod 7) 3*22 12 5。所以模7的兩個原根：3和5。例例 求出模7的所有原根2.6.1 指數(shù)與原根例例 計算計算7 7的縮系中每個元素的指數(shù)的縮系中每個元素的指數(shù)方法1：依次計算冪（如前）方法2：首先找到一個原根，3(從2開始計算指數(shù)找原根)用此原根生成縮系：322, 336, 344, 35

56、5, 361 (mod 7)則：ord7(2)=6/(2,6)=3; ord7(6)=6/(3,6)=2;ord7(4)=6/(4,6)=3; ord7(5)=6/(5,6)=6;ord7(1)=6/(6,6)=1; 再加上ord7(3)=6。2.6.1 指數(shù)與原根定理定理1 1 指數(shù)的基本性質(zhì)若若n m ，則則ordn( (a)| )| ordm( (a) ) 分析： a ordm (a) 1 (mod m) = a ordm (a) 1 (mod n) 對于m=pe的情況特別有用若若(m, n) = 1，(a, mn) = 1，則則ordmn( (a)= )= ordm( (a),),or

57、dn( (a) 分析：設(shè)s=ordm(a),ordn(a),t= ordmn(a),由 ordn(a)|t, ordm(a)|t =s|t; a s 1 (mod m) , a s 1 (mod n) = a s 1 (mod mn) = t|s 2.6.1 指數(shù)與原根解：解：(28)= (4) (7)=2*6=12本來需要計算冪為2、3、4、6但是因為ord7(3)=6，ord4(3)=2，所以6| ord28(3)現(xiàn)在只需直接計算361(mod 28)，所以ord28(3)= 6上面利用的是 ，利用直接因為(4，7)=1，所以ord28(3)=6,2=6。例例 計算3模28的指數(shù)ord28

58、(3)=？2.6.1 指數(shù)與原根解：解： (49)= 49-7=42ord7(3)=6，所以6| ord49(3)因為3681*9-17*9-2*3 -6(mod 49)所以ord49(3)= 42例例 計算3模49的指數(shù)ord49(3)=？2.6.1 指數(shù)與原根定理定理1 1 指數(shù)的基本性質(zhì) (ab, m) =1， ( (ordm( (a),),ordm( (b)=1)=1則則ordm( (ab)=)=ordm( (a) )ordm( (b) ) 分析：設(shè)a ordm (b) ordm (ab) a ordm (b) ordm (ab) b ordm (b) ordm (ab) (a b)

59、ordm (b) ordm (ab) 1 (mod m) = ordm(a)|ordm(b)ordm(ab),同理，ordm(b)|ordm(a)ordm(ab)所以， ordm(a)ordm(b)|ordm(ab)另一方面(a b) ordm (b) ordm (a) 1 (mod m) ,所以ordm(ab)|ordm(a)ordm(b)價值：簡化求原根價值：簡化求原根2.6.1 指數(shù)與原根解：解： (23)= 22，指數(shù)可能為1、2、11、22直接計算:224, 2111(mod 23)，所以ord23(2)=11用以前的方法在計算3的冪，如不行在計算5的此時考慮只需找到一個ord23(

60、a)=2，則ord23(2a)=22而ord23(-1)=2所以ord23(-2)=22，-2是原根，所以原根有(22)=10個(-2)315,(-2)514,(-2)710,(-2)917,(-2)1319(mod 23)(-2)157,(-2)175,(-2)1920,(-2)2111 (mod 23)所以模23的原根有：5,7,10,11,14,15,17,19,20,21。計算模23的原根2.6.2原根的存在條件對于什么樣的正整數(shù)m，模m的原根是存在?下面的定理不用證明，只需應(yīng)用定理定理 若若p p是奇素數(shù)，則原根存在是奇素數(shù)，則原根存在. .定理定理 若若p p是奇素數(shù)，是奇素數(shù)，g