初等數(shù)論第五章同余方程_第1頁(yè)
初等數(shù)論第五章同余方程_第2頁(yè)
初等數(shù)論第五章同余方程_第3頁(yè)
初等數(shù)論第五章同余方程_第4頁(yè)
初等數(shù)論第五章同余方程_第5頁(yè)
已閱讀5頁(yè),還剩38頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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è)二次剩余的

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論