初等數(shù)論第五章同余方程

1、第五章同余方程本章主要介紹同余方程的基礎(chǔ)知識(shí)，并介紹幾類特殊的同余方程的解 法。第一節(jié)同余方程的基本概念本節(jié)要介紹同余方程的基本概念及一次同余方程。在本章中，總假定 m是正整數(shù)。定義1設(shè)f(x) = anxn +aix +ao是整系數(shù)多項(xiàng)式，稱f(x)三 0 (mod m)(1)是關(guān)于未知數(shù)x的模m的同余方程，簡(jiǎn)稱為模 m的同余方程。若an 0 (mod m),則稱為n次同余方程。定義2設(shè)xo是整數(shù)，當(dāng)x = xo時(shí)式(1)成立，則稱xo是同余方程(1)的 解。凡對(duì)于模 m同余的解，被視為同一個(gè)解。同余方程(1)的解數(shù)是指它的關(guān)于模 m互不同余的所有解的個(gè)數(shù)，也即在模m的一個(gè)完全剩余系中的解的

2、個(gè)數(shù)。由定義2,同余方程(1)的解數(shù)不超過(guò) m。定理1 下面的結(jié)論成立：(i )設(shè)b(x)是整系數(shù)多項(xiàng)式，則同余方程(1)與f(x) b(x)三 b(x) (mod m) 等價(jià)；(ii)設(shè)b是整數(shù)，(b, m) = 1,則同余方程與bf(x)三 0 (mod m)等價(jià)；(iii)設(shè)m是素?cái)?shù)，f(x) = g(x)h(x), g(x)與h(x)都是整系數(shù)多項(xiàng)式，又設(shè)xo是同余方程(1)的解，則xo必是同余方程g(x)三 o (mod m) 或 h(x)三 o (mod m)的解。證明留做習(xí)題。下面，我們來(lái)研究一次同余方程的解。定理2設(shè)a, b是整數(shù)，a宇0 (mod m)。則同余方程ax 三 b

3、 (mod m)(2)有解的充要條件是(a, m) bo若有解，則恰有 d = (a, m)個(gè)解。證明顯然，同余方程(2)等價(jià)于不定方程ax +my = b,(3)因此，第一個(gè)結(jié)論可由第四章第一節(jié)定理1得出。若同余方程(2)有解xo,則存在方程(3)的全部解是x =x0=y 二 y0 I由式(4)所確定的x都滿足方程yo,使得-t (a,m)a,tw Z。- t(a,m)(2)。記 d = (a, m),以及(3)的解,此時(shí),(4)t = dq +r, qeZ, r = 0,1,2,，d 1,則m _ m ,x = xo +qm 十一r =x0 十一r (mod m), 0 r d - 1。

4、dd容易驗(yàn)證，當(dāng)r = 0,1,2,，d 1時(shí)，相應(yīng)的解m 2m . (d T)m xo, xo 十一,xo 十一,xo +ddd對(duì)于模m是兩兩不同余的，所以同余方程(2)恰有d個(gè)解。證畢。在定理的證明中，同時(shí)給出了解方程(2)的方法，但是，對(duì)于具體的方程(2),常常可采用不同的方法去解。例1 設(shè)(a, m) = 1 ,又設(shè)存在整數(shù) y,使得a b +ym,則_ b ym ,.、x (mod m)是方程(2)的解。解直接驗(yàn)算，有ax =b +ym =b (mod m)。1。8注：例1說(shuō)明，求方程(2)的解可以轉(zhuǎn)化為求方程my 三-b (mod a)(5)的解，這有兩個(gè)便利之處：第一，將一個(gè)對(duì)于

5、大模m的同余方程轉(zhuǎn)化為一個(gè)對(duì)于小模 a的同余方程，因此有可能通過(guò)對(duì)模 a的完全剩余系進(jìn)行逐個(gè)驗(yàn)證，以求出方程 (5)和(2)的解；第二，設(shè) m三r (mod a), r 0,且(a, m) = 1 , a1是m對(duì)卞a a的最小非負(fù)剩余，則同余 方程a1x 三 b m (mod m)(7)a等價(jià)于同余方程(2)。解 設(shè)x是(2)的解，則由m =am+a1得到 aa1 x =(m -am) x三ax*-bm (mod m),aa a即x是同余方程(7)的解。但是由假設(shè)條件可知同余方程(2)與(7)都有且只有一個(gè)解。所以這兩個(gè)同余方程等價(jià)。注：用本例的方法，可以將同余方程(2)轉(zhuǎn)化成未知數(shù)的系數(shù)更小

6、一些的同余方程，從而易于求解。例4 解同余方程 6x三7 (mod 23)。解由例3,依次得到6x 三 7 (mod 23) u 5x 三7 3 三 2 (mod 23)二 3x 三 2 4 三 8 (mod 23)u 2x 三-8(7)三 10 (mod 23)y x 三 5 (mod 23)。例5 設(shè)(a, m) = 1 ,并且有整數(shù)d 0使得a 三 1 (mod m),則同余方程(2)的解是、1x =ba(mod m)。解直接驗(yàn)證即可。注：由例5及Euler定理可知，若(a, m) = 1 ,則x 三 ba (m) -1 (mod m)總是同余方程(2)的解。例6解同余方程81x3 +

7、24x2 + 5x + 23 三 0 (mod 7)。解原同余方程即是32-3x + 3x 2x+ 2 三 0 (mod 7)。用x = 0 , 41, 2, 3逐個(gè)代入驗(yàn)證，得到它的解是xi 三 1, x2 三 2, x3 三一2 (mod 7)。注：本例使用的是最基本的解同余方程的方法，一般說(shuō)來(lái)，它的計(jì)算 量太大，不實(shí)用。例7解同余方程組3x +5y 三 1(mod 7)/ 。2x -3y 三2(mod 7)解 將(8)的前一式乘以2后一式乘以3再相減得到19y 三 Y (mod 7),5y 三 4 (mod 7),y 三 2 (mod 7)。再代入(8)的前一式得到3x + 10 三 1

8、 (mod 7),x 三 4 (mod 7)。即同余方程組(8)的解是x三4, y三2 (mod 7)。例8 設(shè)a1，a2是整數(shù)，m1，m2是正整數(shù)，證明：同余方程組|x 三a1 (mod m1)(8)(9)x 三 a2 (mod m2)111有解的充要條件是ai 三a2 (mod (mi, m2)。(10)若有解，則對(duì)模mi, m2是唯一的，即若 xi與X2都是同余方程組(9)的 解，貝Uxi 三X2 (mod mi, m2)。(11)解 必要性是顯然的。下面證明充分性。若式(I0)成立，由定理2,同余方程m2y 三 ai - a2 (mod mi)有角y y 三y0 (mod mi), 記

9、 xo = a2 +m2yo,貝Uxo 三 a2 (mod m2) 并且xo = a2 +m2yo 三a2 +ai -a2 三ai (mod mi), 因此xo是同余方程組的解。若xi與x2都是方程組(9)的解，則xi 三x2 (mod mi), xi 三x2 (mod m2), 由同余的基本性質(zhì)，得到式 (ii)。1 .證明定理io2 .解同余方程：(i ) 3ix 三 5 (mod i7);(ii ) 32i5x 三 i60 (mod 235)。3 .解同余方程組：4.設(shè)p是素?cái)?shù)，0 aa -4x 三b(i)3x +5y 三38(mod 47)x - y 三i0(mod 47) p,證明：

10、(p i)(p 2)(p a i)a!(mod p)。是同余方程 ax =b (mod p)的解。5 .證明：同余方程 aixi +a2十十a(chǎn)nxn三b (mod m)有解的充要條件 是iii(ai, a2,，an, m) = d b。若有解，則恰有dmn個(gè)解，mod m。6 . 解同余方程：2x + 7y三5 (mod 12)。第二節(jié)孫子定理本節(jié)要討論同余方程組_|x 三 a1 (mod m1) x =a2(mod m2) d。x 三ak(mod mJ在第一節(jié)的例題中，我們已討論了k = 2的情形。下面考察一般情形。定理1(孫子定理)設(shè)mi, m2,，mk是正整數(shù)，(mi，mj) = 1,

11、1 i, j k, i =j。(2)記m = mim2mk , Mi = , 1 Mi Mk, mi則存在整數(shù) MJ (1 i Mk),使得MiMj 三 1 (mod mi),(3)MiMi三 0 (mod mi), 1 j k, i 刊，(4)并且 kxo 三 ai M i M i (mod m)(5)i 1是同余方程組(1)對(duì)*H m的唯一解，即若有 x使方程組(1)成立，則x 三 xo (mod m)。(6)證明 由式(2),有(Mi, mi) = 1 ,因此利用輾轉(zhuǎn)相除法可以求出Mi與yi ,使得MiMi yimi = 1,即MJ滿足式(3)和式(4)。由式(3)與式(4),對(duì)于1 i

12、 k,有xo 三aiMiMJ 三ai (mod mi), 1 Mi Mk。若x也使式成立，則x 三xo (mod mi), 1 i k,因此x 三xo (mod mi, m2,，mk)。但是，由式(2)可知m，m2,，m = m,這就證明了式(6)。證畢。定理2在定理1的條件下，若式(1)中的ai, a2,，ak分別通過(guò)模mi, m2, ，mk的完全剩余系，則式(5)中的x0通過(guò)模m1m2mk的完全剩余系。證明 這是第二章第二節(jié)習(xí)題 6的特例。證畢。定理3同余方程組(1)有解的充要條件是ai 三aj (mod (mi, mj), 1 Ei, j no(7)證明 必要性是顯然的。下面證明充分性。

13、當(dāng)n = 2時(shí)，由第一節(jié)例8可知充分性成立。假設(shè)充分性當(dāng)n = k時(shí)成立。假設(shè)式(7)當(dāng)n = k +1時(shí)成立。我們來(lái)考慮同余方程組x 三ai (mod mi), 1 i k + 1。由第一節(jié)例8,存在bk,使得x三bk (mod mk, mk+1 )滿足同余方程組x 三ak (mod mk), x 三 ak + 1 (mod mk + 1)。在同余方程組x =a1 (mod m1) x =a - (mod m)x =b(modmk,mk 1)中，由式(7)有ai 三aj (mod (mi, mj), 1 i, j k - 1,因此，若能證明ai 三bk (mod (mi, mk, mk +1

14、), 1 Mi Mk 1。(8)則由歸納假設(shè)就可以證明充分性。由bk的定義，有ak 三bk (mod mk), ak + 1 三bk (mod mk + 1)(9)而且，由于假設(shè)式(7)當(dāng)n = k+ 1時(shí)成立，所以，對(duì)于1 i k - 1有ai 三ak (mod (mi, mk), ai 三ak + 1 (mod (mi, mk + 1),由此及式(9)得到，對(duì)于1 i k 1,有ai 三bk (mod (mi, mk), ai 三bk (mod (mi, mk + 1)。 因此ai 三bk (mod (mi, mk), (mi, mk + 1)。由上式及第一章第六節(jié)例 2,就得到式(8)。

15、證畢。定理4 設(shè)m = m1m2mk ,其中m1，m2,，mk是兩兩互素的正整數(shù)，f(x)是整系數(shù)多項(xiàng)式，以 T與Ti (1 i Wk)分別表示同余方程f(x)三 0 (mod m)(10)與f(x)三 0 (mod mi)(11)的解的個(gè)數(shù)，則 T = T1T2Tk。證明由第二章第一節(jié)定理 5可知，同余方程(10)等價(jià)于同余方程組f(x)三 0 (mod mi), 1 i ko(12)對(duì)于每i (1 i Mk),設(shè)同余方程(11)的全部解是x 三x1(i), x2i),，xTi)(mod mi),(13)則同余方程組(12)等價(jià)于下面的T1T2Tk個(gè)方程組：/_ . 、x =xj (mod

16、m1)x 三x(2)(mod m2)4j22 ,(14)x 三x(?(mod mk)其中x7通過(guò)式(13)中的數(shù)值，即通過(guò)同余方程(11)的全部解。由孫子定理，對(duì)于選定的每一組 x(1),x(2),，x(k) ,同余方程組(14)j1j2jk對(duì)卞m有唯一解，而且，由定理 2,當(dāng)每個(gè)xji)通過(guò)(13)式中的值時(shí)，所得到的丁1丁2一1卜個(gè)同余方程組(14)的解對(duì)于模m都是兩兩不同余的。 證畢。由定理4及算術(shù)基本定理，解一般模的同余方程可以轉(zhuǎn)化為解模為素?cái)?shù)哥的同余方程。例1求整數(shù)n,它被3, 5, 7除的余數(shù)分別是1, 2, 3。解 n是同余方程組n 三 1 (mod 3), n 三 2 (mod

17、 5), n 三 3 (mod 7)的解。在孫子定理中，取mi = 3, m2 = 5, m3 = 7, m = 357 = 105,Mi = 35, M2 = 21 , M3 = 15,Mi= -1, M2= 1, M3= 1 , 則n 三 1 35 (-1) + 2 21 1 + 3 15 1 三 52 (mod 105), 因此所求的整數(shù) n = 52 + 105t, Z。例2解同余方程(15)(16)(17)(18)5x2 + 6x + 49 三 0 (mod 60)。解 因?yàn)?0 = 3 4 5,所以，同余方程(15)等價(jià)于同余方程組5x2 + 6x + 49 三 0 (mod 3)

18、5x2 + 6x + 49 三 0 (mod 4)5x2 + 6x + 49 三 0 (mod 5)。分別解同余方程(16), (17), (18)得到解x1三 1, x2(1)三-1 (mod 3), x1三 1, x2三-1 (mod 4),x1(3)三 1 (mod 5),這樣，同余方程(15)的解x可由下面的方程組決定：x 三 a1 (mod 3), x 三a2 (mod 4), x 三a3 (mod 5), 其中a1 二 1或-1, a2 = 1或一1, a3 = 1。利用孫子定理，取m1 = 3, m2 = 4, m3 = 5, m = 60, M1 = 20, M2 = 15,

19、M3 = 12, M1 = 2, M2= 1, M3= 3, 則x 三40a1 15a2 + 36a3 (mod 60)。將a1，a2, a3所有可能的取值代入上式，得到方程(15)的全部解是x1 三40 1 15 1 + 36 1 三 1 (mod 60),x2 三 40 (T) 15 1 + 36 1 三19 (mod 60),x3 三40 1 15 (-1) + 36 1 三 31 (mod 60), x4 三 40 (T) 15(1) + 36 1 三 11 (mod 60)。x 三 b1(mod 5)1.解同余方程組:x =b2(mod 6)|x =b3(mod 7)x =b4(mo

20、d11)。X-x 三 8(mod15)2.解同余方程組:x 三5(mod 8)x 三 13(mod 25)。3.有一隊(duì)士兵，若三人一組，則余 1人；若五人一組，則缺 2人； 若十一人一組，則余 3人。已知這隊(duì)士兵不超過(guò) 170人，問(wèn)這隊(duì)士兵 有幾人？11 一.4 .求一個(gè)最小的自然數(shù) n,使得它的,是一個(gè)平萬(wàn)數(shù)，它的1是一個(gè)23立方數(shù)，它的-是一個(gè)5次方數(shù)。 55 .證明：對(duì)于任意給定的 n個(gè)不同的素?cái)?shù)P1, P2,，Pn,必存在連續(xù) n個(gè)整數(shù)，使得它們中的第k個(gè)數(shù)能被pk整除。6 . 解同余方程：3x2 + 11x 20 三 0 (mod 105)。第三節(jié)模p的同余方程在第二節(jié)中，我們已經(jīng)看

21、到，求解模m的同余方程可以轉(zhuǎn)化為對(duì)模 pa的同余方程的求解。本節(jié)要對(duì)模 p：的同余方程做進(jìn)一步討論。容易看出，若xO是同余方程(2)f(x)三 0 (mod p )的解，則它必是方程 一 1f(x) = 0 (mod p )的解，因此，必有與 x0相應(yīng)的方程(2)的某個(gè)解x1，使1x0 =x1 (mod p ),-1 , x0 = x1pt0,115此處，to是某個(gè)適當(dāng)?shù)恼麛?shù)。這提示我們：可以從方程(2)的解中去求方程(i)的解。于是，現(xiàn)在的問(wèn) 題是，對(duì)于方程(2)的每個(gè)解xi,是否必有方程(i)的解與之對(duì)應(yīng)？若 有，如何去確定它？多項(xiàng)式，又設(shè)xi是同余方程(2)的一個(gè)解。以 (x)表示f(x

22、)的導(dǎo)函數(shù)。(i )若f (xi)手0 (mod p),則存在整數(shù)t,使得i,x = xi，p t定理 設(shè)p是素?cái)?shù)，a之2是整數(shù)，f(x) = anxn +aix+ao是整系數(shù)是同余方程(i)的解。(ii) 若 f (xi)三 0 (mod p),并且 f(xi)三 0 (mod p 則對(duì)于 t = 0, i, 2, ，p i,式(3)中的x都是方程(i)的解。證明 我們來(lái)說(shuō)明，如何確定式(3)中的t,使xi +pQ/t滿足同余方程 ，即要使an(xi+pa/t)n+an(xi + p/t)n,+ai(xi+pa,t)+a0 三 0 (mod pj, (4)f(xi) +p ，tf (xi)三

23、 0 (mod p ),f (xi)tf (xi)三瓦i (mod p)。p-下面考慮兩種情形。(i ) 若f (x)于0 (mod p),則關(guān)于t的同余方程 有唯一解t三to (mod p),即 t = to +pk (k三Z),于x 三 xi p - 一 (mod p )是同余方程(1)的解。(ii) 若f (xi)三0 (mod p),并且f(xi)三0 (mod p0),則式(5)對(duì)于任意的 整數(shù)t成立，即同余方程(5)有p個(gè)解t 三i (mod p), 0 i p - i。于是x三xi +pi (mod p% 0 Wi 1,同余方程(1)與(6)的解數(shù)相同。證明留做習(xí)題。例1解同余方

24、程x3 + 3x - 14 三 0 (mod 45)。解原同余方程等價(jià)于同余方程組x3 + 3x - 14 三 0 (mod 9),(7)x3 + 3x - 14 三 0 (mod 5)。(8)先解同余方程(7)。容易驗(yàn)證，同余方程 x3 + 3x - 14三0 (mod 3)的解是 x 三 2 (mod 3)。令x = 2 + 3t并代入方程(7),得到(2 +3t)3 + 3(2 + 3t) -14 三 0 (mod 9),(9)容易看出，這是一個(gè)對(duì)于任何整數(shù)t都成立的同余式，所以，方程 (9)的解是t三0, 1, 2 (mod 3),于是方程 的解是x 三 2, 5, 8 (mod 9)

25、。(10)再解同余方程(8)。用x = 0, 1, 2, 3, 4去驗(yàn)證，得到(8)的解是x 三 1, 2 (mod 5)。因此，原同余方程的解是下面六個(gè)同余方程組的解：x 三a1(mod 9), a1 = 2 , 5, 8,x 三a2 (mod 5), a2 = 1,2。利用孫子定理解這六個(gè)方程組，記m1 = 9 , m2 = 5 , m = 45, M1 = 5, M2 = 9 , M/ = 2, M2 = -1,X3 三 105 9 1 三 41 (mod 45),X4 三 105 92 三 32 (mod 45),X5 三 108 91 三 26 (mod 45),X6 三 108 9

26、2 三 17 (mod 45)。例2解同余方程2x2 + 13x 34 三 0 (mod 53)。(11)解容易驗(yàn)證，同余方程2x2 + 13x 34 三 0 (mod 5)(12)有兩個(gè)解 x三一1, 2 (mod 5)。令x = -1 5t,(13)代入同余方程2x2 +13 34 三 0 (mod 52),(14)得到2(-1 + 5t)2 + 13(-1 + 5t) 34 三 0 (mod 25),-45 + 45t 三 0 (mod 25),9t 三 9 (mod 5), t 三 1 (mod 5)。(15)于是，將式(15)與式(13)聯(lián)合，得到方程(14)的解x = -1 + 5

27、(1 + 5t1) = 4 + 25t1, t1 WZ。(16)將式(16)中的x代入同余方程(11),得到2(4 + 25t1)2 +13(4 + 25t1) 34 三 0 (mod 53),50 + 725t1 三 0 (mod 53),2 + 29t1 三 0 (mod 5),t1 三 2 (mod 5)。將上式與(16)聯(lián)合，得到同余方程(11)的一個(gè)解x = 4 + 25t1 = 4 + 25(2 + 5t2)三 54 (mod 53)。(ii)從同余方程(12)的另一個(gè)解x三2 (mod 5)出發(fā)利用上述方法，可 以求出同余方程(11)的另一個(gè)解。(略，請(qǐng)讀者補(bǔ)足)。例3解同余方程

28、x2 三 1 (mod 2k), k三N。(17)解 若k = 1,則方程(17)的解是x三1 (mod 2)。若k = 2,則方程(17)的解是x三1, -1 (mod 4)。若k之3,則同余方程(17),即x - 1 = (x +1)(x -1)三 0 (mod 2 k),的解必是奇數(shù)，設(shè) x = 2y + 1,則同余方程(1)成為(2y + 2)2y 三 0 (mod 2k),y(y +1)三 0 (mod 2k-2)。(18)同余方程(18)的解是y1三0, y2三1 (mod 2k,)，即y1 = 2u, y2 = -1 + 2 v, u, vWZ,所以，方程(17)的解是x1 =

29、2 -u + 1, x2 = 2 -v -1, u, vWZ, 即x 三1, 1 + 2k,，-1, -1 + 2k(mod 2k)。例4 解同余方程x2三2 (mod 7 3)。解設(shè)x是這個(gè)同余方程的解，則它可以表示成x = x0 + 7x1 + 72x2, 0 Wxj E 6, 0 i n。第四節(jié)素?cái)?shù)模的同余方程在上節(jié)中，我們證明了，對(duì)于素?cái)?shù) p,模p邪J同余方程的求解可以轉(zhuǎn) 化為模p的同余方程的求解。本節(jié)要對(duì)素?cái)?shù)模的同余方程做些初步研 究。以下，設(shè)f(x) = anxn +aix+ao是整系數(shù)多項(xiàng)式，p是素?cái)?shù)，p|%。定理1 設(shè)k 1,在上式中，令 x = xi (i = 2, 3, k

30、),則有0 三 f(xi)三(xi -x1)f1(xi) (mod p)。(4) 由于x2，xk對(duì)于模p是兩兩不同余的，所以，上式給出fi(xi)三 0 (mod p), i = 2,，k。(5)由此及歸納法，即可證明定理。證畢。推論 若p是素?cái)?shù)，則對(duì)于任何整數(shù)x,有xp 1 1 三(x 1)(x - 2)(x -p + 1) (mod p)。證明 由Fermat定理(第二章第四節(jié)定理2),數(shù)1,2,，p 1是同余方程xp 1 三 1 (mod p)的解，因此，利用定理 1即可得證。定理2同余方程(1)的解數(shù)no證明 假設(shè)同余方程(1)有n + 1個(gè)不同的解x 三xi (mod p), 1 i

31、 Wn +1。由定理 1,有 f(x)三an(x Xi)(x xn) (mod p),因此0 三f(xn + 1)三an(xn + 1 -Xi)(Xn + 1 -Xn) (mod p)。(6)由于pfan, xn + 1平Xi (mod p), 1 i n,所以式(6)不能成立。這個(gè)矛 盾說(shuō)明同余方程(1)不能有n + 1個(gè)解。證畢。推論 若同余方程bnxn十+b。三0 (mod p)的解數(shù)大于n,則pl bi, 0 i n(7)證明 若式不成立，設(shè)p |bd, d n, p bi, d j n0則bnxn + +b。三bdxd + +b。三 0 (mod p)。(8)由定理2,同余方程(8)

32、的解數(shù)不大于d,因而不大于n,這與假設(shè)矛盾。 因此，式(7)必成立。證畢。定理3同余方程(1)或者有p個(gè)解，或者存在次數(shù)不超過(guò) p - 1的整系 數(shù)多項(xiàng)式r(x),使得同余方程 與r(x)三0 (mod p)等價(jià)。證明 由多項(xiàng)式除法可知，存在整系數(shù)多項(xiàng)式g(x)與r(x),使得f(x) = g(x)(xp -x) +r(x)。(9)由Fermat定理，對(duì)于任意的整數(shù)x,有xp三x (mod p),因此，如果r(x) 的系數(shù)都是p的倍數(shù)，則對(duì)于任意的整數(shù)x, f(x)三0 (mod p),即同余方程(1)有p個(gè)解。如果r(x)的系數(shù)不都是p的倍數(shù)，則r(x)的次數(shù)不超 過(guò)p-1。由式(9)看出，

33、對(duì)于任意的整數(shù) x, f(x)三r(x) (mod p),即同余 方程(1)與r(x)三0 (mod p)等價(jià)。證畢。定理4設(shè)n Ep,則同余方程f(x) = xn +an _ixn,+ +aix +ao 三 0 (mod p) (10) 有n個(gè)解的充要條祚是存在整數(shù)多項(xiàng)式q(x)和r(x), r(x)的次數(shù) n,使xp -x = f(x)q(x) +pr(x)。(11)證明 必要性 由多項(xiàng)式除法，存在整系數(shù)多項(xiàng)式q(x)與r(x), ri(x)的次數(shù) n,使得xpx = f(x)q(x) +門(x)。(12)若同余方程(10)有n個(gè)解x三xi (mod p )(1 i n),則由式(12)和

34、Fermat 定理，得到門(xi)三 0 (mod p), 1 i no由此及定理2推論，可知r1(x)的系數(shù)都能被p整除，即門(x) = p r(x), 其中r(x)是整系數(shù)多項(xiàng)式。這證明了式 (11)。 充分性 若式(11)成立，由Fermat定理，對(duì)于任何整數(shù)x,有0 三xp x 三f(x)q(x) (mod p),(13)即同余方程f(x)q(x)三 0 (mod p)有p個(gè)解，但是，q(x)是p -n次多項(xiàng)小，所以由定理2,方程q(x)三0(mod p)的解數(shù) 一.、.、 k、一 1.*、3 . 設(shè)(a, m) = 1 , k與m是正整數(shù)，又設(shè) xo三a (mod m),證明同余方x

35、k 三 a(mod m)的一切解x都可以表示成x三yxo (mod m),其中y滿足同余方程yk三1 (mod m)。4 .設(shè)n是正整數(shù)，p是素?cái)?shù)，(n, p 1) = k,證明同余方程xn三1 (mod p)有k個(gè)解。5 .設(shè)p是素?cái)?shù)，證明：(i ) 對(duì)于一切整數(shù) x, xp,1 三(x 1) (x - 2)(xp+ 1) (mod p);(ii ) (p -1)!三1 (mod p)。6 .設(shè)p至3是素?cái)?shù)，證明：(x 1)(x- 2)(xp +1)的展開式中除首項(xiàng)及常數(shù)項(xiàng)外，所有的系數(shù)都是p的倍數(shù)。第五節(jié) 素?cái)?shù)模的二次同余方程設(shè)p是素?cái)?shù)，我們來(lái)研究素?cái)?shù)模p的二次同余方程ax2+bx+c 三

36、 0 (mod p)。(1)如果p = 2,則可以直接驗(yàn)證 x三0或1 (mod 2)是否方程(1)的解。如果(a, p) = p,則方程(1)成為一元一次同余方程。因此，只需考察 p 2, (a, p) = 1的情形。此時(shí)，因?yàn)?4a, p) = 1 ,所以，方程(1)等價(jià)于方 程4a2x2 + 4abx + 4ac 三 0 (mod p),即(2ax + b)2 三 b2 4ac (mod p)。這樣，研究方程(1)歸結(jié)為對(duì)方程x2 三 n (mod p)(2)的研究。定義1 給定整數(shù)p,對(duì)于任意的整數(shù)n, (n, p) = 1,若方程(2)有解， 則稱n是模p的二次剩余，記為 nWQR(

37、p);否則，稱n是模p的二次 非剩余，記為n三QNR(p)。顯然，若n1三n2 (mod p),則它們同是模p的二次剩余(或二次非剩余)， 因此，在談到模p的二次剩余(或二次非剩余)時(shí)，把 n1和上看作是 同一個(gè)。以下，在本節(jié)中，總假定 p是奇素?cái)?shù)。定理1 若(n, p) = 1,則(i ) n是模p的二次剩余的充要條件是p 1n 2 三 1 (mod p);(3)(ii )若n是模p的二次剩余，則方程(2)有兩個(gè)解；(iii) n是模p的二次非剩余的充要條件是p 1n 2 三一1 (mod p)。(4)證明 結(jié)論(i )與(五)由第四節(jié)定理5直接推出。(iii)若(n, p) = 1,由第二

38、章第四節(jié)定理1,有np三 1 (mod p),p 1p-1(n 2 +1)(n 2 - 1)三 0 (mod p)。(5)因?yàn)閜是奇素?cái)?shù)，所以式(3)式與式(4)必有且僅有一個(gè)成立，利用結(jié)論(i ),可得到結(jié)論(血)。證畢。定理2 模p的簡(jiǎn)化系中，二次剩余與二次非剩余的個(gè)數(shù)都是衛(wèi)二1 ,2而且，模p的每個(gè)二次剩余與且僅與數(shù)列色 22,，(_LZ1)2(6)中的一個(gè)數(shù)同余。證明 顯然，數(shù)列(6)包含了模p的全部二次剩余。為了證明定理，只需證明式(6)中的任何兩個(gè)數(shù)對(duì)模 p不同余。對(duì)任意白整數(shù) k, s, 1 k s W_p二1 ,若2k2 三s2 (mod p),(7)則p k+s或p k-s。

39、這都是不可能的，而以式 (7)不能成立。證畢。定義2給定奇素?cái)?shù)p,對(duì)于整數(shù)n,定義Legendre符號(hào)為。當(dāng)(n,p)=1;(n) =1,當(dāng)nWQR(p)；p 11,當(dāng) nWQNR(p)。例如，由定理1,1與4是模5的二次剩余，2與3是模5的二次非剩 余，于是（1） =1, （2）（3）=-1，=1,定理3 設(shè)p是奇素?cái)?shù)，n是整數(shù)，則p 1（i ）（）三n 2 （mod P）；P(ii)若 n 三 n1 (mod p),則(iii)3)證明1 -1初（一）=1，（一）=（-1） 2 ； pp對(duì)任意白整數(shù)m, 1 i k,有a1a2 aka1 a2a x（7）=（力卓卓。結(jié)論（i ）與（ii ）

40、容易由定義2及定理1得到。133為了證明結(jié)論（iii）,只需證明其中的第二個(gè)等式。由結(jié)論 （i）,有-1(曹)pj2 (mod p),其中同余式兩端都只能取值力或-1,因此，結(jié)論（話）的第二個(gè)等式 成立。乂 442 = a1-2- a2Tp 1 ak-最后，由結(jié)論（i ）,有,a1a2 ak、()二(a1a2ak)p三（；）（放）（半）（mod p）。所以它們必相等。p 三 1（mod 4）;由于上式首端與末端都是只取值-1, 0或1的整數(shù),結(jié)論（iv ）得證。證畢。推論設(shè)p是奇素?cái)?shù)，則-1WQR（p）的充要條件是T WQNR（p）的充要條件是 p三3（mod 4）。例1判斷方程x2三5 （m

41、od 11）有沒(méi)有解。解由定理2,因?yàn)?11()三5H =55 三5 54 三5 32 三 1 (mod 11), 11方程有解。例2 設(shè)p是奇素?cái)?shù)，p三1 (mod 4),則(11%)2= 1 (mod P)解 由Wilson定理(第二章第二節(jié)例 3),有p-1 三(p-1)!=(-1)(p -1)!p 1p T p 1=(-1) 2 1 2( p -1)22=(-p2-1)!)2(mod p)。定理2和例2說(shuō)明，當(dāng)素?cái)?shù)p三1(mod 4)時(shí)，模p的所有二次剩余之積對(duì)*H p同余于一1。此外，我們還得到了方程x2三一1 (mod p)的解。例3 設(shè)n是整數(shù)，證明n2 +1的任何奇因數(shù)都是 4

42、m + 1 (mZ)的 形式。解 由于任何奇數(shù)都可表成奇素?cái)?shù)之積，而且任意多個(gè)形如4m+1的整數(shù)之積也具有 4m + 1的形式，我們只需證明：若素?cái)?shù) p是n2 +1的 因數(shù)，則p具有4m + 1的形式。事實(shí)上，若p n2 +1,則n 三一1 (mod p), 即-1WQR(p)。由定理3推論得出所需結(jié)論。例4 形如4m +1 (kZ)的素?cái)?shù)有無(wú)窮多個(gè)。解 用反證法。假設(shè)只有有限多個(gè)形如4k+1的素?cái)?shù)p1，p2,，pk,記一 2N = 4(p1p2 pk)1由例2,必有奇素?cái)?shù)q, q三1 (mod 4) , q N,顯然q #pi (1 i k), 這與假設(shè)矛盾，所以形如4m + 1的素?cái)?shù)有無(wú)窮

43、多個(gè)。例5 若a三1 (mod 4) , 2 b,并且b沒(méi)有形如4k + 3 (HZ)的素因 數(shù)，證明方程y2 = x3 - a3 -b2(8)沒(méi)有整數(shù)解。解 用反證法。假設(shè)有整數(shù)x, y滿足方程(8)。若2 |x,則由式(8)得則y2三-l(mod 4)這不可能。若x三3 (mod 4),則由式(8)得到y(tǒng)2 三x3 - a3 -b2 三 33 - 13 - 0 三 2 (mod 4),這是不可能的。若 x 三 1 (mod 4),貝Ux2+ax+a2 三 1 +a+a2 三 3 (mod 4),(9)因此，必有素?cái)?shù) p三3 (mod 4),使得p x2 +ax +a2。(10)由式(8)與

44、式(10)得到y(tǒng)2 = x3-a3-b2 三-b2(mod p),(11)即 爐WQR(p)。但是，由假設(shè)，p | b2,所以有(手管)(1) = T這與式(11)矛盾。例6 設(shè)p是素?cái)?shù)，證明：數(shù)例 1,2,，p- 1中的模p的二次剩余之 和是p( p2 -1)S 一24解 對(duì)于整數(shù)k, 1 k M衛(wèi)二1 ,記 2k2 = pqk+k, qke Z , 1 WrkWp_1, k2則qk =,并且，由定理2,有pp -4p -4p -122 c 2 k 2S = rk = k - p k 1 k 1k T p- p(p2 -1)24p k2 pJ。k 1 p例7 設(shè)p是奇素?cái)?shù)，證明：若同余方程x

45、4 十 1 三 0 (mod p)(12)有解，則 p三1 (mod 8)。解 設(shè)x三a (mod p)是方程(12)的解，則a4 三 T (mod p),(13)a8 三 1 (mod p)。(14)以d0表不使ad 三 1 (mod p)(15)成立的最小正整數(shù) d,記8 = qdo +r, 0 r do 一 1,則由式(14)與式(15) 得到1 三a8 = aqdo * 三 ar (mod p),因此，若r豐0,則上式與do的定義矛盾。所以r = 0,即do 8,這樣， do的取值只可能是1, 2, 4或8。由式(13)可知do = 8。用同樣方法以及 Fermat定理可以證明 8 p - 1即p三1 (mod 8)。習(xí)題五1 .同余方程x2三3 (mod 13)有多少個(gè)解？2 .求出模23的所有的二次剩余和二次非剩余。3 .設(shè)p是奇素?cái)?shù)，證明：模 p的兩個(gè)二次剩余的