1、Good is good, but better carries it.精益求精，善益求善。數論算法教案 4章(二次同余方程與平方剩余)-二次同余方程與平方剩余內容二次同余方程，平方剩余模為奇素數的平方剩余勒讓德符號、雅可比符號二次同余方程的求解要點二次同余方程有解的判斷與求解一般二次同余方程二次同余方程bxc0（modm），（a0（modm）（1）化簡設m，則方程（1）等價于同余方程問題歸結為討論同余方程bxc0（mod），（pa）（2）化為標準形式p2，方程（2）兩邊同乘以4a，44abx4ac0（mod）4ac（mod）變量代換，y2axb（3）有4ac（mod）（4）當p為奇素數時，方

2、程（4）與（2）等價。即兩者同時有解或無解；有解時，對（4）的每個解，通過式（3）（x的一次同余方程，且（p,2a）1，所以解數為1）給出（2）的一個解，由（4）的不同的解給出（2）的不同的解；反之亦然。兩者解數相同。結論：只須討論以下同余方程a（mod）（5）【例】化簡方程7x25x20（mod9）為標準形式。（解）方程兩邊同乘以4a4728，得196x2140 x560（mod9）配方(14x5)225560（mod9）移項(14x5)281（mod9）變量代換y14x5得y20（mod9）（解之得y0,3，從而原方程的解為x(y5)(y5)2(y5)2y102y17,1,54,1,2（m

3、od9）二次剩余【定義4.1.1】設m是正整數，a是整數，ma。若同余方程a（modm）（6）有解，則稱a是模m的平方剩余（或二次剩余）；若無解，則稱a是模m的平方非剩余（或二次非剩余）。問題：設正整數a是模p的平方剩余，若記方程（6）中的解為x（modm），那么此處的平方根（modm）與通常的代數方程a的解有何區別？如何判斷方程（6）有解？如何求方程（6）的解？例【例1】1是模4平方剩余，1是模4平方非剩余。【例2】1、2、4是模7平方剩余，3、5、6是模7平方非剩余。【例3】直接計算12，22，142得模15的平方剩余（實際上只要計算（12，22，72）1，4，9，10，6平方非剩余：2，

4、3，5，7，8，11，12，13，14【例4】求滿足方程E：x1（mod7）的所有點。（解）對x0，1，2，3，4，5，6分別解出y：0，1（mod7），y1，6（mod7）1，3（mod7），無解2，4（mod7），y2，5（mod7）3，3（mod7），無解4，6（mod7），無解5，5（mod7），無解6，6（mod7），無解所以，滿足方程的點為（0,1），（0,6），（2,2），（2,5）。說明：方程E：x1的圖形稱為橢圓曲線。模為奇素數的平方剩余與平方非剩余模為素數的二次方程a（modp）,(a,p)1（1）因為，故方程（1）要么無解，要么有兩個解。平方剩余的判斷條件【定理4.2.1

5、】（歐拉判別條件）設p是奇素數，(a,p)1，則（i）a是模p的平方剩余的充要條件是1（modp）（2）（ii）a是模p的平方非剩余的充要條件是1（modp）（3）并且當a是模p的平方剩余時，同余方程（1）恰有兩個解。（證）先證pa時，式（2）或（3）有且僅有一個成立。由費馬定理1（modp）10（modp）0（modp）（4）即但1或2且素數p2。所以，p能整除，但p不能同時整除和（否則，p能整除它們的最大公因子1或2）所以，由式（4）立即推出式（2）或式（3）有且僅有一式成立。（i）必要性。若a是模p的二次剩余，則必有使得a（modp），因而有（modp）。即（modp）。由于pa，所以p

6、，因此由歐拉定理知1（modp）。即（2）式成立。充分性。已知1（modp），這時必有pa。故一次同余方程a（modp）,(1bp1)（5）有唯一解，對既約剩余系(p1)/2，1，1，(p1)/2（6）由式（6）給出的模p的既約剩余系中的每個j，當bj時，必有唯一的屬于既約剩余系（6），使得式（5）成立。若a不是模p的二次剩余，則必有。這樣，既約剩余系（6）中的p1個數就可按j、xj作為一對，兩兩分完。（b1b2，則相應的解x1x2，且除了1之外，每個數的逆不是它本身）因此有由威爾遜定理知與式（2）矛盾。所以必有某一，使，由此及式（5）知，a是模p的二次剩余。（ii）由已經證明的這兩部分結論，

7、立即推出第（ii）條成立。其次，若0（modp）是方程（1）的解，則也是其解，且必有（modp）。故當(a,p)1時，方程（1）要么無解，要么同時有兩個解。（說明：本定理只是一個理論結果，當p1時，它并不是一個實用的判斷方法）小結：對于任何整數a，方程（1）的解數可能為T(x2a；p)0,1,2【例1】設p19，驗證定理4.2.1的證明過程。（解）由費馬定理知，對任何a1,2,18，都有1（mod19）。方程1（mod19）只有兩個解，即x1（mod19）。從而必有1（mod19）（視1（mod19），即）針對必要性：例如a17是模19的二次剩余，即存在6使得17（mod19）。那么必有1（m

8、od19）針對充分性：例如a6，1（mod19），驗證6是二次剩余。解方程6（mod19）,(1b18)當b1,2,3,4,5,17,18（mod19）時，方程有唯一解x6,3,2,11,5,16,13（mod19）其中556（mod19）即當b5時，x5。所以6是二次剩余。又選a8，1（mod19），驗證：解方程8（mod19）,(1b18)得188，248，398，428，5138，6148，7128，818，938，10168，11188，1278，1358，1468，15178，16108，17158，181181218(18)(24)(39)(513)(614)(712)(1016)

9、(1118)(1517)1（mod19）【例2】判斷137是否為模227的平方剩余。（解）首先，227是素數。其次，計算1（mod227）所以，137是模227的平方非剩余。【推論】設p是奇素數，(a1,p)1，(a2,p)1，則（i）若a1，a2都是模p的平方剩余，則a1a2是模p的平方剩余；（ii）若a1，a2都是模p的平方非剩余，則a1a2是模p的平方剩余；（iii）若a1是模p的平方剩余，a2是模p的平方非剩余，則a1a2是模p的平方非剩余。（證）因平方剩余的個數【定理4.2.2】設p是奇素數，則模p的既約剩余系中平方剩余與平方非剩余的個數各為(p1)2，且(p1)2個平方剩余恰與序列

10、12，22，中的一個數同余。（證）由定理4.2.1，模p的平方剩余個數等于方程1（modp）的解數。但由定理3.4.5知，方程的解數為，即平方剩余的個數是，且平方非剩余的個數是(p1)。其次，可以證明當1k1，1k2，且k1k2時，有modp。故結論成立。（定理3.4.5：設p為素數，n為正整數，np。則同余方程0modp有n個解被除所得余式的所有系數都是p的倍數）勒讓德符號目的：快速判斷整數a是否為素數p的平方剩余。勒讓德符號【定義4.3.1】設p是素數，定義勒讓德（Legendre）符號為：L(a,p)【推論】整數a是素數p的平方剩余的充要條件是1。（證）由定義4.3.1。因此，判斷平方剩

11、余轉化為計算勒讓德符號的值。【例1】直接計算，得11（注：本例仍是利用平方剩余而得到勒讓德符號值）問題：反過來，如何快速計算勒讓德符號的值，以判斷平方剩余。（勒讓德符號的）性質【性質1】（歐拉判別法則）設p是奇素數，則對任意整數a，有（modp）（證）由定理4.2.1即知。【性質2】1（證）顯然（因為方程x21（modp）始終有解x1（modp），或者由性質1立得）。【性質3】。（證）由性質1即得。【例2】1，1【推論】（證）p1（mod4）p4k11p3（mod4）p4k31另一種描述：設素數p2，則1是模p的二次剩余的充分必要條件是p1（mod4）。【性質4】（證）因x2ap（modp）x

12、2a（modp）【推論】若ab（modp），則【性質5】（證）因【推論1】【推論2】當pa時，1討論：確定a是否是模p的平方剩余就變為如何計算Legendre符號的值。上述性質可以用來計算，并由算術基本定理，設a的分解式為，（t0,1）則（t0,1）故只要能計算出，就可以計算出任意的，其中是小于p的素數。已經解決的計算：剩余的問題：，的計算。解決這些問題的基礎是下面的二次互反律（Gauss定理）。【性質6】【例3】1，1，故2是模17的平方剩余，但不是模19的平方剩余。【推論】p為奇素數，則（證）因為當p8k1時k(8k2)偶數當p8k3時(2k1)(4k1)奇數【例4】由于3171（mod8

13、），593（mod8），故1，1，即2是模31的平方剩余，但不是模59的平方剩余。【性質7】（二次互反律，高斯定理）pq且均為奇素數，則另一表示形式：說明1：符號和分別刻畫了二次同余方程q（modp）和p（modq）是否有解，即q是否是模p的二次剩余和p是否是模q的二次剩余，其中正好是模與剩余互換了位置，而性質7恰好刻畫了兩者之間的關系，故稱為二次互反律。說明2：由歐拉提出，高斯首先證明。已有一百五十多個不同的證明。由二次互反律引伸出來的工作，導致了代數數論的發展和類域論的形成。【推論】（i）設奇素數p、q中至少有一個模4為1，則方程q（modp）有解方程p（modq）有解（ii）若pq3（m

14、od4），則方程q（modp）有解方程p（modq）無解（證）（i）設p1（mod4），即p4k1，則（ii）此時，p4s3，q4t3，則【例5】判斷3是否是模17的平方剩余。（解）1所以，3是模17的平方非剩余。（不但如此，17也是3的平方非剩余，即2是3的平方非剩余）【例6】判斷同余方程137（mod227）是否有解。（解）已知137與227均為奇素數，所以1所以，方程無解。另法：1【例7】判斷同余方程1（mod365）是否有解，若有解，求解數。（解）由于365573，所以1（mod365）1所以方程有解，且解數為4。【例8】判斷同余方程2（mod3599）是否有解，若有解，求解數。（解）

15、由于35995961，所以2（mod3599）因為593（mod8），即1，故方程2（mod59）無解，從而原方程無解。【例9】證明形如4k1的素數有無窮多。（證）反證法：不然，形如4k1的素數為有限個，設為，令4b1即a也形如4k1且a（i1,2,k）。所以a為合數，設其素因數p為奇數，則1所以1為模p平方剩余。由性質3的推論，p1（mod4），即p也是形如4k1的素數。（【推論】）但顯然p（i1,2,k），矛盾（否則，且由pa知p1）。二次互反律的證明證明應用【例1】求所有奇素數p，它以3為其平方剩余。（解）即求所有奇素數p，使得1。易知p3。由二次互反律因為以及（排除偶數）知1或即p1（

16、mod12）或p1（mod12）故3是模p二次剩余p1（mod12）【例2】設p為奇素數，d是整數。若1，則p一定不能表示為的形式。（證）用反證法。設p有表達式，則由p是素數可知(x,p)(y,p)1。這是因為若(x,p)1，則必有但由1知(d,p)1，所以py2，進而py。那么p2x2，p2y2p2x2dy2p矛盾。（即(x,p)(y,p)1成立）由(x,p)(y,p)1知，1，1，從而1與題設矛盾。【性質8】同余方程的解數是。【問題】求所有奇素數p，它以5或2為其平方剩余。雅可比符號問題：在計算勒讓德符號時，若a為奇數，但非素數，如何快速計算。目的：為了快速計算勒讓德符號。雅可比符號【定義

17、4.5.1】設m是奇素數的連乘積（可以重復），對任意整數a，定義雅可比（Jacobi）符號為：J(a,m)說明：上式右端的為勒讓德符號，即J(a,m)雅可比符號形式上是勒讓德符號符號的推廣。但與勒讓德符號意義不同。兩者的本質區別：勒讓德符號可用來判斷平方剩余，但雅可比符號卻不能。即當k1時，如果J(a,m)1，則方程a（modm）無解（因為至少存在一個，使得1，即方程a（mod）無解，從而原方程a（modm）也無解），但當J(a,m)1時，方程a（modm）則不一定有解。當k1時，J(a,m)L(a,m)，即此時勒讓德符號的值與雅可比符號的值相等。因此，求勒讓德符號的值轉化為計算雅可比符號。【

18、例1】由定義4.5.1(1)(1)1但可以驗證2是模9的平方非剩余。又如當奇素數p3（mod4）時，由勒讓德符號的性質知，1是模P的非平方剩余，即方程1（modp）無解，從而方程1（mod）也無解。即1是模的平方非剩余。但若取m，則總有(1)(1)1問題：如何快速計算雅可比符號的值，以幫助加速勒讓德符號的求值過程，從而加速判斷平方剩余。（雅可比符號的）性質【性質1】若(a,m)1，則J(a,m)1；若(a,m)1，則J(a,m)0。（證）因(a,m)1時，至少有某個，即0，從而0。【例2】a15，m39，則J(a,m)00【性質2】1（證）J(1,m)1【性質3】（證）因為1故m1（mod4）

19、，即m1（mod4）（mod2）所以J(1,m)【推論】（證）m1mod4m4k113mod4m4k31【例3】1，1【性質4】（證）首先，由m和maa（modm）知maa（mod）其次，由雅可比符號和勒讓德符號性質知【推論】若ab（modm），則（證）顯然【性質5】（證）因【推論1】【推論2】當(m,a)1時，1【性質6】（證）因為11（mod64）而對任何奇數q，都有1（mod8）（i1,2,k），故（mod8）（mod2）所以J(2,m)【推論】m為奇數，則（證）因為當m8k1時k(8k2)偶數當m8k3時(2k1)(4k1)奇數【例4】1，1。【性質7】（二次互反律，高斯定理）設m、n

20、都是奇數，則或【性質8】、a為整數，則（證）設，則左邊J(n,)J(a,)J(a,)右邊這樣，計算勒讓德符號的值就轉化為了計算雅可比符號的值。而后者的求值要比前者快了許多。【例5】用雅可比符號計算：(i)L(51,71)(ii)L(35,97)(iii)L(313,401)(iiii)L(165,503)（解）(i)1(ii)1(iii)1(iv)1【例6】同余方程286（mod563）是否有解。（解）563為素數，計算勒讓德符號1所以，原方程無解。【例7】判斷同余方程88（mod105）是否有解。（解）105357為合數，直接計算雅可比符號1所以，原方程無解。（因為原方程等價于方程組，而方程

21、組有解的充分必要條件是勒讓德符號1。但1，說明、三者中至少有一個為1，即方程組中至少有一個方程無解，從而原方程無解）。再次說明雅可比符號可以用來否定方程有解，但不能肯定方程有解。【例8】求同余方程38（mod385）的解數。（解）3857511為合數，直接計算雅可比符號11并不能肯定原方程是否有解。所以，還須判斷方程組中的每個方程是否有解。故再計算勒讓德符號1，因此方程38（mod5）無解，最終說明原方程解數為零。模p平方根目的：解同余方程a（modp），p為素數且pa（1）方法：逐步迭代設p1s。理論基礎理論基礎：a是模p的平方剩余的充要條件（歐拉定理）Z1（modp）若t1則（偶數）1（m

22、odp）若1（modp）且t2，繼續開方；否則，構造N，使1（modp）又可以繼續開方。其中N為模p的平方非剩余（即）。目標：構造，使得：a（modp）從而得方程（1）的解：x（modp）算法將偶數p1表為p1s，t1，s為奇數。（1）選模p的平方非剩余N，即1，令b（modp），則有1（modp）1（modp）即b是模p的次單位根，但非模p的次單位根。（2）計算：（modp）則y滿足方程：1（modp）（因1（modp）即y是模p的次單位根。（3）若t1，則x（modp）滿足方程a（modp）（此時p12s，a（modp）。即方程已經解出）否則，t2，尋找，使得y滿足方程1（modp）即y是

23、模p的次單位根。（a）若1（modp）令0，（modp），則即為所求。（b）若1（modp）令1，b（modp），則即為所求。（因(1)(1)1（modp）（4）若t2，則x（modp）滿足方程a（modp）（此時p1s，a（modp）否則，t3，尋找，使得y滿足方程1（modp）即y是模p的次單位根。（a）若1（modp）令0，（modp），則即為所求。（b）若1（modp）令1，（modp），則即為所求。依次類推（k1）設找到整數滿足1（modp）即y是模p的次單位根：1（modp）（k2）若tk，則x（modp）滿足方程a（modp）否則，tk1，尋找整數，使得y滿足方程1（modp）即

24、y是模p的次單位根。（a）若1（modp）令0，（modp），則即為所求。（b）若1（modp）令1，（modp），則即為所求。最后，kt1：（modp）滿足方程：a（modp），p為素數且pa例【例1】用上述方法解同余方程186（mod401）（解）a186，p401。判斷：p401為素數，且（用雅可比符號計算）111或（用勒讓德符號計算）1(1)(1)1故原方程有解。準備：p1401140025，其中t4，s25。（1）由上邊計算，1，即N3是模401的平方非剩余。令b268（mod401）。（2）計算103（mod401）235（mod401）（3）因為1（mod401）故令1，1032

25、68336（mod401）。（此時，）（4）因為1（mod401）故令0，336（mod401）。（此時，）（5）因為2351（mod401）故令1，336304（mod401）。（此時，）則304（mod401）滿足原方程。（驗證，92416186（mod401）【例2】設p是形為4k3的素數，若方程a（modp）有非零解，則其解為x（modp）（解）因為p4k3，故q為奇數，而方程a（modp）有解，則a是模p的二次剩余，從而有1（modp）即1（modp）已知原方程有非零解，即（a,p）1，故有a（modp）即a（modp）x（modp）【例3】設pq均為形如4k3的素數，且1，求解同余

26、方程：a（modpq）（解）首先a（modpq）而兩個方程的解分別為（modp）和（modq）利用中國剩余定理解聯立方程得原方程的解為（modp）uq（modq）vp（modpq）其中，1（modp），vp1（modq）【例3】解同余方程3（mod253）。（解）2531123，1123，二者均為形如4k3的素數，且1，解方程3（mod11），得5（mod11）解方程3（mod23），得7（mod23）利用中國剩余定理解聯立方程M1123253，11，計算1（mod11），21（mod23）523171121（mod253）1159916，39，（mod253）合數的情形方程a（modm），（

27、a,m）1（1）a（mod），（a,p）1，1（3）P為奇素數【定理4.7.1】設p是奇素數，則（3）有解1。且有解時，（3）的解數為2。（證）必要性a（mod）有解a（modp）有解1充分性：設1，則存在整數x（modp）使得a（modp）令f(x)a，則2x，（2，p）1，故方程（3）的解數為2。【推論】同余方程（3）的解數為T1P2a（mod），（a,2）1，1（4）（當1時，方程a1（mod2）有一個解x1（mod2）【定理4.7.2】設1，則同余方程（4）有解的必要條件是當2時，a1（mod4）；當3時，a1（mod8）。若上述條件成立，則（4）有解。且當2時，解數是2；當3時，解數

28、是4。（證）必要性：若（4）有解，則存在整數z，使得a（mod）由（a,2）1知（z,2）1，記z12t，則上式可表為a14t(t1)（mod）（5）（注：14t4）所以當2時，a1（mod4）。而當3時，由（5）知a14t(t1)（mod8）又由2t(t1)知，a1（mod8）。充分性：（i）當2時，a1（mod4），方程a1（mod）顯然有兩個解x1，3（mod）（ii）當3時，a1（mod8）。此時，若3，易驗證方程a1（mod）（6）的解為x1，5（mod），即(1)，0,1,2或()，0,1,2（7）其中，x31,5。若4，方程為a（mod）（8）令a（mod）（由第三章結論，希望從

29、方程（6）的解的值（7）中去找方程（8）的解，即確定）即2()a（mod）亦即a（mod）a（mod）所以（mod2）（mod2）（注意1（mod2）或2，0,1,2代入（7），方程（8）的解可表為（()，0,1,2（7）()，2，0,1,2()，0,1,2或()，0,1,2其中，且1（mod2）。（因為a1（mod8），故整數，從而為偶數）依次類推，對于4，設同余方程a（mod）（9）的解為()，0,1,2（10）或()（mod），0,1且1（mod2）。為了從方程（9）的上述解的值（10）中找出方程a（mod）（11）的解，令a（mod）即2()a（mod）亦即a（mod）a（mod）（1

30、2）所以（mod2）（mod2）或2，0,1,2代入（10）式，方程（11）的解可表為（()，0,1,2（10）()，2，0,1,2即()，0,1,2或()，0,1,2其中，且1（mod2）。（因為由式（12）可知整數，從而為偶數）【例1】解方程57（mod64）。（解）64，即6。因571（mod8），故方程有4個解。3時，解的值為x(1)，0,1,2（13）（解的表示：x1，3，5，7（mod8），或x1，57，3（mod8）或x(14t)(34t)（mod8），t0,1還可表為：x1，37，5（mod8）或x(12t)(52t)（mod8），t0,1此時方程為571（mod8）（1）4時

31、，在式（13）的所有值中找方程57（mod）（14）的解。為此，令57（mod）則21(4)57（mod）即157（mod）157（mod）11（mod2）1（mod2）或212，0,1,2代入（13）式得方程（14）的解為（x(1)，0,1,2（13）x(11)(5)，0,1,2或x(5)（mod），0,1或x5，133，5（mod）（5）5時，令57（mod），則25()57（mod）557（mod）50（mod2）0（mod2）或022，0,1,2故方程57（mod）的解為x(50)(5)，0,1,2或x(5)（mod），0,1或x5，215，11（mod）（5）6時，令57（mod），

32、則25()57（mod）557（mod）51（mod2）1（mod2）或12，0,1,2故方程57（mod）的解為(51)(21)，0,1,2或(21)（mod），0,1或21，5311，21（mod）（21）解同余方程總結方法一般方程方程f(x)0（modm）化為等價方程組其中解素數冪方程f(x)0（mod），p為素數deg(f)2，1，p2或奇素數的解法deg(f)2，2，p2或奇素數的解法deg(f)2，若已知1時的解，求2時的解問題（1）m的分解（2）deg(f)2，1時的解法習題4求滿足下列方程的所有整點：（1）E：（mod7）；（2）E：（mod7）；（3）E：（mod17）；（4

33、）E：（mod17）。利用歐拉判別條件判斷：（1）8是否是模53的二次剩余；（2）8是否是模67的二次剩余。求下列同余方程的解數：（1）2（mod67）；（2）2（mod67）；（3）2（mod37）；（4）2（mod37）；（5）1（mod221）；（6）1（mod427）；計算下列勒讓德符號：（1）；（2）；（3）；（4）；（5）；（6）；（7）；（8）；（9）；（10）；（11）；（12）。判斷下列同余方程是否有解，若有解，請求其解數：（1）7（mod227）；（2）249（mod257）（3）79（mod433）；（4）365（mod389）（5）11（mod511）；（6）2495（mod5249）；（7）116（mod91）；（8）514（mod6193）。解下列同余方程：（1）60（mod56）；（2）40（mod32）按要求完成下列問題：求以3為其二次剩余的全體素數；求以3為其二次剩余的全體素數；求以3為其二次非剩余的全體素數；求以3為二次剩余、以3為二次非剩余的全體素數；求以3為二次剩余、以3為二次非剩余的全體素數；求以3為二次非剩余、以2為二次剩余的全體素數（即以3為正的最小二次非剩余的全體素