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

1、數(shù)論算法 第三章 同余方程第 3 章 同余方程（一） 內(nèi)容：l 同余方程概念l 解同余方程l 解同余方程組（二） 重點l 解同余方程（三） 應(yīng)用l 密碼學(xué)，公鑰密碼學(xué)3.1 基本概念及一次同余方程(一) 同余方程（1） 同余方程【定義3.1.1】（定義1）設(shè)m是一個正整數(shù)，f(x)為n次多項式其中是正整數(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）中的每個剩余都是解。故把這些解都看做是相同的，并說剩余類是同余方程(1)的一個解，這個解通常記為xa（mod m）當均為同余方程(1)的解，且對模m不同余時，就稱它們是同余方程(2)的不同的解，所有對模m的兩兩不同余的解的個數(shù)，稱為是同余方程（1）的解數(shù)，記作。顯然m（4） 同余方程的解法一：窮舉法任意選定模m的一組完全剩余系，并以其中的每個剩余代入方程（1），在這完全剩余系中解的個數(shù)就是解數(shù)。【例1】（例1）可以驗證，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的絕對最小完全剩余系：7，6，1，0，1，2，7，直接計算知x6，3是解。所以，該同余方程的解是x6，3（mod 15）且解數(shù)2。【例3】求同余方程0（mod 15）的解（解）同樣直接計算知是解。所以它的解是，解數(shù)為4?！纠?】求解同余方程。（解）經(jīng)直接計算知，本方程無解，即解數(shù)為0。說明：當?shù)南禂?shù)都是模m的倍數(shù)時，顯見，任意的整數(shù)值x都是同余方程（1）的解，這樣的同余方程 （1）的解數(shù)為m。但這并不

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

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

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

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

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

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

10、應(yīng)于 (6)的解。這時，代入原同余方程得。利用定理3.1.1，它可化為由定理3.1.2知，滿足上式的y的值即為，即。所以，y3k1，x3y19k4，kz。因此，原同余方程恰有一個相應(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(a,b,m)時，ab（mod m）adbd（mod m）d）。(ii) 設(shè)同余方程（8）的全部解為 （10）由前一部分結(jié)論知，滿足模m的同余方程（1）的所有x

11、的值（不是解數(shù)）即是由式（10）給出的全部x的值（不是同余類）。由定理3.1.2知，對應(yīng)于每一個同余類，恰好是模m的d個不同的同余類之和，由此就推出式（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倍。故可以先解相對簡單的方程（6），再利用其解求方程（1）

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

13、9x260（mod 3）的等價方程為00（mod 3），故其解為x0，1，2。由定理3.1.2知原方程的不同的解一定在集合0,3,6,9,12；1,4,7,10,13；2,5,8,11,14中。若采用方法一，即逐個試驗：以x0，1，14分別代入原方程中，可知x2，7，12（mod 15）滿足原方程。但定理3.1.2沒有發(fā)揮作用。若用方法二，還得再解3個方程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】當（a，m）1時，同余方程（11）必有解，且其解數(shù)為1。證法一 已知當時，x遍歷模m的一組完全剩余系時，ax也遍歷模m的完全剩余系，即若是模m的一組完全剩余系，則也是模m的一組完全剩余系。因此，有且僅有一個使得即同余方程（11）有且僅有一個解。證法2 當時，可知a對模m有逆滿足容易看出滿足同余方程（11）。其次，若還有解也滿足方程（11），則有，從而。即方程（11）的解數(shù)為1。特別地，按照證法二，并利用euler定理，同余方程（11）的解是（mod m） （12）【例9】解一次同余方程3x8（mod 20）。（解）用方法一、即窮舉。令x0,1,2,19，經(jīng)計算，可知

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

16、方程 （13）的x的值是相同的。由于，故由定理3.1.4知同余方程（13）有解，所以同余方程（11）也有解。這就證明了充分性。其次，求方程（11）的解數(shù)：若是同余方程（11）的解，則它也是同余方程（13）的解，進而由定理3.1.4知，滿足同余方程（13）的所有的x的值是（mod ） （14）由上面討論知，式（14）也給出了滿足同余方程（11）的所有的x的值（不是解數(shù)）。即由式（14）給出的模的同余類就是以下d個模m的同余類：即定理的后一半結(jié)論成立?！就普摗浚ǘɡ?）當(a,m)1時，一次同余方程x1（mod m） （15）有唯一解x（mod m）?！径x3.1.2】模m可逆元：設(shè)m是一個正整數(shù)

17、，a是一個整數(shù)，。若存在整數(shù)，使得1（mod m）成立，則a叫做模m可逆元，叫做a的模m逆元，記作a（mod m）?！径ɡ?.1.6】（定理3）記d(a,m)，則一次同余方程（11）的全部解為， 。(四) 簡化剩余的充要條件【定理3.1.7】（定理4）整數(shù)a是模m的簡化剩余a是模m可逆元。(五) 一次同余方程的解法（1）窮舉【例10】解一次同余方程6x9（mod 15）（解）方式一：針對原方程和模15窮舉，即令x0,1,2,14，計算：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）方式二：化原方程為解的值相同的等價方程2x3（mod 5） (16)再對模5窮舉，即令x0,1,2,3,4，計算：r2x（mod 5）（0r4）200， 212， 224， 231， 243 方程(16)的解為 x4（mod 5）即原方程的解為 x4，45，4104，9，14（mod 15）【例11】解一次同余方程6x9（mod 14）（解）方式一：針對原方程和模14窮舉600， 616， 6212，634， 6410， 652， 668， 670， 686， 6912， 6104，61110，6122，6138 原方程

19、無解（2）公式：先判斷，后求解【例12】解一次同余方程12x18（mod 30）。（解）(12,30)6，618，所以原方程有6個解。等價方程2x3（mod 5） （17）解得x4（mod 5），即對模數(shù)5而言，剩余類集合xxz，x4（mod 5）,6,1,4,9,14,中每個剩余都是方程（17）的解，從而每個都是原方程的解。但對模數(shù)m5而言，中的所有元素都屬于同一個剩余類，故只是一個解。也就是說方程（17）只有一個解。若這個解取最小正剩余，則有x4，若取最大非正剩余，則x1。而對模數(shù)m30而言，集合中的所有元素并不屬于同一個剩余類，而且可以看出，當m30時，集合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個不同的解。即4，9，14，19，24，29（mod 30）【例13】解一次同余方程99x18（mod 143）。（解）(99,143)11，而1118，所以原方程無解。（3）利用展

21、轉(zhuǎn)相除法：axb（mod m） （11）（i）取，由定理3.1.1知，同余方程（11）等價于同余方程 （18）（ii）同余方程（18）與同余方程 （19）同時有解或無解。這是因為同余方程（18）與不定方程同時有解或無解。而這不定方程可寫為同樣理由，上述不定方程與同余方程（19）同時有解或無解。（iii）若是（19）的解，則是（18），即（11）的解，這里 （20）反過來，若是(11)即(18)的解，則是（19）的解，這里 （21）此外，若，是（19）的兩個不同的解，則相應(yīng)地確定的，也是（18）即（11）的兩個不同的解。所以（19）和（18）即（11）的解數(shù)相同。總結(jié)：以上的步驟（i）（ii）（

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

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

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

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

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

27、其中z為待定參數(shù)）。再將x 代入方程組（10）的第二式，有 mod 或 mod 已知(,)(，)1，故有() mod 其中1 mod 。代入（11）式，得方程組（9）的解為（() mod ） mod 即（() mod ） mod 由數(shù)學(xué)歸納法，命題成立。(三) 例【例1】解“物不知數(shù)”問題。（解）（用公式）已知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。【例2】（韓信點兵）有兵一隊，不到百人，若排成三行縱隊，則末行一人；成五行縱隊，則末行二人；成七行縱隊，則末行五人。求兵數(shù)。（解）問題等價于解方程組。由上例知3，5，7時，m105，35，21，15，2（mod 3），1（mod 5），1（mod 7），從而有 x70121215518782（mod 105）規(guī)律：對方程 若模數(shù)3、5、7不變，則m、不變，故方程的解為x702115（mod 105） （12）韓信點兵：三人同行七十稀，五樹梅花廿一枝，七子團圓正月半，除百零五便得知。又如：有兵一隊，不到百人，若排成三行縱隊，則末行一人

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

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

31、交）求解方程組（解）孤立地看問題，方程組中每個方程的解都是已知的，即方程的解為x1（mod 3），方程的解為x5（mod 8）。那么，解方程組實質(zhì)就是求同時滿足方程和的x。為此，給出兩個方程各自解的值的集合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）是方程組和的共同解，從而也就是原方程組的解?！纠?】（利用集合求交）求解方程組（解）先獨立地解每個方程，得方

32、程的解為x5（mod 7），方程的解為x2，6（mod 8）。為了求同時滿足方程和的x，給出兩個方程各自解的值的集合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）。【例7】計算（mod 77）（解）方法一：利用euler定理和

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

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

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

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

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

38、.3.1求解）由定理3.3.1知方程等價于同余方程組即 分別解單個方程，得各自的解為 的解為 x1，4（mod 5） 的解為 x3，5，6（mod 7）聯(lián)立二方程的解，得方程組 （22）其解為（mod m）7353（mod 35）（m35，7，3，5，3）對不同的（，），設(shè)方程組（22）的解為a（mod 35）111444356356a31266241934說明：解方程組（22）的本質(zhì)原因是求同時滿足方程和的x：例如方程的一個解為x1（mod 5），方程的一個解為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）兩個方程的共同解，從而也就是原方程組的解。(二) 特殊情形定理3.3.1的意義還在于指出了一般同余方程（1）（即同余方程組（2）的求解途徑：即先解出每一個同余方程（3）的個全部解；然后，求一次同余方程組（4）的解；由這樣得到的t個解就是同余方程（1）的全部解。當對某個j，同余方程（3）無解，則同余方程（1）也無解。通常，當時，取。這樣，一般同余方程的求解就歸結(jié)為模為素數(shù)冪的同余方程的求解。即求解 0 mod (5)設(shè)f(x)

40、為整系數(shù)多項式，記稱為f(x)的導(dǎo)式。準備知識：f(abx)(bx)（按x 的升冪整理）【定理3.3.2】設(shè)x（mod p）是同余方程 0（mod p） (6)的一個解，且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è)定理對i1成立，即同余方程 0 mod （11）有解，0,1,2 （12）為了求方程 0 mod （13）的解，將（12）代入（13）得關(guān)于的同余方程 0 mod 從中解出，即得（13）的解。為此，展開上式得0 mod 其中諸為整數(shù)。由于i2時，k(i1)i，故（k2,3,n）所以上式化簡為0 mod （14）由歸納假設(shè)，是方程（11）的解，即 0 mod 亦即，從而（14）可化為 （mod p） （15）由（12）知（mod p），故（mod

42、 p）進而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,）（注：此時方程（25）的解為1，4，7（mod 9），

43、但下邊可以看出，對方程（23）而言，它們都對應(yīng)一個解）代入（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的公式計算）（1）1，解方程0（mod 3）得 x0（mod 3）那么 5，且（，p）（5，3）1從而2（mod p）3（2）2，解方程0 mod （31）利用公式（7） （7）計算f(0)6，故1（mod 3）0313 mod （3）3，解原方程利用公式（7）計算f(3)00（mod 3）303 mod 還可以繼續(xù)算下去f(3)00（mod 3）303 mod 【例4】（問題的本質(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,）中找，且對于模數(shù)而言，實際上最多只有3個不同的解0，3，6 mod （或0，3）以0，3代入方程（32）檢驗，知解為3 mod （3）3，解原方程0 mod （33）與上類似，上方程的解只能在x3，（0,1, 2,）中找，且對于模數(shù)而言，實際上也最多只有3個不同的解（0,1）6，3，12 mod 代入方程（33）檢驗，知解為3 mod 依次類推，當i1時，設(shè)方程的一個解為 mod 則當i時，相應(yīng)于的