同余式教學(xué)課件

1、2021-11-31第四章第四章 同同 余余 式式4.1 4.1 基本概念及一次同余式基本概念及一次同余式 2021-11-3皖西學(xué)院 數(shù)理系2一、基本概念一、基本概念1110( ),nnnnif xa xaxa xa az 設(shè)設(shè)0,1,.inmz 是是整整系系數(shù)數(shù)多多項(xiàng)項(xiàng)式式, ,( )0(mod)(1)f xm 稱稱是關(guān)于模是關(guān)于模m的同余方程，或同余式。的同余方程，或同余式。0(mod)nam 若若，則稱為則稱為n次同余方程。次同余方程。 ( )0(mod)f am 注注： 若若，則剩余類則剩余類 里的元素都滿足該方程。里的元素都滿足該方程。 ak定義定義1 12021-11-3皖西學(xué)院

2、 數(shù)理系3定義定義2 設(shè)設(shè)a是整數(shù)，當(dāng)是整數(shù)，當(dāng) ( )0(mod)f am 成立時(shí)，成立時(shí)， 則稱則稱 (mod)xam 是同余方程是同余方程(1)的一個(gè)解。的一個(gè)解。 即與即與a同余的一切整數(shù)作為（同余的一切整數(shù)作為（1）式的一個(gè)解。）式的一個(gè)解。( )0(mod)(1)f xm 注：同余方程注：同余方程(1)的解數(shù)是指它的關(guān)于模的解數(shù)是指它的關(guān)于模m互不同余互不同余的所有解的個(gè)數(shù)，也即在模的所有解的個(gè)數(shù)，也即在模m的一個(gè)完全剩余系中的一個(gè)完全剩余系中的解的個(gè)數(shù)。顯然，同余方程的解的個(gè)數(shù)。顯然，同余方程(1)的解數(shù)不超過(guò)的解數(shù)不超過(guò)m。2021-11-3皖西學(xué)院 數(shù)理系4二、等價(jià)同余式二、

3、等價(jià)同余式定理定理1 1 下面的結(jié)論成立：下面的結(jié)論成立：（1）設(shè)）設(shè)b(x)是整系數(shù)多項(xiàng)式，則同余方程是整系數(shù)多項(xiàng)式，則同余方程(1)與與 f(x) b(x) b(x) (mod m)等價(jià)；等價(jià)；（2）設(shè)）設(shè)b是整數(shù)，是整數(shù)，(b, m) = 1，則同余方程，則同余方程(1)與與 bf(x) 0 (mod m)等價(jià)；等價(jià)；（3）設(shè)）設(shè)m是素?cái)?shù)，是素?cái)?shù)，f(x) = g(x)h(x)，g(x)與與h(x)都是都是 整系數(shù)多項(xiàng)式，又設(shè)整系數(shù)多項(xiàng)式，又設(shè)x0是同余方程是同余方程(1)的解，的解， 則則x0必是同余方程必是同余方程 g(x) 0 (mod m) 或或 h(x) 0 (mod m)的解

4、。的解。( )0(mod)(1)f xm 2021-11-3皖西學(xué)院 數(shù)理系5三、一次同余方程的基本解法三、一次同余方程的基本解法定理定理2 設(shè)設(shè)a，b是整數(shù)，是整數(shù)，a 0 (mod m)。則同余方程。則同余方程 ax b (mod m) (2) 有解的充要條件是有解的充要條件是(a, m) b。 若有解，則恰有若有解，則恰有d = (a, m)個(gè)解。個(gè)解。 特別地，若特別地，若(a, m)1，則方程（，則方程（2）有唯一解。）有唯一解。證明證明 ax b (mod m) m axb 同余方程同余方程(2)等價(jià)于不定方程等價(jià)于不定方程 ax my = b， (3)因此，第一個(gè)結(jié)論可由第二章第

5、一節(jié)定理因此，第一個(gè)結(jié)論可由第二章第一節(jié)定理1p25得出。得出。2021-11-3皖西學(xué)院 數(shù)理系6若同余方程若同余方程(2)有解有解x0，則存在，則存在y0，使得，使得x0與與y0是是方程方程(3)的解，的解，00( ,),(4)( ,)mxxta mtzayyta m 由式由式(4)所確定的所確定的x都滿足方程都滿足方程(2)。 ax b (mod m) (2) ax my = b (3)此時(shí)，方程此時(shí)，方程(3)(3)的解是的解是記記d = (a, m)，以及，以及t = dq r，q z，r = 0, 1, 2, , d 1.00(mod),mmxxqmrxrmdd則則0 r d 1。

6、 2021-11-3皖西學(xué)院 數(shù)理系7容易驗(yàn)證，當(dāng)容易驗(yàn)證，當(dāng)r = 0, 1, 2, , d 1時(shí)，相應(yīng)的解時(shí)，相應(yīng)的解00002(1)mmdmxxxxddd ， ，對(duì)于模對(duì)于模m是兩兩不同余的，所以同余方程是兩兩不同余的，所以同余方程(2)恰有恰有d個(gè)解。個(gè)解。00(mod)(mod)rmsmrmsmxxmmrsdddd 注注：解方程解方程(2)(2)的方法：的方法： 先求出相應(yīng)不定方程先求出相應(yīng)不定方程 ax my = b的一個(gè)特解的一個(gè)特解 0 x0(mod), 01.mxxrmrdd 再再代代入入2021-11-3皖西學(xué)院 數(shù)理系8例例1 1 解同余式解同余式 912(mod15).

7、x (9,15)3,312d 解解：且且故原同余式有故原同余式有3 3個(gè)解。個(gè)解。 0915123.xyx 解解方方程程得得一一個(gè)個(gè)特特解解所以所以 原同余式的解為原同余式的解為 335 (mod15),0,1,2mxrrrd3,8,13(mod15).x 即即2021-11-3皖西學(xué)院 數(shù)理系9四、其他解法四、其他解法定理定理3 3 ( ,)1,|,a mamyza b+ ym 設(shè)設(shè)又又設(shè)設(shè)使使得得(mod ).myba 即即滿滿足足(mod).bymxma 則則是是方方程程的的解解ax b (mod m)證證: 直接驗(yàn)算，有直接驗(yàn)算，有 ax b ym b (mod m)。 注：注： 將一

8、個(gè)對(duì)于較大模將一個(gè)對(duì)于較大模m的同余方程轉(zhuǎn)化為一個(gè)對(duì)于的同余方程轉(zhuǎn)化為一個(gè)對(duì)于較小模較小模a的同余方程，設(shè)的同余方程，設(shè)m r (mod a)，r 0，且，且(a, m) = 1，a1是是m對(duì)模對(duì)模a的最小的最小非負(fù)剩余，則同余方程非負(fù)剩余，則同余方程1(mod)ma xbma 等價(jià)于同余方程等價(jià)于同余方程 ax b (mod m) 證：設(shè)證：設(shè)x是是ax b (mod m)的解，的解， 1mm = aaa 由由得得：1()ma x = maxa maxa (mod)mbma 即即x是同余方程是同余方程 的解。的解。 1(mod)ma xbma 由假設(shè)條件知：這兩個(gè)同余方程都有且只有一個(gè)解，由

9、假設(shè)條件知：這兩個(gè)同余方程都有且只有一個(gè)解，所以這兩個(gè)同余方程等價(jià)。所以這兩個(gè)同余方程等價(jià)。2021-11-3皖西學(xué)院 數(shù)理系14例例3 解同余方程解同余方程6x 7 (mod 23)。解解 由定理由定理4 4，依次得到，依次得到6x 7 (mod 23) 5x 7 3 2 (mod 23) 3x 2 4 8 (mod 23) 2x 87 10 (mod 23) x 5 (mod 23)。1(mod)ma xbma ax b (mod m) 2021-11-3皖西學(xué)院 數(shù)理系15定理定理5 5 四、其他解法四、其他解法 應(yīng)用歐拉定理應(yīng)用歐拉定理設(shè)設(shè)(a, m) = 1，并且有整數(shù)，并且有整數(shù)

10、0使得使得 a 1 (mod m)， 則同余方程則同余方程ax b (mod m)的解是的解是 x ba 1 (mod m).注注1 1：直接驗(yàn)證即可。：直接驗(yàn)證即可。 注注2：由定理：由定理5及及euler定理可知，若定理可知，若(a, m) = 1，則，則x ba (m) 1 (mod m) 是同余方程是同余方程ax b (mod m)的解。的解。例例4 4 解同余方程解同余方程 1714(mod21)x 解：解：x ba (21) 1 1114 17 7(mod21) 2021-11-3皖西學(xué)院 數(shù)理系16五、簡(jiǎn)單同余方程組五、簡(jiǎn)單同余方程組模相同模相同的解法的解法例例5 5 解同余方程

11、組解同余方程組 351(mod7)232(mod7)xyxy 解解: :將將( (* *) )的前一式乘以的前一式乘以2 2，后一式乘以，后一式乘以3 3，相減得到，相減得到 ( (* *) )19y 4 (mod 7)，即即 5y 4 (mod 7)，y 2 (mod 7)。再代入再代入( (* *) )的前一式得到的前一式得到 3x 10 1 (mod 7)， x 4 (mod 7)。即同余方程組即同余方程組( (* *) )的解是的解是x 4，y 2 (mod 7)。注：注：同余方程組的解法與方程組的解法相似。同余方程組的解法與方程組的解法相似。2021-11-3皖西學(xué)院 數(shù)理系174.

12、2 4.2 孫子定理孫子定理 2021-11-3皖西學(xué)院 數(shù)理系18問題：?jiǎn)栴}：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何。剩三，七七數(shù)之剩二，問物幾何。孫子算經(jīng)孫子算經(jīng)分析：分析：設(shè)所求物數(shù)為設(shè)所求物數(shù)為x，則有，則有 2(mod3),3(mod5),2(mod7).xxx 稱之為同余式組。稱之為同余式組。即要求這些同余式的公共解。即要求這些同余式的公共解。一一般般地地，1122(mod),(mod),(mod)kkxamxamxam 2021-11-3皖西學(xué)院 數(shù)理系19問題：?jiǎn)栴}：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之今有物不

13、知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何。剩三，七七數(shù)之剩二，問物幾何。孫子算經(jīng)孫子算經(jīng)為什么??？為什么啊？除除數(shù)數(shù)余余數(shù)數(shù)最小公最小公倍數(shù)倍數(shù)衍數(shù)衍數(shù)乘乘率率 各各 總總答答 數(shù)數(shù)最小最小答數(shù)答數(shù)3 32 23 35 57 7=105=1055 57 72 235352 23 3140+63140+63+30+30=233=233233-233-2 2105105=23=235 53 33 37 71 121211 13 37 72 23 35 51 115151 12 22021-11-3皖西學(xué)院 數(shù)理系20問題問題1：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之今有物不知其數(shù)

14、，三三數(shù)之剩二，五五數(shù)之剩二，七七數(shù)之剩二，問物幾何。剩二，七七數(shù)之剩二，問物幾何。問題問題2：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，問物幾何。剩三，問物幾何。x-2是是3、5、7的公倍數(shù)。的公倍數(shù)。3|2, 5|3xx123253xkk11152,51(mod3),xnn 記記且且1522(mod3)n 則則；22233,31(mod5),xnn 記記且且2333(mod5).n 則則125,3,| x| x另另外外，顯顯然然有有12122(mod3),3(mod5).xxxx 從從而而有有2021-11-3皖西學(xué)院 數(shù)理系21問題：?jiǎn)栴}：今有物不

15、知其數(shù)，三三數(shù)之剩二，五五數(shù)之今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何。剩三，七七數(shù)之剩二，問物幾何。孫子算經(jīng)孫子算經(jīng)111572,571(mod3),xnn 記記且且12(mod3)x 則則；222373,371(mod5),xnn 記記且且23(mod5).x 則則322352,351(mod7),xnn 記記且且32(mod7).x 則則12357,37,35,| x| x| x另另外外，顯顯然然有有123,xxxx令令2(mod3),3(mod5),2(mod7).xxx 則則有有2021-11-3皖西學(xué)院 數(shù)理系22一、同余式組的解法一、同余式組的解法中國(guó)剩

16、余定理中國(guó)剩余定理定理定理1 1 孫子定理孫子定理 1122(mod),(mod),(mod) (1)kkxamxamxam m1, m2, , mk是兩兩互質(zhì)的正整數(shù)，是兩兩互質(zhì)的正整數(shù)， 記記 m = m1m2mk ， ,1.iimmikm則則(1)的解為的解為 1(mod)(2)kiiiixa m mm 其中，整數(shù)其中，整數(shù)mi （1 i k），滿足），滿足mimi 1 (mod mi). 設(shè)有同余式組設(shè)有同余式組2021-11-3皖西學(xué)院 數(shù)理系23證明：證明： 由由 (mi, mi) = 1，利用輾轉(zhuǎn)相除法可以求出，利用輾轉(zhuǎn)相除法可以求出mi 與與yi ，使得，使得mimi yimi

17、 = 1， 1(mod)iiim mm aimimi ai (mod mi)，1 i k。, (,)1iijjijm mm mmm m由由,.ijm mij 1(mod)kjjjiiiiija m ma m mam 121(mod,)(mod)kjjjikija m mam mmam 1(mod)(1).kjjjjxa m mm 滿滿足足方方程程2021-11-3皖西學(xué)院 數(shù)理系24反之，若反之，若 是（是（1）的解，）的解， 1x1(mod).iixam 則則又又 m1, m2, , mk兩兩互質(zhì)，兩兩互質(zhì)， 1(mod).ixam 所所以以故方程（故方程（1 1）的解只能為（）的解只能為（

18、2 2）式。）式。2021-11-3皖西學(xué)院 數(shù)理系25例例1 1 解同余式組解同余式組 2(mod3),3(mod5),2(mod7).xxx 1233,5,7mmm 解解：兩兩兩兩互互質(zhì)質(zhì)，357105.m = 12335,21,15.mmm ii123m m 1(mod)1,1,1immmm 由由()im 不不唯唯一一351(mod3) 35( 1)1(mod3); 211(mod5) 21 11(mod5);151(mod7) 15 11(mod7). 1kiiiixa m m 235( 1)321 1215123(mod105) 衍數(shù)衍數(shù)乘率乘率() 衍衍數(shù)數(shù)乘乘率率余余數(shù)數(shù)2021

19、-11-3皖西學(xué)院 數(shù)理系26例例2 2 韓信點(diǎn)兵韓信點(diǎn)兵有兵一隊(duì)，若列成五行縱隊(duì)，則有兵一隊(duì)，若列成五行縱隊(duì)，則末行末行1 1人；成六行縱隊(duì)，則末行人；成六行縱隊(duì)，則末行5 5人；成七行縱隊(duì)，人；成七行縱隊(duì)，則末行則末行4 4人；成十一行縱隊(duì)，則末行人；成十一行縱隊(duì)，則末行1010人。求兵數(shù)。人。求兵數(shù)。解解：即即求求解解同同余余式式組組1(mod5),5(mod6),4(mod7),10(mod11).xxxx 12345,6,7,11.mmmm 其其中中，12341,5,4,10.aaaa 126711462,5711385,mm 345611330,567210.mm 余數(shù)余數(shù)衍數(shù)衍數(shù)

20、2021-11-3皖西學(xué)院 數(shù)理系27列表如下：列表如下： 5 1 2310 462 6 5 385 7 4 330 11 10 210 imiamimimiiia m miiia m m 4622(mod5)46231(mod5) 其他略其他略14623 53851 43301 102101 67312111(mod2310) 31112021-11-3皖西學(xué)院 數(shù)理系28定理定理2 在定理在定理1的條件下，若式的條件下，若式(1)中的中的a1, a2, , ak分別通過(guò)模分別通過(guò)模m1, m2, , mk的完全剩余系，則式的完全剩余系，則式(2)中中的的x通過(guò)模通過(guò)模m1m2mk的完全剩余

21、系。的完全剩余系。證明：證明：1(mod)kiiiixa m mm 由由，則則x通過(guò)通過(guò)m1m2mk個(gè)整數(shù)，個(gè)整數(shù)， 且容易它們是兩兩不同余的。且容易它們是兩兩不同余的。2021-11-3皖西學(xué)院 數(shù)理系29二、同余方程組解的存在性及解數(shù)的判定二、同余方程組解的存在性及解數(shù)的判定引理引理：設(shè)：設(shè)a1，a2是整數(shù)，是整數(shù)，m1，m2是正整數(shù)，則是正整數(shù)，則 同余同余方程組方程組1122(mod),(mod)(3)xamxam 有解的充要條件是有解的充要條件是 a1 a2 (mod (m1, m2) (4)若有解，則對(duì)模若有解，則對(duì)模m1, m2是唯一的，即若是唯一的，即若x1與與x2都是都是同余

22、方程組同余方程組(3)的解，的解，則則 x1 x2 (mod m1, m2)。 (5)證證 必要性必要性 1122(mod),(mod)xamxam 1122,m xam xa 1212(,)m maa2021-11-3皖西學(xué)院 數(shù)理系30充分性充分性記記(m1, m2)d.若式若式(4)(4)成立，成立， 12d aa 即即，則同余方程則同余方程m2y a1 a2 (mod m1) 有解有解y y0 (mod m1)， 記記x0 = a2 m2y0，則，則 x0 a2 (mod m2).并且并且 x0 = a2 m2y0 a2 a1 a2 a1 (mod m1)，因此因此x0是同余方程組是同

23、余方程組(3)的解。的解。若若x1與與x2都是方程組都是方程組(3)的解，的解， 則則 x1 x2 (mod m1)，x1 x2 (mod m2)，從而有從而有 x1 x2 (mod m1, m2)。2021-11-3皖西學(xué)院 數(shù)理系31定理定理3 3 同余方程組同余方程組(1)有解的充要條件是有解的充要條件是ai aj (mod (mi, mj)，1 i, j n。 (6)2021-11-3皖西學(xué)院 數(shù)理系322021-11-3皖西學(xué)院 數(shù)理系332021-11-3皖西學(xué)院 數(shù)理系344.3 4.3 高次同余式的解數(shù)及解法高次同余式的解數(shù)及解法 ( )0(mod)f xm ( ).f xx其

24、其中中，是是關(guān)關(guān)于于 的的整整系系數(shù)數(shù)多多項(xiàng)項(xiàng)式式2021-11-3皖西學(xué)院 數(shù)理系35一、化合數(shù)模為兩兩互質(zhì)的模一、化合數(shù)模為兩兩互質(zhì)的模例例1 解同余方程解同余方程 5x2 6x 49 0 (mod 60)。（。（1）解：解： 60 = 3 4 5，同余方程同余方程(1)等價(jià)于同余方程組等價(jià)于同余方程組5x2 6x 49 0 (mod 3) 即即-x2 1 0 (mod 3) (2)5x2 6x 49 0 (mod 4) 即即x2 2x 1 0 (mod 4) (3)5x2 6x 49 0 (mod 5) 即即x -1 0 (mod 5) (4)由由(2)(2)得：得： x1(1) 1，x

25、2(1) 1 (mod 3)，由由(3)(3)得：得： x1(2) 1，x2(2) 1 (mod 4)，由由(4)(4)得：得： x1(3) 1 (mod 5)2021-11-3皖西學(xué)院 數(shù)理系36這樣，同余方程這樣，同余方程(1)的解的解x可由下面的方程組決定：可由下面的方程組決定：x1(1) 1，x2(1) 1 (mod 3)，x1(2) 1，x2(2) 1 (mod 4)， x1(3) 1 (mod 5)x a1 (mod 3)，x a2 (mod 4)，x a3 (mod 5)，其中其中a1 = 1或或 1，a2 = 1或或 1，a3 = 1。 利用孫子定理，其中利用孫子定理，其中m1

26、 = 3，m2 = 4，m3 = 5，m = 60.m1 = 20，m2 = 15，m3 = 12，m1 = 2，m2 = 1，m3 = 3，則則 x 40a1 15a2 36a3 (mod 60)。將將a1，a2，a3所有可能的取值代入上式，得到方程所有可能的取值代入上式，得到方程(1)的全部解是的全部解是x1 1 (mod 60)，x2 19 (mod 60)，x3 31 (mod 60)，x4 11 (mod 60)。2021-11-3皖西學(xué)院 數(shù)理系37注注：由定理：由定理4及算術(shù)基本定理，解一般模的同余方程及算術(shù)基本定理，解一般模的同余方程可以轉(zhuǎn)化為解模為素?cái)?shù)冪的同余方程?？梢赞D(zhuǎn)化為

27、解模為素?cái)?shù)冪的同余方程。定理定理4 設(shè)設(shè)m = m1m2mk ，其中，其中m1, m2, , mk 是兩兩是兩兩互素的正整數(shù)，互素的正整數(shù)，f(x)是整系數(shù)多項(xiàng)式，以是整系數(shù)多項(xiàng)式，以t與與ti（1 i k）分別表示同余方程）分別表示同余方程f(x) 0 (mod m) （1）與與 f(x) 0 (mod mi) ，1 i k. （2）的解的個(gè)數(shù)，的解的個(gè)數(shù)，則則t = t1t2tk 。2021-11-3皖西學(xué)院 數(shù)理系38定理的證明：定理的證明：因?yàn)橐驗(yàn)?a b (mod mi )，1 i k a b (mod m)，所以所以 同余方程同余方程(1)(1)等價(jià)于同余方程組（等價(jià)于同余方程組（

28、2 2） f(x) 0 (mod m) （1）f(x) 0 (mod mi) ，1 i k. （2）對(duì)于每個(gè)對(duì)于每個(gè)i（1 i k），設(shè)同余方程），設(shè)同余方程(2)的全部解是的全部解是( )( )( )12,(mod)(3)iiiitixxxxm 則同余方程組則同余方程組(3)等價(jià)于下面的等價(jià)于下面的t1t2tk個(gè)方程組：個(gè)方程組：12(1)(2)( )12(mod),(mod),(mod)(4)kkjjjkxxmxxmxxm ( )iijx其中其中 通過(guò)式通過(guò)式(3)中的數(shù)值，即通過(guò)方程中的數(shù)值，即通過(guò)方程(2)的全部解。的全部解。2021-11-3皖西學(xué)院 數(shù)理系39f(x) 0 (mod

29、 m) （1）f(x) 0 (mod mi) ，1 i k. （2）( )( )( )12,(mod)(3)iiiitixxxxm 12(1)(2)( )12(mod),(mod),(mod)(4)kkjjjkxxmxxmxxm 由孫子定理，對(duì)于選定的每一組由孫子定理，對(duì)于選定的每一組 12(1)(2)( ),kkjjjxxx同余方程組同余方程組(4)對(duì)模對(duì)模m有唯一解。有唯一解。 而且，由而且，由4.2定理定理2， 當(dāng)每個(gè)當(dāng)每個(gè) 通過(guò)通過(guò)(3)式中的值時(shí)，式中的值時(shí)， ( )iijx所得到的所得到的t1t2tk個(gè)同余方程組個(gè)同余方程組(4)的解對(duì)于模的解對(duì)于模m都是都是兩兩不同余的。兩兩不同

30、余的。 2021-11-3皖西學(xué)院 數(shù)理系40二、方冪模的解法二、方冪模的解法若若x0是同余方程是同余方程 f(x) 0 (mod p ) (1) 的解，的解，則必是方程則必是方程 f(x) 0 (mod p -1) (2) 的解的解. .因此，必有與因此，必有與x0相應(yīng)的方程相應(yīng)的方程(2)的某個(gè)解的某個(gè)解x1，使，使x0 x1 (mod p)，x0 = x1 p -1 t0，即可以從方程即可以從方程(2)(2)的解中去求方程的解中去求方程(1)(1)的解。的解。 但對(duì)于方程但對(duì)于方程(2)的每個(gè)解的每個(gè)解x1，是否必有方程，是否必有方程(1)的解的解x0與之對(duì)應(yīng)？若有，如何去確定它？與之對(duì)

31、應(yīng)？若有，如何去確定它？ 2021-11-3皖西學(xué)院 數(shù)理系41定理定理5 5 設(shè)設(shè)p是素?cái)?shù)，是素?cái)?shù)，n 2，f(x) = anxn a1x a0是整系數(shù)多項(xiàng)式，又設(shè)是整系數(shù)多項(xiàng)式，又設(shè)x1是同余方程是同余方程(2)的一個(gè)解。的一個(gè)解。以以f (x)表示表示f(x)的導(dǎo)函數(shù)。的導(dǎo)函數(shù)。1(1)()0(mod ),fxptz 若若則則存存在在使使得得11(3)xxpt 11(2)()0(mod ),()0(mod),fxpf xp 若若且且則對(duì)于則對(duì)于t = 0，1, 2, , p 1，式，式(3)中的中的x都是都是方程方程(1)(1)的解。的解。f(x) 0 (mod p ) (1)f(x)

32、0 (mod p -1) (2)是方程是方程(1)(1)的解。的解。2021-11-3皖西學(xué)院 數(shù)理系42證明：如何確定式證明：如何確定式(3)(3)中的中的t， 使使x1 p 1t滿足同余方程滿足同余方程(1)， an(x1+p 1t)n+an 1(x1+p 1t)n 1+a1(x1+p 1t)+a0 0 (mod p ) 即要使即要使由二項(xiàng)式定理展開可得由二項(xiàng)式定理展開可得 f(x1) p 1tf (x1) 0 (mod p ) （4）111()()(mod )(5)f xtfxpp 即即11(3)xxpt f(x) 0 (mod p ) (1)f(x) 0 (mod p -1) (2)下

33、面考慮兩種情形下面考慮兩種情形 2021-11-3皖西學(xué)院 數(shù)理系43 (1) 若若f (x1) 0 (mod p)， 則關(guān)于則關(guān)于t的同余方程的同余方程(5)有唯一解有唯一解t t0 (mod p)， 111()()(mod ) (5)f xtfxpp 即即t = t0 pk（k z），）， 于是于是 x x1 p 1t0 (mod p ) 是同余方程是同余方程(1)的解。的解。(2) 若若f (x1) 0 (mod p)，并且，并且f(x1) 0 (mod p )， 則式則式(5)對(duì)于任意的整數(shù)對(duì)于任意的整數(shù)t成立，成立， 即同余方程即同余方程(5)有有p個(gè)解個(gè)解 t i (mod p)，

34、0 i p 1。于是于是 x x1 p 1i (mod p )，0 i p 1，都是，都是同余方程同余方程(1)的解。的解。 2021-11-3皖西學(xué)院 數(shù)理系442021-11-3皖西學(xué)院 數(shù)理系45例例2 2 解同余方程解同余方程 4( )0(mod27),( )74f xf xxx 考慮方程：考慮方程：( )0(mod27)1f x （ ）( )0(mod9)2f x （ ）( )0(mod3)3f x （ ）44( )741f xxxxx 0(mod3) 1(mod3),x (1)1120(mod3)f 又又，則則(2)(2)的解可表示為：的解可表示為：113xt代入代入(2)(2)，

35、得，得411(13 )7(13 )40(mod9)tt 1111221110(mod9),tt 1360(mod9)t即即1120(mod3)t 11(mod3)t 1231.tt2021-11-3皖西學(xué)院 數(shù)理系46則則(2)(2)的解可表示為：的解可表示為：113xt1231.tt即即(2)(2)的解可表示為：的解可表示為：249 .xt 249(1),xt把把代代入入得得422(49 )7(49 )40(mod27)tt ，43224449194tt即即218180(mod27)t 2220(mod3)t 22(mod3)t2332tt 從而從而(1)(1)的解可表示為：的解可表示為：2

36、334949(32)2227xttt22(mod27)x 或或記記作作：2021-11-3皖西學(xué)院 數(shù)理系47推論推論1 1若若x a (mod p)是同余方程是同余方程 ( )0(mod )f xp 的的解解，( )0(mod ),(mod )fapxxap 并并且且，則則存存在在，(mod)( )0(mod).xxpf xp 使使得得是是同同余余方方程程的的解解42( )0(mod27),( )74.f xf xxx 如如例例 ：( )0(mod3)1(mod3),f xx 的的解解為為( )0(mod27)22(mod27),f xx 的的解解為為1,22,ax 這這里里，221(mod

37、3). 顯顯然然有有2021-11-3皖西學(xué)院 數(shù)理系48推論推論2 2( )0(mod )( )0(mod )fxpf xp若若與與沒沒有有公公共共解解，2,( )0(mod)( )0(mod)f xpf xp 則則對(duì)對(duì)與與的的解解數(shù)數(shù)相相同同。42( )0(mod27),( )74.f xf xxx 如如例例 ：( )0(mod3)1(mod3),f xx 的的解解為為( )0(mod3)2(mod3),fxx 的的解解為為( )0(mod27)( )0(mod3)f xf x 的的解解數(shù)數(shù)與與的的解解數(shù)數(shù)相相同同。2021-11-3皖西學(xué)院 數(shù)理系49三、一般高次同余式的解法三、一般高次

38、同余式的解法例例3 解同余方程解同余方程 x3 3x 14 0 (mod 45) 解：解： 原同余方程等價(jià)于同余方程組原同余方程等價(jià)于同余方程組 x3 3x 14 0 (mod 9)， (1) x3 3x 14 0 (mod 5). (2)先求先求(1)(1)的解：的解： x3 3x 14 0 (mod 3)的解為的解為 x 2 (mod 3)。令令x = 2 3t并代入方程并代入方程(1)，得到，得到(2 3t)3 3(2 3t) 14 0 (mod 9)，恒成立。恒成立。于是方程于是方程(1)的解是的解是 x 2，5，8 (mod 9)。 2021-11-3皖西學(xué)院 數(shù)理系50例例3 解同

39、余方程解同余方程 x3 3x 14 0 (mod 45) (2) 的解為：的解為： x 1，2 (mod 5)。解：解： 原同余方程等價(jià)于同余方程組原同余方程等價(jià)于同余方程組 x3 3x 14 0 (mod 9)， (1) x3 3x 14 0 (mod 5). (2)(1) 的解是：的解是： x 2，5，8 (mod 9)。x a1 (mod 9)， a1 = 2，5，8，x a2 (mod 5)， a2 = 1，2。因此，原同余方程的解是下面六個(gè)同余方程組的解：因此，原同余方程的解是下面六個(gè)同余方程組的解：利用孫子定理解這六個(gè)方程組利用孫子定理解這六個(gè)方程組. . 2021-11-3皖西學(xué)

40、院 數(shù)理系51記記 m1 = 9，m2 = 5，m = 45，m1 = 5，m2 = 9， 11111(mod)2;m mmm由由22221(mod)1.m mmm 由由12109(mod45)iiixa m maa 則則將將a1和和a2的不同取值代入，得到所求的解是的不同取值代入，得到所求的解是x1 10 2 9 1 11 (mod 45)，x2 10 2 9 2 2 (mod 45)，x3 10 5 9 1 41 (mod 45)，x4 10 5 9 2 32 (mod 45)，x5 10 8 9 1 26 (mod 45)，x6 10 8 9 2 17 (mod 45) 2021-11-

41、3皖西學(xué)院 數(shù)理系524.4 4.4 質(zhì)數(shù)模的同余式質(zhì)數(shù)模的同余式 2021-11-3皖西學(xué)院 數(shù)理系53 在上節(jié)證明了，對(duì)于素?cái)?shù)在上節(jié)證明了，對(duì)于素?cái)?shù)p，模，模p 的同余的同余方程的求解可以轉(zhuǎn)化為模方程的求解可以轉(zhuǎn)化為模p的同余方程的求解。的同余方程的求解。本節(jié)要對(duì)素?cái)?shù)模的同余方程做些初步研究。本節(jié)要對(duì)素?cái)?shù)模的同余方程做些初步研究。以下，設(shè)以下，設(shè)f(x) = anxn a1x a0是整系數(shù)多項(xiàng)式，是整系數(shù)多項(xiàng)式， a .npp a是是素素?cái)?shù)數(shù)，且且2021-11-3皖西學(xué)院 數(shù)理系54f(x) = anxn a1x a0 0 (mod p) (1)定理定理1 1 同余方程同余方程與一個(gè)次數(shù)

42、不超過(guò)與一個(gè)次數(shù)不超過(guò)p-1的同余式等價(jià)。的同余式等價(jià)。證：由帶余數(shù)除法，存在整系數(shù)多項(xiàng)式證：由帶余數(shù)除法，存在整系數(shù)多項(xiàng)式 ( ), ( ),q xr x( )() ( )( )pf xxx q xr x使使得得，( )1.r xp 且且的的次次數(shù)數(shù)不不超超過(guò)過(guò)由費(fèi)馬定理知，由費(fèi)馬定理知， (mod ),0(mod ).ppxxpxxp 即即( )( )(mod).xzf xr xp 從從而而，2021-11-3皖西學(xué)院 數(shù)理系55定理定理2 2 設(shè)設(shè)k n，若同余方程，若同余方程(1)有有k個(gè)不同的解個(gè)不同的解其中其中fk(x)是一個(gè)次數(shù)為是一個(gè)次數(shù)為n k的整系數(shù)多項(xiàng)式，的整系數(shù)多項(xiàng)式，

43、x1, x1, , xk，則對(duì)，則對(duì) 有有xz ，f(x) (x x1) (x x2)(x xk)fk(x) (mod p)，并且它的并且它的xn k項(xiàng)的系數(shù)是項(xiàng)的系數(shù)是an.證明：證明：由多項(xiàng)式除法，有由多項(xiàng)式除法，有f(x) = (x x1)f1(x) r1， (2)f1(x)是首項(xiàng)系數(shù)為是首項(xiàng)系數(shù)為an的的n 1次整系數(shù)多項(xiàng)式，次整系數(shù)多項(xiàng)式，r1是常數(shù)。是常數(shù)。 在式在式(2)兩邊令兩邊令x = x1，則可知，則可知f(x1) = r1 0 (mod p)， 因此，式因此，式(2)成為成為 f(x) (x x1)f1(x) (mod p) (3)即即 當(dāng)當(dāng)k = 1時(shí)，定理成立。時(shí)，定

44、理成立。 2021-11-3皖西學(xué)院 數(shù)理系56如果如果k 1，在，在(3)式中，令式中，令x = xi（i = 2, 3, , k），）， 則有則有 0 f(xi) (xi x1)f1(xi) (mod p) (4)由于由于x1, x2, , xk對(duì)于模對(duì)于模p是兩兩不同余的，是兩兩不同余的， f1(xi) 0 (mod p)，i = 2, , k。 (5)所以，由所以，由(4)(4)式得出式得出由此及歸納法，即可證明定理。由此及歸納法，即可證明定理。 f(x) (x x1)f1(x) (mod p) (3)2021-11-3皖西學(xué)院 數(shù)理系57定理定理3 3 (1) 若若p是素?cái)?shù)，則對(duì)于任

45、何整數(shù)是素?cái)?shù)，則對(duì)于任何整數(shù)x，有，有 x p 1 1 (x 1)(x 2)(x p 1) (mod p)。(2)wilson定理定理 (1)! 10(mod )pp 證明證明: : (1)由由fermat定理，數(shù)定理，數(shù)1, 2, , p 1是同余方程是同余方程x p 1 1 (mod p)，即，即x p 1 1 0(mod p)的解，的解， 因此，利用定理因此，利用定理2可得可得 x p 1 1 (x 1)(x 2)(x p 1) fk(x) (mod p)其中其中fk(x)an1，所以所以 x p 1 1 (x 1)(x 2)(x p 1) (mod p)。(2)(1)xp 在在中中取取即即得得證證. .2021-11-3皖西學(xué)院 數(shù)理系58定理定理4 4 同余方程同余方程(1)的解數(shù)的解數(shù) n