數(shù)論算法講義 3章（同余方程）

1、數(shù)論算法 第三章 同余方程第 3 章 同余方程（一） 內(nèi)容：l 同余方程概念l 解同余方程l 解同余方程組（二） 重點(diǎn)l 解同余方程（三） 應(yīng)用l 密碼學(xué)，公鑰密碼學(xué)3.1 基本概念及一次同余方程(一) 同余方程（1） 同余方程【定義3.1.1】（定義1）設(shè)m是一個(gè)正整數(shù)，f(x)為n次多項(xiàng)式其中是正整數(shù)（0（mod m），則(x)0（mod m） （1）叫做模m的（n次）同余式（或模m的（n次）同余方程），n叫做f(x)的次數(shù)，記為deg f。（2） 同余方程的解若整數(shù)a使得 (a)0（mod m）成立，則a叫做該同余方程的解。（3） 同余方程的解數(shù)若a是同余方程（1）的解，則滿足xa（mo

2、d m）的所有整數(shù)都是方程（1）的解。即剩余類xxz，xa（mod m）中的每個(gè)剩余都是解。故把這些解都看做是相同的，并說(shuō)剩余類是同余方程(1)的一個(gè)解，這個(gè)解通常記為xa（mod m）當(dāng)均為同余方程(1)的解，且對(duì)模m不同余時(shí)，就稱它們是同余方程(2)的不同的解，所有對(duì)模m的兩兩不同余的解的個(gè)數(shù)，稱為是同余方程（1）的解數(shù)，記作。顯然m（4） 同余方程的解法一：窮舉法任意選定模m的一組完全剩余系，并以其中的每個(gè)剩余代入方程（1），在這完全剩余系中解的個(gè)數(shù)就是解數(shù)。【例1】（例1）可以驗(yàn)證，x2，4（mod 7）是同余方程0（mod 7）的不同的解，故該方程的解數(shù)為2。0113 mod 711

3、33 mod 721350 mod 7312472 mod 74110290 mod 75131312 mod 76177836 mod 7【例2】求同余方程0（mod 15）的解。（解）取模15的絕對(duì)最小完全剩余系：7，6，1，0，1，2，7，直接計(jì)算知x6，3是解。所以，該同余方程的解是x6，3（mod 15）且解數(shù)2?！纠?】求同余方程0（mod 15）的解（解）同樣直接計(jì)算知是解。所以它的解是，解數(shù)為4?！纠?】求解同余方程。（解）經(jīng)直接計(jì)算知，本方程無(wú)解，即解數(shù)為0。說(shuō)明：當(dāng)?shù)南禂?shù)都是模m的倍數(shù)時(shí)，顯見(jiàn)，任意的整數(shù)值x都是同余方程（1）的解，這樣的同余方程 （1）的解數(shù)為m。但這并不

4、是同余方程（1）的解數(shù)為m的必要條件。例如 2135x140（mod 7）顯然，上方程等價(jià)于方程 00（mod 7）【例5】由fermateuler定理知，同余方程 的解數(shù)為5；同余方程 的解數(shù)為7。一般地，對(duì)素?cái)?shù)p，同余方程的解數(shù)為p。【例6】同余方程即的解數(shù)為35。（證）記，由同余的性質(zhì)，存在i，j使得成立（因5、7都是素?cái)?shù)）直接計(jì)算：為奇函數(shù)，其余為偶函數(shù)x0時(shí)，0（mod 5），0（mod 7）x1時(shí)，0（mod 5），0（mod 7）0（mod 35）即x2時(shí)，50（mod 5），210（mod 7）即，x3時(shí)，100（mod 5），910（mod 7）x4時(shí)，150（mod 5），

5、2733970（mod 7）x5時(shí)，50（mod 5），6519370（mod 7）x6時(shí)，350（mod 35），x7時(shí)，500（mod 5），70（mod 7）x8時(shí)，650（mod 5），630（mod 7）x9時(shí)，800（mod 5），94970（mod 7）x10時(shí)，100（mod 5），144370（mod 7）x11時(shí)，2450（mod 5），210970（mod 7）x12時(shí)，2950（mod 5），298370（mod 7）x13時(shí)， 3450（mod 5），2470（mod 7）x14時(shí)，3950（mod 5），140（mod 7）x15時(shí)， 150（mod 5），3270

6、（mod 7）x16時(shí)， 5150（mod 5），939970（mod 7）x17時(shí)， 5850（mod 5），1197370（mod 7）注意：由于本方程中x的冪都是奇數(shù)，故當(dāng)x為其解釋時(shí)，x也是其解。(二) 同余方程的性質(zhì)【定理3.1.1】（i）若兩個(gè)多項(xiàng)式f(x)g(x)（mod m），則同余方程（1）的解和解數(shù)與同余方程g(x)0（mod m）相同，此時(shí)稱兩個(gè)方程同解。（ii）若，則同余方程（1）的解和解數(shù)與同余方程相同。特別地，當(dāng)時(shí)，取a（mod m），則多項(xiàng)式的首項(xiàng)系數(shù)為（證）（i）顯然。（ii）因?yàn)闀r(shí)，有(x)0（mod m） a(x)0（mod m）（當(dāng)(a,m)1時(shí)，bc（m

7、od m）abac（mod m）【例6】證明同余方程（mod 15）與方程（mod 15）同解。（證）首先（mod 15），故方程（mod 15）與（mod 15）同解。其次，由于4（mod 15），所以，原方程又可以化簡(jiǎn)為()0（mod 15）0（mod 15）0（mod 15）另外，同余方程（mod 12）與方程（mod 12）同解。【定理3.1.2】（i）設(shè)正整數(shù)dm，那么，模m的同余方程（1）有解的必要條件是模d的同余方程 （2）有解。（ii）設(shè)方程（2）有解，它的全部解為（mod d） （3）那么，對(duì)（1）的每個(gè)解（如果有的話）a，有且僅有一個(gè)滿足（mod d）（證）（i）設(shè)a是同余

8、方程（1）的解，即(a)0（mod m）從而由同余性質(zhì)知 m(a)。已知，所以d(a)所以 (a)0（mod d），即（2）成立。（ii）又若有兩個(gè)解和同時(shí)滿足（mod d）， （mod d）則由同余的等價(jià)性之傳遞性知，必有（mod d）即（ii）成立。意義：方程（1）的解一定要在與方程（2）的解同余的數(shù)中去找。如a是（1）的解，是（2）的解，則必有kd，其中k為某個(gè)整數(shù)【例7】解同余方程。（解）考慮模5的同余方程 （4）由于由定理3.1.1知，方程（4）與方程的解相同。上式即容易驗(yàn)證它無(wú)解。因而由定理3.1.2知原同余方程無(wú)解?！纠?】解同余方程。（解）由直接計(jì)算知，同余方程（即方程0（mo

9、d 3）有兩個(gè)解：方法一：利用方程0（mod 3）的解試探或窮舉。已知方程0（mod 3）的解為x0,1（mod 3），故由定理3.1.2知原方程的不同的解一定在集合0，3，6，1，4，7中。逐個(gè)試驗(yàn)：以x0，3，3，1，4，2分別代入原方程中，可知x3，0，3，4滿足原方程，而x2，1不滿足原方程。故原方程的解為x3，0，3，4。方法二：利用定理3.1.2，先求原同余方程相應(yīng)于 (5)的解。這時(shí)x3y0，代入原同余方程得顯見(jiàn)，上式對(duì)所有y都成立。因此，相應(yīng)的全部解即為滿足式（5）的全部x的值。所以，原模9的同余方程有三個(gè)相應(yīng)的解：x0,3,6（mod 9） 或x3,0,3（mod 9）再求相

10、應(yīng)于 (6)的解。這時(shí)，代入原同余方程得。利用定理3.1.1，它可化為由定理3.1.2知，滿足上式的y的值即為，即。所以，y3k1，x3y19k4，kz。因此，原同余方程恰有一個(gè)相應(yīng)的解這樣，由定理3.1.2推出，原同余方程的解數(shù)為4，即x3,0,3,4（mod 9）【定理3.1.3】（i）若正整數(shù)，則滿足模m的同余方程（1）的所有x的值（不是解數(shù)），與滿足模的同余方程 （8）的所有x的值相同。(ii)且有 （9）（證）（i）顯然（當(dāng)d(a,b,m)時(shí)，ab（mod m）adbd（mod m）d）。(ii) 設(shè)同余方程（8）的全部解為 （10）由前一部分結(jié)論知，滿足模m的同余方程（1）的所有x

11、的值（不是解數(shù)）即是由式（10）給出的全部x的值（不是同余類）。由定理3.1.2知，對(duì)應(yīng)于每一個(gè)同余類，恰好是模m的d個(gè)不同的同余類之和，由此就推出式（9）。證畢?！咀⒁狻慷ɡ?.1.2結(jié)論與定理3.1.3結(jié)論的區(qū)別（1） 定理3.1.2：方程（1）：(x)0（mod m）的解必滿足方程（2）：(x)0（mod d），而方程（2）的解未必滿足方程（1）。所以方程（2）的解集合包含方程（1）的解集合，從而可以在方程（2）的解中找方程（1）的解。（2） 定理3.1.3：方程（1）與方程（6）的所有解x的值相同，但解數(shù)不同，前者解數(shù)是后者的d倍。故可以先解相對(duì)簡(jiǎn)單的方程（6），再利用其解求方程（1）

12、的解和解數(shù)。【例9】解同余方程。（解）選d=(6,9,6,15)=3，由定理3.1.3知，原方程與方程的解的值相同。直接計(jì)算，同余方程有一個(gè)解：x2（mod 5）。其解的所有值的集合為s23，18，13，8，3，2，7，12，17，22，27，那么，由定理3.1.3的（i）知，s中每個(gè)值也滿足原方程。但相對(duì)于原方程而言，s中包含了3類不同的解，即s，13，2，17，8，7，22，3，12，27，即對(duì)原方程，其解為x2，7，12（mod 15）若用定理3.1.2的思路解方程，則是利用方程6x39x260（mod 3）或6x39x260（mod 5）的解再求原方程的解。由定理3.1.1知方程6x3

13、9x260（mod 3）的等價(jià)方程為00（mod 3），故其解為x0，1，2。由定理3.1.2知原方程的不同的解一定在集合0,3,6,9,12；1,4,7,10,13；2,5,8,11,14中。若采用方法一，即逐個(gè)試驗(yàn)：以x0，1，14分別代入原方程中，可知x2，7，12（mod 15）滿足原方程。但定理3.1.2沒(méi)有發(fā)揮作用。若用方法二，還得再解3個(gè)方程6(3y)39(3y)260（mod 15）、6(3y1)39(3y1)260（mod 15）、6(3y2)39(3y2)260（mod 15）才能獲得原方程的解。(三) 一次同余方程的解設(shè)ma，那么，模m的一次同余方程為axb（mod m）

14、 （11）【定理3.1.4】當(dāng)（a，m）1時(shí)，同余方程（11）必有解，且其解數(shù)為1。證法一 已知當(dāng)時(shí)，x遍歷模m的一組完全剩余系時(shí)，ax也遍歷模m的完全剩余系，即若是模m的一組完全剩余系，則也是模m的一組完全剩余系。因此，有且僅有一個(gè)使得即同余方程（11）有且僅有一個(gè)解。證法2 當(dāng)時(shí)，可知a對(duì)模m有逆滿足容易看出滿足同余方程（11）。其次，若還有解也滿足方程（11），則有，從而。即方程（11）的解數(shù)為1。特別地，按照證法二，并利用euler定理，同余方程（11）的解是（mod m） （12）【例9】解一次同余方程3x8（mod 20）。（解）用方法一、即窮舉。令x0,1,2,19，經(jīng)計(jì)算，可知

15、3168（mod 20） x16（mod 20）用方法二、因7（mod 20） x8785616（mod 20）【定理3.1.5】（定理1+補(bǔ)）一次同余方程（11）有解 (a,m)b。當(dāng)方程（11）有解時(shí)，其解數(shù)為d(a,m)。而且，若是（11）的某個(gè)解，則它的d個(gè)解是，。此時(shí)稱為方程（11）的一個(gè)特解，稱上式為方程（11）的通解。（證）必要性：設(shè)方程（11）有解x（mod m） ，即滿足ab（mod m），從而必存在使得abm即 amb而da， dm，故 damb。充分性：當(dāng)d(a,m)1時(shí)，就是定理3.1.4。故假定d1。若db，則由定理3.1.3知，滿足同余方程（11）的x的值和滿足同余

16、方程 （13）的x的值是相同的。由于，故由定理3.1.4知同余方程（13）有解，所以同余方程（11）也有解。這就證明了充分性。其次，求方程（11）的解數(shù)：若是同余方程（11）的解，則它也是同余方程（13）的解，進(jìn)而由定理3.1.4知，滿足同余方程（13）的所有的x的值是（mod ） （14）由上面討論知，式（14）也給出了滿足同余方程（11）的所有的x的值（不是解數(shù)）。即由式（14）給出的模的同余類就是以下d個(gè)模m的同余類：即定理的后一半結(jié)論成立。【推論】（定理2）當(dāng)(a,m)1時(shí)，一次同余方程x1（mod m） （15）有唯一解x（mod m）。【定義3.1.2】模m可逆元：設(shè)m是一個(gè)正整數(shù)

17、，a是一個(gè)整數(shù)，。若存在整數(shù)，使得1（mod m）成立，則a叫做模m可逆元，叫做a的模m逆元，記作a（mod m）?！径ɡ?.1.6】（定理3）記d(a,m)，則一次同余方程（11）的全部解為， 。(四) 簡(jiǎn)化剩余的充要條件【定理3.1.7】（定理4）整數(shù)a是模m的簡(jiǎn)化剩余a是模m可逆元。(五) 一次同余方程的解法（1）窮舉【例10】解一次同余方程6x9（mod 15）（解）方式一：針對(duì)原方程和模15窮舉，即令x0,1,2,14，計(jì)算：r6x（mod 15）（0r14）600， 616， 6212， 633， 649， 650， 666， 6712， 683， 699， 6100，6116，6

18、1212，6133，6149 原方程的解為 x4,9,14（mod 15）方式二：化原方程為解的值相同的等價(jià)方程2x3（mod 5） (16)再對(duì)模5窮舉，即令x0,1,2,3,4，計(jì)算：r2x（mod 5）（0r4）200， 212， 224， 231， 243 方程(16)的解為 x4（mod 5）即原方程的解為 x4，45，4104，9，14（mod 15）【例11】解一次同余方程6x9（mod 14）（解）方式一：針對(duì)原方程和模14窮舉600， 616， 6212，634， 6410， 652， 668， 670， 686， 6912， 6104，61110，6122，6138 原方程

19、無(wú)解（2）公式：先判斷，后求解【例12】解一次同余方程12x18（mod 30）。（解）(12,30)6，618，所以原方程有6個(gè)解。等價(jià)方程2x3（mod 5） （17）解得x4（mod 5），即對(duì)模數(shù)5而言，剩余類集合xxz，x4（mod 5）,6,1,4,9,14,中每個(gè)剩余都是方程（17）的解，從而每個(gè)都是原方程的解。但對(duì)模數(shù)m5而言，中的所有元素都屬于同一個(gè)剩余類，故只是一個(gè)解。也就是說(shuō)方程（17）只有一個(gè)解。若這個(gè)解取最小正剩余，則有x4，若取最大非正剩余，則x1。而對(duì)模數(shù)m30而言，集合中的所有元素并不屬于同一個(gè)剩余類，而且可以看出，當(dāng)m30時(shí)，集合xxz，x4（mod 5）,6

20、,1,4,9,14,19,24,29,34,56,26,4, 34,64,51,21,9, 39,69,46,16,14, 44,74,41,11,19, 49,79,36, 6,24, 54,84,31, 1,29, 59,89,xxz，x4（mod 30）xxz，x9（mod 30）xxz，x14（mod 30）xxz，x19（mod 30）xxz，x24（mod 30）xxz，x29（mod 30）原方程有6個(gè)不同的解。即4，9，14，19，24，29（mod 30）【例13】解一次同余方程99x18（mod 143）。（解）(99,143)11，而1118，所以原方程無(wú)解。（3）利用展

21、轉(zhuǎn)相除法：axb（mod m） （11）（i）取，由定理3.1.1知，同余方程（11）等價(jià)于同余方程 （18）（ii）同余方程（18）與同余方程 （19）同時(shí)有解或無(wú)解。這是因?yàn)橥喾匠蹋?8）與不定方程同時(shí)有解或無(wú)解。而這不定方程可寫為同樣理由，上述不定方程與同余方程（19）同時(shí)有解或無(wú)解。（iii）若是（19）的解，則是（18），即（11）的解，這里 （20）反過(guò)來(lái)，若是(11)即(18)的解，則是（19）的解，這里 （21）此外，若，是（19）的兩個(gè)不同的解，則相應(yīng)地確定的，也是（18）即（11）的兩個(gè)不同的解。所以（19）和（18）即（11）的解數(shù)相同?？偨Y(jié)：以上的步驟（i）（ii）（

22、iii）表明：求解模m的同余方程（11），通過(guò)同余方程（18）轉(zhuǎn)化為求解較小的模的同余方程（19）。如果（19）能立即解出，則由（20）就得到（11）的全部解；如果（19）還不容易解出，則繼續(xù)對(duì)它用步驟（i），（ii），化為一個(gè)模更小的同余方程。這樣進(jìn)行下去總能使問(wèn)題歸結(jié)為求解一個(gè)模很小且能直接看出其是否有解的同余方程。再依次利用式（20）（即步驟（iii）反向推導(dǎo)即可求得（11）的全部解?！纠?3】解同余方程589x1026（mod 817）。（解）。這表明最后一個(gè)關(guān)于u的同余方程對(duì)模19有19個(gè)解：按（iii），即式（20）逐次反向推導(dǎo)得：關(guān)于對(duì)模38的同余方程有19個(gè)解，u0,1,18關(guān)

23、于z對(duì)模95的同余方程有19個(gè)解：，u0,1,18關(guān)于y對(duì)模228的同余方程有19個(gè)解：，u0,1,18最后得到x對(duì)模817的同余方程有19個(gè)解：x(817y209)(228)(817(12u5)209)(228) 43u17 (mod 228)u0,1,18。注 在運(yùn)用這一方法時(shí)，千萬(wàn)不能把搞錯(cuò)（特別是b1的正負(fù)號(hào)）。此外，如果在運(yùn)用這方法過(guò)程中，利用同余式的性質(zhì)化簡(jiǎn)同余方程時(shí)，改變了同余方程的模。則要注意方程的解數(shù)。例如，在例1中，當(dāng)?shù)玫搅送喾匠?（22）后，如果利用同余的性質(zhì)，就得到容易看出，滿足這同余方程的所有的z的值是。但原來(lái)對(duì)z的同余方程的模為95，為了得到原方程（22）的解，就

24、要利用定理3.1.3，得到（22）有19個(gè)解：z25u，u0,1,18?！纠?3】解同余方程21x38（mod 117）。（解），最后的同余方程無(wú)解，所以原方程無(wú)解。3.2 中國(guó)剩余定理(一) 問(wèn)題同余方程組孫子算經(jīng)的“物不知數(shù)”問(wèn)題：今有物，不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？答：23問(wèn)題的建模：設(shè)物的總數(shù)為x，則x滿足稱為一次同余方程組。(二) 解法【定理3.2.1】（孫子定理、孫子剩余定理、中國(guó)剩余定理）設(shè)是兩兩互素的正整數(shù)。那么，對(duì)任意整數(shù)，一次同余方程組。 （1）必有解，且解數(shù)為1。并且有（i）若令，（i1,2,k）則同余方程組（1）的解是（mod m） （

25、2）其中是滿足 （i1,2,k） （3）的一個(gè)整數(shù)（即對(duì)模的逆）。（ii）若令，（i1,2,k1）則同余方程組（1）的解可表為（mod m） （4）其中是同余方程組的解（i1,2,k），并滿足遞歸關(guān)系式（mod ） （5）（i2,3,k）（證）證法一 由于，兩兩互素，故m （6）先證唯一性，即若同余方程組（1）有解，則必有（mod m）這是因?yàn)楫?dāng)均是同余方程組（1）的解時(shí)，必有 mod , i1,2,k由于兩兩互素，由同余的性質(zhì)，從上式及式（6）即知唯一性成立。下面證由式（2）給出的 （7）確是同余方程組（1）的解。顯見(jiàn)，所以滿足式（3）的必存在。由式（3）及（）立知 mod ， i1,2,k

26、即c是解。證法一雖然簡(jiǎn)單，但很難看出為什么有形式（2）那樣的解。證法二（構(gòu)造性證明方法）用歸納法。當(dāng)k1時(shí)，同余方程 mod 的解為x mod 當(dāng)k2時(shí)，原同余方程組等價(jià)于同余方程組 （7）將上式的第一個(gè)方程的解x mod 表為x （8）（其中z為待定參數(shù)）。再將x 代入方程組（7）的第二式，有 mod 或 mod 已知(,)(,)1，故有() mod 其中1 mod 。代入（8）式，得方程組（7）的解為（() mod ） mod 設(shè)i1（i2）時(shí)，命題成立。即方程組有解 mod 對(duì)于i，同余方程組 （9）等價(jià)于方程組 （10）類似于k2時(shí)的情形，可將（10）中第一個(gè)方程的解表為x （11）（

27、其中z為待定參數(shù)）。再將x 代入方程組（10）的第二式，有 mod 或 mod 已知(,)(，)1，故有() mod 其中1 mod 。代入（11）式，得方程組（9）的解為（() mod ） mod 即（() mod ） mod 由數(shù)學(xué)歸納法，命題成立。(三) 例【例1】解“物不知數(shù)”問(wèn)題。（解）（用公式）已知3，5，7，故m357105，。解方程，求（i1,2,k）：351（mod 3），得2（mod 3）211（mod 5），得1（mod 5）151（mod 7），得1（mod 7）由公式（2）得解為（mod m）352221131512（mod 105）233（mod 105）23（mo

28、d 105）即物品數(shù)可能為23105k， （k0）最少為23?！纠?】（韓信點(diǎn)兵）有兵一隊(duì)，不到百人，若排成三行縱隊(duì)，則末行一人；成五行縱隊(duì)，則末行二人；成七行縱隊(duì)，則末行五人。求兵數(shù)。（解）問(wèn)題等價(jià)于解方程組。由上例知3，5，7時(shí)，m105，35，21，15，2（mod 3），1（mod 5），1（mod 7），從而有 x70121215518782（mod 105）規(guī)律：對(duì)方程 若模數(shù)3、5、7不變，則m、不變，故方程的解為x702115（mod 105） （12）韓信點(diǎn)兵：三人同行七十稀，五樹(shù)梅花廿一枝，七子團(tuán)圓正月半，除百零五便得知。又如：有兵一隊(duì)，不到百人，若排成三行縱隊(duì)，則末行一人

29、；成五行縱隊(duì)，則末行二人；成七行縱隊(duì)，則末行五人。求兵數(shù)。（解）此即解方程組由式（12）得x70121215582（mod 105）【例3】（逐次求解，對(duì)應(yīng)證法二）求解 （13）（解）由第一個(gè)方程知 x2u1， u0,1,2（即針對(duì)第一個(gè)方程，有 x1（mod 2）代入第二個(gè)方程得 2u12（mod 3）解之得 u2（mod 3）即 u3v2， v0,1,2所以 x2u12(3v2)16v5， v0,1,2（即針對(duì)前兩個(gè)方程，有 x5（mod 6）代入第三個(gè)方程得 6v53（mod 5）解之得 v3（mod 5）即 v5w3， w0,1,2所以 x6v56(5w3)530w23， w0,1,2

30、 x23（mod 30）【例4】（代入化簡(jiǎn)法）繼續(xù)求解同余方程組（13）。1（mod 2） 2（mod 3） 3（mod 5） （解）化簡(jiǎn)過(guò)程：由方程知 x12y， y0,1,2 將代入方程、得12y2（mod 3）12y3（mod 5）即2y1（mod 3）2y2（mod 5）解之得y2（mod 3） y1（mod 5） （化為兩個(gè)方程），再由方程得y23z 將代入方程得23z1（mod 5）解之得（化為一個(gè)方程） z3（mod 5） 回代過(guò)程：由 z35t， t0,1,2將z代入 y23(35t)1115t將y代入 x12(1115t)2330t x23（mod 30）【例5】（利用集合求

31、交）求解方程組（解）孤立地看問(wèn)題，方程組中每個(gè)方程的解都是已知的，即方程的解為x1（mod 3），方程的解為x5（mod 8）。那么，解方程組實(shí)質(zhì)就是求同時(shí)滿足方程和的x。為此，給出兩個(gè)方程各自解的值的集合a=, -11, -8, -5, -2, 1, 4, 7, 10, 13, 16, , 31, 34, 37, 40, b=, -11, -3, 5, 13, 21, 29, 37, 45, 而其共同解則為集合a與b的交，即ab=, -11, 13, 37, 所以x13（mod 24）是方程組和的共同解，從而也就是原方程組的解?！纠?】（利用集合求交）求解方程組（解）先獨(dú)立地解每個(gè)方程，得方

32、程的解為x5（mod 7），方程的解為x2，6（mod 8）。為了求同時(shí)滿足方程和的x，給出兩個(gè)方程各自解的值的集合a=, -30, -23, -16, -9, -2, 5, 12, 19, 26, 33, 40, 47, 54, =, -30, -22, -14, -6, 2, 10, 18, 26, 34, 42, =, -10, -2, 6, 14, 22, 30, 38, 46, 54, 而其共同解的值的集合為a()=, -30, -2, 26, 54, 82, 110, 所以，原方程組的解為x-2, 26（mod 56）?！纠?】計(jì)算（mod 77）（解）方法一：利用euler定理和

33、模重復(fù)平方快速算法。首先，(2,77)1，故1（mod 77）所以（mod 77）其次，利用模重復(fù)平方快速算法得，23（mod 77）所以 23（mod 77）方法2：將計(jì)算x（mod 77）化為小模數(shù)的方程組，利用解方程組求r。即x（mod 77） （注意1（mod 7），1（mod 11）解之得 23（mod 77）【例8】求相鄰的四個(gè)整數(shù)，它們依次可被及整除。（解）設(shè)這四個(gè)相鄰整數(shù)是。由題意知x應(yīng)該滿足，即解同余方程組問(wèn)題。此時(shí)有，由定理3.2.1知。 所以滿足要求的四個(gè)相鄰整數(shù)有無(wú)窮多組，它們是2934844100t，2934944100t，2935044100t，2935144100

34、t 0，1，2，最小的這樣的四個(gè)相鄰正整數(shù)是：29348，29349，29350，29351【例9】（模數(shù)m1，m2，, mk不是兩兩互素）解同余方程組：（解）這里不兩兩互素，所以不能直接用定理3.2.1求解。容易看出，本同余方程組的等價(jià)方程組為顯見(jiàn)，滿足第一個(gè)方程的x必滿足第二個(gè)方程，而第三，四個(gè)方程是一樣的。因此，原同余方程組和同余方程組 （14）的解相同。同余方程組（14）滿足定理3.2.1的條件。容易解出其解為注意到，所以這也就是原同余方程組的解，且解數(shù)為1。上例給出了模數(shù)不是兩兩互素時(shí)，求解同余方程組（1）的具體例子?！纠?0】解同余方程組。（解） 這不是定理3.2.1中的同余方程組

35、的形式。容易看出，第二個(gè)同余方程有解且解數(shù)為2：。因此，原同余方程組的解就是以下兩個(gè)同余方程組的解： （15）及 （16）容易求出，同余方程組（15）的解是x31（mod 56）；同余方程組（16）的解是x3（mod 56）。所以，原同余方程組的解數(shù)為2，其解為3，31（mod 5）6【例11】解同余方程。（解） 這是一個(gè)一次同余方程，模數(shù)較大，求解不方便，但可以將其化為模較小的一次同余方程組來(lái)解，而且容易求解。由于，所以由同余性質(zhì)知，原同余方程與同余方程組的解相同。整理可得典型的方程組進(jìn)而，分別解同余方程組中的第二，第三，第四個(gè)方程，上述同余方程組就變?yōu)榈葍r(jià)方程組再由定理3.2.1求解此方程

36、組得。這就是原同余方程的解。(四) 其它孫子定理是數(shù)論中最重要的基本定理之一。它實(shí)質(zhì)上刻畫了剩余系的結(jié)構(gòu)?！径ɡ?.2.2】在定理3.2.1的條件下，若分別遍歷模的完全剩余系，則（mod m）遍歷模的完全剩余系。（證）令（mod m）則當(dāng)分別遍歷模的完全剩余系時(shí)，遍歷個(gè)數(shù)。下面證明這m個(gè)數(shù)模m兩兩不同余，從而構(gòu)成m的一個(gè)完全剩余系，即定理結(jié)論成立。用反證法：假如對(duì)相應(yīng)于的，存在另一組數(shù)，也使得（mod m）則應(yīng)有（mod m）由同余的性質(zhì)，上式成立的充分必要條件是 mod 即（注意當(dāng)ji時(shí)，0 mod ） （i1,2,k） （3）但，故有， （i1,2,k）而、是同一個(gè)完全剩余系中的兩個(gè)數(shù)，故

37、， （i1,2,k）3.3 高次同余式的解數(shù)及解法(一) 解數(shù)【定理3.3.1】（定理1）設(shè)兩兩互素，m，是整系數(shù)多項(xiàng)式。則同余方程 （1）與同余方程組 （2）等價(jià)。且這里表示同余方程的解數(shù)。也就是說(shuō)，解數(shù)是m的積性函數(shù)。（證）由同余的性質(zhì)知，當(dāng)兩兩互素時(shí)， 即等價(jià)性成立。設(shè)方程 （3）的解是 （i1,2,k），則由中國(guó)剩余定理可求得一次同余方程組 （4）的解x（mod m）因?yàn)椋?（i1,2,k）故x也是方程（1）的解。因此，當(dāng)遍歷f(x)0（mod ）的所有解（i1,2,k）時(shí)，x也遍歷方程（1）的所有解，即方程組（2）的解數(shù)為【例1】（例1）解同余方程0（mod 35）。（解）（用定理3

38、.3.1求解）由定理3.3.1知方程等價(jià)于同余方程組即 分別解單個(gè)方程，得各自的解為 的解為 x1，4（mod 5） 的解為 x3，5，6（mod 7）聯(lián)立二方程的解，得方程組 （22）其解為（mod m）7353（mod 35）（m35，7，3，5，3）對(duì)不同的（，），設(shè)方程組（22）的解為a（mod 35）111444356356a31266241934說(shuō)明：解方程組（22）的本質(zhì)原因是求同時(shí)滿足方程和的x：例如方程的一個(gè)解為x1（mod 5），方程的一個(gè)解為x3（mod 7），則二者解的值的集合為a=, -9, -4, 1, 6, 11, 16, 21, 26, 31, 36, b=,

39、-11, -4, 3, 10, 17, 24, 31, 38, 而其共同解則為集合a與b的交，即ab=, -4, 31, 66, 所以x31（mod 35）是方程組（22）兩個(gè)方程的共同解，從而也就是原方程組的解。(二) 特殊情形定理3.3.1的意義還在于指出了一般同余方程（1）（即同余方程組（2）的求解途徑：即先解出每一個(gè)同余方程（3）的個(gè)全部解；然后，求一次同余方程組（4）的解；由這樣得到的t個(gè)解就是同余方程（1）的全部解。當(dāng)對(duì)某個(gè)j，同余方程（3）無(wú)解，則同余方程（1）也無(wú)解。通常，當(dāng)時(shí)，取。這樣，一般同余方程的求解就歸結(jié)為模為素?cái)?shù)冪的同余方程的求解。即求解 0 mod (5)設(shè)f(x)

40、為整系數(shù)多項(xiàng)式，記稱為f(x)的導(dǎo)式。準(zhǔn)備知識(shí)：f(abx)(bx)（按x 的升冪整理）【定理3.3.2】設(shè)x（mod p）是同余方程 0（mod p） (6)的一個(gè)解，且1則同余式（5）有解x mod 其中由下面關(guān)系式遞歸得到 （7）(i2,3, )。（證）用歸納法。(i) 2，相應(yīng)于（5）的方程是 0 mod （8）由假設(shè)條件，方程（6）的解x（mod p）可表為p， 0,1,2代入（8）得關(guān)于的同余方程（希望選擇某些以使上式滿足方程（8） 0 mod 即0 mod 整理得 即 0 mod （9）由于是方程（6）的解，即 0（mod p），故p （或pq）。所以（9）可化為 （mod p）

41、 （10）由已條件知，1，故方程（10）有唯一解 （mod p）由此得（8）的解（注意方程(10)的解可能有3類情形，此處為其一）（ii）設(shè)3i，并假設(shè)定理對(duì)i1成立，即同余方程 0 mod （11）有解，0,1,2 （12）為了求方程 0 mod （13）的解，將（12）代入（13）得關(guān)于的同余方程 0 mod 從中解出，即得（13）的解。為此，展開(kāi)上式得0 mod 其中諸為整數(shù)。由于i2時(shí)，k(i1)i，故（k2,3,n）所以上式化簡(jiǎn)為0 mod （14）由歸納假設(shè)，是方程（11）的解，即 0 mod 亦即，從而（14）可化為 （mod p） （15）由（12）知（mod p），故（mod

42、 p）進(jìn)而1所以（15）有唯一解 （mod p） （mod p）代入（12），得（13）的解 （16）由歸納法原理，定理3.3.2成立?！纠?】解同余方程0 mod 。（解）（用定理3.3.2的證明思路求解）（1）1，解方程0（mod 3）即 x0（mod 3）得 x0（mod 3）即 xp03（0,1, 2,）（2）2，解方程0 mod （23）以 xp03 （24）代入（23），求滿足條件的0 mod 整理得0 mod （25）兩邊同除以p3得22（mod 3） （26）解得1（mod 3）（即方程（26）的解為 13，0,1, 2,）（注：此時(shí)方程（25）的解為1，4，7（mod 9），

43、但下邊可以看出，對(duì)方程（23）而言，它們都對(duì)應(yīng)一個(gè)解）代入（24）得滿足（23）的解x0303(13)39，（0,1, 2,）即 x3（mod 9）（若以方程（25）的另一解 43（0,1, 2,）代入（24）式，則x0303(43)129，即方程（23）的解仍為x123（mod 9）（以方程（25）的另一解 73（0,1, 2,）代入（24）式，也得同樣的結(jié)果）（3）3，解原方程0 mod （27）以 x39 （28）代入（27），求滿足條件的0 mod 整理得90 mod （29）或 180 mod 兩邊同除以9得20（mod 3） （30）解得0（mod 3）即方程（30）的解為 03，

44、0,1, 2,）代入（28）得滿足（27）的解x3939(03)327，（0,1, 2,）即 x3 mod 【例3】解同余方程0 mod 。（解）（用定理3.3.2的公式計(jì)算）（1）1，解方程0（mod 3）得 x0（mod 3）那么 5，且（，p）（5，3）1從而2（mod p）3（2）2，解方程0 mod （31）利用公式（7） （7）計(jì)算f(0)6，故1（mod 3）0313 mod （3）3，解原方程利用公式（7）計(jì)算f(3)00（mod 3）303 mod 還可以繼續(xù)算下去f(3)00（mod 3）303 mod 【例4】（問(wèn)題的本質(zhì)）解同余方程0 mod 。（解）（1）1，解方程0（mod 3）得 x0（mod 3）（即 xp03，（0,1, 2,）（2）2，解方程0 mod （32）由定理3.1.2知，上方程的解只能在xp03（0,1, 2,）中找，且對(duì)于模數(shù)而言，實(shí)際上最多只有3個(gè)不同的解0，3，6 mod （或0，3）以0，3代入方程（32）檢驗(yàn)，知解為3 mod （3）3，解原方程0 mod （33）與上類似，上方程的解只能在x3，（0,1, 2,）中找，且對(duì)于模數(shù)而言，實(shí)際上也最多只有3個(gè)不同的解（0,1）6，3，12 mod 代入方程（33）檢驗(yàn)，知解為3 mod 依次類推，當(dāng)i1時(shí)，設(shè)方程的一個(gè)解為 mod 則當(dāng)i時(shí)，相應(yīng)于的