本文格式為Word版，下載可任意編輯——《數(shù)論算法》教案4章（二次同余方程與平方剩余）《數(shù)論算法》第四章二次同余方程與平方剩余

第4章二次同余方程與平方剩余

內(nèi)容1.二次同余方程，平方剩余2.模為奇素?cái)?shù)的平方剩余3.勒讓德符號、雅可比符號4.二次同余方程的求解二次同余方程有解的判斷與求解要點(diǎn)4.1一般二次同余方程

(一)二次同余方程

ax2＋bx＋c≡0（modm），（a

(二)化簡

0（modm））（1）

?1?2設(shè)m＝p1p2?pkk，則方程（1）等價(jià)于同余方程

??ax2?bx?c?0（mod?2?ax?bx?c?0（mod?????ax2?bx?c?0（mod?問題歸結(jié)為探討同余方程

?1p1）?2p2）?kpk）ax2＋bx＋c≡0（modp?），（pa）（2）

(三)化為標(biāo)準(zhǔn)形式

p≠2，方程（2）兩邊同乘以4a，

4a2x2＋4abx＋4ac≡0（modp?）

?2ax?b?2≡b2－4ac（mod

1/49

p?）

《數(shù)論算法》第四章二次同余方程與平方剩余

變量代換，

y＝2ax＋b（3）

有

y2≡b2－4ac（modp?）（4）

當(dāng)p為奇素?cái)?shù)時(shí)，方程（4）與（2）等價(jià)。即?兩者同時(shí)有解或無解；有解時(shí)，對（4）的每個(gè)解

通過式（3）（x的一次同余方程，且（p,y?y0?modp?，

2a）＝1，所以解數(shù)為1）給出（2）的一個(gè)解x?x0?modp?，由（4）的不同的解給出（2）的不同的解；反之亦然。?兩者解數(shù)一致。

結(jié)論：只須探討以下同余方程

x2≡a（modp?）（5）

化簡方程7x2＋5x－2≡0（mod9）為標(biāo)準(zhǔn)形式。（解）方程兩邊同乘以4a＝4×7＝28，得

196x2＋140x－56≡0（mod9）

配方(14x＋5)2－25－56≡0（mod9）移項(xiàng)(14x＋5)2≡81（mod9）變量代換y＝14x＋5得y2≡0（mod9）

（解之得y＝0,±3，從而原方程的解為

x≡14?1(y－5)≡5?1(y－5)≡2(y－5)≡2y－10≡2y－1

≡－7,－1,5≡－4,－1,2（mod9））

2/49

《數(shù)論算法》第四章二次同余方程與平方剩余

(四)二次剩余

設(shè)m是正整數(shù)，a是整數(shù)，ma。若同余方程

x2≡a（modm）（6）

有解，則稱a是模m的平方剩余（或二次剩余）；若無解，則稱a是模m的平方非剩余（或二次非剩余）。

問題：

（1）設(shè)正整數(shù)a是模p的平方剩余，若記方程（6）中的

解為x≡a（modm），那么此處的平方根a（modm）與尋常的代數(shù)方程x2＝a的解a有何區(qū)別？（2）如何判斷方程（6）有解？（3）如何求方程（6）的解？(五)例

1是模4平方剩余，－1是模4平方非剩余。1、2、4是模7平方剩余，3、5、6是模7平方非剩余。

直接計(jì)算12，22，…，142得模15的平方剩余（實(shí)際上只要計(jì)算（12，22，…，72）

1，4，9，10，6

平方非剩余：2，3，5，7，8，11，12，13，14

求滿足方程E：y2≡x3＋x＋1（mod7）的所有點(diǎn)。

（解）對x＝0，1，2，3，4，5，6分別解出y：，y≡1，6（mod7）x＝0，y2≡1（mod7）

3/49

《數(shù)論算法》第四章二次同余方程與平方剩余

，無解x＝1，y2≡3（mod7）

，y≡2，5（mod7）x＝2，y2≡4（mod7），無解x＝3，y2≡3（mod7），無解x＝4，y2≡6（mod7），無解x＝5，y2≡5（mod7），無解x＝6，y2≡6（mod7）

所以，滿足方程的點(diǎn)為（0,1），（0,6），（2,2），（2,5）。說明：方程E：y2≡x3＋x＋1的圖形稱為橢圓曲線。

4.2模為奇素?cái)?shù)的平方剩余與平方非剩余

模為素?cái)?shù)的二次方程

x2≡a（modp）,(a,p)＝1（1）

由于??x?＝x2，故方程（1）要么無解，要么有兩個(gè)

解。

2(一)平方剩余的判斷條件

（歐拉判別條件）設(shè)p是奇素?cái)?shù)，(a,p)＝1，則

（i）a是模p的平方剩余的充要條件是

a?p?1?2≡1（modp）（2）

（ii）a是模p的平方非剩余的充要條件是

a?p?1?2≡－1（modp）（3）

并且當(dāng)a是模p的平方剩余時(shí)，同余方程（1）恰有兩個(gè)解。

（證）先證pa時(shí)，式（2）或（3）有且僅有一個(gè)成立。由費(fèi)馬定理ap?1≡1（modp）

4/49

《數(shù)論算法》第四章二次同余方程與平方剩余

?a??a?p?1?2?－1≡0（modp）

?1??a???1?≡0（modp）（4）

p?1?22p?12即pap?1?1＝a?p?1?2?1a?p?1?2?1但a?p?1?2?1,a?p?1?2?1＝1或2

且素?cái)?shù)p>2。所以，p能整除a?p?1?2?1a?p?1?2?1，但p不能同時(shí)整除a?p?1?2?1和a?p?1?2?1（否則，p能整除它們的最大公因子1或2）

所以，由式（4）馬上推出式（2）或式（3）有且僅有一式成立。

（i）必要性。若a是模p的二次剩余，則必有x0使得

2≡a（modp），x0??????????因而有

??2?p?1?2x0≡a?p?1?2（modp）。

即x0p?1?a?p?1?2（modp）。由于pa，所以p

x0，因此由歐拉定理知

。x0p?1≡1（modp）

即（2）式成立。充分性。已知a一次同余方程

?p?1?2≡1（modp），這時(shí)必有pa。故

bx≡a（modp）,(1≤b≤p－1)（5）

有唯一解，對既約剩余系

－(p－1)/2，…，－1，1，…，(p－1)/2（6）

由式（6）給出的模p的既約剩余系中的每個(gè)j，當(dāng)b＝j(luò)時(shí)，

必有唯一的x?xj屬于既約剩余系（6），使得式（5）成立。若a不是模p的二次剩余，則必有j?xj。這樣，既約剩余

5/49

《數(shù)論算法》第四章二次同余方程與平方剩余

系（6）中的p－1個(gè)數(shù)就可按j、xj作為一對，兩兩分完。（b1≠b2，則相應(yīng)的解x1≠x2，且除了±1之外，每個(gè)數(shù)的逆不是它本身）因此有

(p?1)!?a?p?1?2?modp?.

由威爾遜定理知

a?p?1?2??1?modp?.

與式（2）矛盾。所以必有某一j0，使j0?xj0，由此及式（5）知，a是模p的二次剩余。

（ii）由已經(jīng)證明的這兩部分結(jié)論，馬上推出第（ii）條成立。

其次，若x00（modp）是方程（1）的解，則－x0也是其解，且必有x0－x0（modp）。故當(dāng)(a,p)＝1時(shí)，方程（1）要么無解，要么同時(shí)有兩個(gè)解。

（說明：本定理只是一個(gè)理論結(jié)果，當(dāng)p>>1時(shí)，它并不是一個(gè)實(shí)用的判斷方法）

小結(jié)：對于任何整數(shù)a，方程（1）的解數(shù)可能為

T(x2－a；p)＝0,1,2

設(shè)p＝19，驗(yàn)證定理4.2.1的證明過程。（解）由費(fèi)馬定理知，對任何a＝1,2,…,18，都有a18≡1（mod19）。方程x2≡1（mod19）只有兩個(gè)解，即x≡±1（mod19）。從而必有

a9≡±1（mod19）

（視a18?a9≡1（mod19），即x?a9）

針對必要性：例如a＝17是模19的二次剩余，即存在x0≡6使得62≡17（mod19）。那么必有

6/49

??2《數(shù)論算法》第四章二次同余方程與平方剩余

a?p?1?2≡179≡618≡1（mod19）

針對充分性：例如a＝6，a?p?1?2≡69≡1（mod19），驗(yàn)證6是二次剩余。解方程

bx≡6（mod19）,(1≤b≤18)

當(dāng)b≡1,2,3,4,5,…,17,18（mod19）時(shí)，方程有唯一解x≡6,3,2,11,5,…,16,13（mod19）其中5?5≡6（mod19）

即當(dāng)b≡5時(shí)，x≡5。所以6是二次剩余。

又選a＝8，a?p?1?2≡89≡－1（mod19），驗(yàn)證：解方程

bx≡8（mod19）,(1≤b≤18)

得1?8≡8，2?4≡8，3?9≡8，4?2≡8，5?13≡8，6?14≡8，7?12≡8，8?1≡8，9?3≡8，10?16≡8，11?18≡8，12?7≡8，13?5≡8，14?6≡8，15?17≡8，16?10≡8，17?15≡8，18?11≡8

1?2?…?18≡

(1?8)(2?4)(3?9)(5?13)(6?14)(7?12)(10?16)(11?18)(15?17)

≡89≡－1（mod19）

判斷137是否為模227的平方剩余。（解）首先，227是素?cái)?shù)。其次，計(jì)算

137?227?1?2≡－1（mod227）

所以，137是模227的平方非剩余。

設(shè)p是奇素?cái)?shù)，(a1,p)＝1，(a2,p)＝1，則（i）若a1，a2都是模p的平方剩余，則a1a2是模p的平方剩余；

（ii）若a1，a2都是模p的平方非剩余，則a1a2是模p

7/49

《數(shù)論算法》第四章二次同余方程與平方剩余

的平方剩余；

（iii）若a1是模p的平方剩余，a2是模p的平方非剩余，則a1a2是模p的平方非剩余。

（證）因?a1a2??p?1?2＝a1?p?1?2a2?p?1?2

(二)平方剩余的個(gè)數(shù)

設(shè)p是奇素?cái)?shù)，則模p的既約剩余系中平方剩余與平方非剩余的個(gè)數(shù)各為(p－1)／2，且(p－1)／2個(gè)平方剩余恰與序列

?p?1?221，2，…，???2?中的一個(gè)數(shù)同余。

（證）由定理4.2.1，模p的平方剩余個(gè)數(shù)等于方程

2x的解數(shù)。但

p?12≡1（modp）

xp?12?1xp?1

p?1由定理3.4.5知，方程的解數(shù)為，即平方剩余的個(gè)數(shù)是

2p?1p?1p?1，且平方非剩余的個(gè)數(shù)是(p－1)－＝。222p?1p?1其次，可以證明當(dāng)1≤k1≤，1≤k2≤，且k1

222≠k2時(shí)，有k12modp。故結(jié)論成立。k2（定理3.4.5：設(shè)p為素?cái)?shù)，n為正整數(shù)，n≤p。則同余方程

nn?1f?x?＝x?an?1x???a1x?a0≡0modp有n個(gè)解

?xp?x被f?x?除所得余式的所有系數(shù)都是p的倍數(shù)）

8/49

《數(shù)論算法》第四章二次同余方程與平方剩余

4.3勒讓德符號

目的：快速判斷整數(shù)a是否為素?cái)?shù)p的平方剩余。(一)勒讓德符號

設(shè)p是素?cái)?shù)，定義勒讓德（Legendre）符號為：

?1,當(dāng)a是模p的二次剩余；?a??L(a,p)＝??p??＝??1,當(dāng)a是模p的二次非剩余；????0,當(dāng)pa。?a?整數(shù)a是素?cái)?shù)p的平方剩余的充要條件是??p??＝

??1。

（證）由定義4.3.1。

因此，判斷平方剩余轉(zhuǎn)化為計(jì)算勒讓德符號的值。

直接計(jì)算，得

?1??2??4??8??9??13??15??16?????????????????????????17??17??17??17??17??17??17??17?＝1

?3??5??6??7??10??11??12??14?????????????????????????17??17??17??17??17??17??17??17?＝－1（注：本例仍是利用平方剩余而得到勒讓德符號值）

問題：反過來，如何快速計(jì)算勒讓德符號的值，以判斷平方剩余。

9/49

《數(shù)論算法》第四章二次同余方程與平方剩余

(二)（勒讓德符號的）性質(zhì)

（歐拉判別法則）設(shè)p是奇素?cái)?shù)，則對任意整數(shù)a，有

?a???p??＝a??

p?12（modp）

（證）由定理4.2.1即知。

?1???p??＝1

??（證）顯然（由于方程x2≡1（modp）始終有解x≡±1（modp），或者由性質(zhì)1立得）。

??1??p?1?2???＝。?1??p???（證）由性質(zhì)1即得。

??1???1???＝1，??＝－1

?17??19?

??1??1,p?1?mod4???p??＝??1,p?3?mod4????（證）p≡1（mod4）?p＝4k＋1?

??1??p?1?22k????＝＝＝1?1?1???p???p≡3（mod4）?p＝4k＋3?

10/49

《數(shù)論算法》第四章二次同余方程與平方剩余

??1??p?1?22k?1????＝＝＝－1?1?1???p???另一種描述：設(shè)素?cái)?shù)p>2，則－1是模p的二次剩余的充

分必要條件是p≡1（mod4）。

???a?p??a???＝?????p??p?（證）因x2≡a＋p（modp）?x2≡a（modp）

?a??b?若a≡b（modp），則??p??＝??p??

????

?ab??a??b???p??＝??p????p??

??????p?1?ab?（證）因??p??＝?ab?2＝a??p?1p?1?2b2＝?a??b??p????p???????ak??p???a??＝????p????k?a2??當(dāng)pa時(shí)，??p?＝1??

探討：確定a是否是模p的平方剩余就變?yōu)槿绾斡?jì)算

?a??a?Legendre符號?的值。上述性質(zhì)可以用來計(jì)算???p??p??，并由

????算術(shù)基本定理，設(shè)a的分解式為

11/49

《數(shù)論算法》第四章二次同余方程與平方剩余

?a＝±p11?k?k?2?1?2＝??1?p1，（t＝0,1）p2?pkp2?pkt則

?a????1?t??p??＝?????p??q1???????p????1?q2??qk??????p??p???????2?k

（t＝0,1）故只要能計(jì)算出

??1??2??q???p??，??p???p??，????????a?就可以計(jì)算出任意的??p??，其中q?2是小于p的素?cái)?shù)。

????1?已經(jīng)解決的計(jì)算：??p????剩余的問題：???2??q???，?的計(jì)算。????p??p?解決這些問題的基礎(chǔ)是下面的二次互反律（Gauss定理）。

p?1?2???p??＝??1?8

??17?11816?2????＝??1?8＝??1?24＝1，

?17?2219?12023?2????＝??1?8＝??1?42＝－1，故2是模17的平方?19?2剩余，但不是模19的平方剩余。

p為奇素?cái)?shù)，則

12/49

《數(shù)論算法》第四章二次同余方程與平方剩余

?2??1,p??1?mod8???p??＝??1p??3?mod8????（證）由于當(dāng)p＝8k＋1時(shí)

p2?1?p?1??p?1??8k?2?8k＝＝＝k(8k＋2)＝偶數(shù)888當(dāng)p＝8k＋3時(shí)

p2?1?8k?4??8k?2?＝＝(2k＋1)(4k＋1)＝奇數(shù)

88?2?由于31≡7≡－1（mod8），59≡3（mod8），故???31??2?＝1，??＝－1，即2是模31的平方剩余，但不是模59

?59?的平方剩余。

（二次互反律，高斯定理）p≠q且均為奇素?cái)?shù)，則

p?1q?1?p??q???＝??1?22?????q??p?p?1q?1?q??p??另一表示形式：???＝??1?22???p??q??q??p??說明1：符號??和?分別刻畫了二次同余方程???p??q?x2≡q（modp）

和

x2≡p（modq）

13/49

《數(shù)論算法》第四章二次同余方程與平方剩余

是否有解，即q是否是模p的二次剩余和p是否是模q的二次剩余，其中正好是模與剩余互換了位置，而性質(zhì)7恰好刻畫了兩者之間的關(guān)系，故稱為二次互反律。

說明2：由歐拉提出，高斯首先證明。已有一百五十多個(gè)

不同的證明。由二次互反律引伸出來的工作，導(dǎo)致了代數(shù)數(shù)論的發(fā)展和類域論的形成。

（i）設(shè)奇素?cái)?shù)p、q中至少有一個(gè)模4為1，則方程x2≡q（modp）有解?方程x2≡p（modq）有解（ii）若p≡q≡3（mod4），則

方程x2≡q（modp）有解?方程x2≡p（modq）無解（證）（i）設(shè)p≡1（mod4），即p＝4k＋1，則

p?1p?1?p?4kp?1?p??p??q???2222????p??＝??1??q??＝??1??q??＝??q??

????????（ii）此時(shí)，p＝4s＋3，q＝4t＋3，則

p?1p?1?p?4s?24t?2?p??p??q???2222????p??＝??1??q??＝??1??q??＝－??q??

????????

判斷3是否是模17的平方剩余。

17?13?117?3????2??（解）??＝??1?22??＝??＝－1

?17??3??3?所以，3是模17的平方非剩余。（不但如此，17也是3的平方非剩余，即2是3的平方非剩余）

判斷同余方程x2≡137（mod227）是否有解。（解）已知137與227均為奇素?cái)?shù)，所以

14/49

《數(shù)論算法》第四章二次同余方程與平方剩余

227?137?1227?137????90??22???1＝????＝??

?227??137??137??2?32?5??2??5??5?＝????＝???137??＝????137??137??137?＝??1?137?15?122?137??2???＝??＝－1?5??5?所以，方程無解。

2?137???90???1??2?3?5??另法：??＝??＝??????227??227??227??227?227?15?1227?2??5???＝－????＝??1?22??

?227??227??5??2?＝??＝－1?5?判斷同余方程x2≡－1（mod365）是否有解，若有解，求解數(shù)。

（解）由于365＝5·73，所以

2?x??12

x≡－1（mod365）??2?x??1?mod5?

?mod73???1???1???＝??＝1?5??73?所以方程有解，且解數(shù)為4。

判斷同余方程x≡2（mod3599）是否有解，若有解，求解數(shù)。

（解）由于3599＝59·61，所以

215/49

《數(shù)論算法》第四章二次同余方程與平方剩余

2?x?22x≡2（mod3599）??2?x?2?mod59?

?mod61??2?由于59≡3（mod8），即??＝－1，故方程x2≡2（mod59）

?59?無解，從而原方程無解。

證明形如4k＋1的素?cái)?shù)有無窮多。

（證）反證法：不然，形如4k＋1的素?cái)?shù)為有限個(gè)，設(shè)為p1，p2，…，pk，令

a＝?2p1p2?pk?2?1＝4b＋1

即a也形如4k＋1且a＞pi（i＝1,2,…,k）。所以a為合數(shù)，設(shè)其素因數(shù)p為奇數(shù)，則

2??1???1?a???2p1p2?pk???＝1??p??＝??p??＝???p??????所以－1為模p平方剩余。由性質(zhì)3的推論，p≡1（mod4），??1?即p也是形如4k＋1的素?cái)?shù)。（??p??＝???1,p?1?mod4?）???1,p?3?mod4?但顯然p≠pi（i＝1,2,…,k），矛盾（否則，。p?2p1p2?pk?，且由p│a知p│1）2

4.4二次互反律的證明

(一)證明

16/49

《數(shù)論算法》第四章二次同余方程與平方剩余

(二)應(yīng)用

求所有奇素?cái)?shù)p，它以3為其平方剩余。

?3?（解）即求所有奇素?cái)?shù)p，使得??p??＝1。

??易知p＞3。由二次互反律

p?1?3??p?2????1＝????p??3???由于

??1?以及

p?12?1,p?1?mod4?＝???1,p??1?mod4???1????1,p?1?mod6???p???3?（排除偶數(shù)）??＝??3????1???,p??1?mod6????3?知

?3???p??＝1??即

?p?1???p?1?mod4??p??1?mod4?或??mod6??p??1?mod6?p≡1（mod12）或p≡－1（mod12）

故3是模p二次剩余?p≡±1（mod12）

?d?設(shè)p為奇素?cái)?shù)，d是整數(shù)。若??p??＝－1，則p一

??定不能表示為x2?dy2的形式。

（證）用反證法。設(shè)p有表達(dá)式x2?dy2，則由p是素?cái)?shù)

17/49

《數(shù)論算法》第四章二次同余方程與平方剩余

可知(x,p)＝(y,p)＝1。這是由于若(x,p)≠1，則必有

px

?

px2?p?dy2

?d?2

但由?＝－1知(d,p)＝1，所以p│y，進(jìn)而p│y。那么??p???p2│x2，p2│y2?p2│x2－dy2＝p

矛盾。（即(x,p)＝(y,p)＝1成立）

?x??y?由(x,p)＝(y,p)＝1知，??p??＝±1，??p??＝±1，從而

?????d??d??y2??dy2??x2?p??x2??????????p??＝??p????p?＝?p?＝?p?＝?p?＝1

????????????與題設(shè)矛盾。

?a?同余方程x2?a?modp?的解數(shù)是1???p??。

??

求所有奇素?cái)?shù)p，它以5或－2為其平方剩余。

4.5雅可比符號

?a?（1）問題：在計(jì)算勒讓德符號??p??時(shí)，若a為奇數(shù)，但非

???a?素?cái)?shù)，如何快速計(jì)算??p??。

??（2）目的：為了快速計(jì)算勒讓德符號。(一)雅可比符號

18/49

《數(shù)論算法》第四章二次同余方程與平方剩余

設(shè)m＝p1p2…pk是奇素?cái)?shù)pi的連乘積（pi可以重復(fù)），對任意整數(shù)a，定義雅可比（Jacobi）符號為：

?a??a??a??a?????J(a,m)＝??＝??????????m??p1??p2??pk?說明：

?a?（1）上式右端的??p??為勒讓德符號，即

?i?k?a??a??a??a?????J(a,m)＝??＝?＝?L?a,?????????m??p1??p2??pk?i?1pi?

（2）雅可比符號形式上是勒讓德符號符號的推廣。但與

勒讓德符號意義不同。（3）兩者的本質(zhì)區(qū)別：勒讓德符號可用來判斷平方剩余，

但雅可比符號卻不能。即當(dāng)k＞1時(shí)，假使J(a,m)＝－1，則方程x2≡a（modm）無解（由于至少存?a?2?在一個(gè)pi，使得?＝－1，即方程≡a（modx?p??i?，pi）無解，從而原方程x2≡a（modm）也無解）但當(dāng)J(a,m)＝1時(shí)，方程x≡a（modm）則不一

定有解。

（4）當(dāng)k＝1時(shí)，J(a,m)＝L(a,m)，即此時(shí)勒讓德符號

的值與雅可比符號的值相等。（5）因此，求勒讓德符號的值轉(zhuǎn)化為計(jì)算雅可比符號。

由定義4.5.1

2?2??2??2???＝????＝(－1)(－1)＝1?9??3??3?但可以驗(yàn)證2是模9的平方非剩余。

19/49

《數(shù)論算法》第四章二次同余方程與平方剩余

又如當(dāng)奇素?cái)?shù)p≡3（mod4）時(shí)，由勒讓德符號的性質(zhì)知，－1是模P的非平方剩余，即方程x2≡－1（modp）無解，從而方程x2≡－1（modp）也無解。即－1是模p的平方非剩余。但若取m＝p，則總有

222??1???1???1???p????p??＝(－1)(－1)＝1?p2??＝???????

問題：如何快速計(jì)算雅可比符號的值，以幫助加速勒讓

德符號的求值過程，從而加速判斷平方剩余。(二)（雅可比符號的）性質(zhì)

?a?若(a,m)＝1，則J(a,m)＝??＝±1；若(a,m)

?m??a?＞1，則J(a,m)＝??＝0。

?m??a?（證）因(a,m)＞1時(shí)，至少有某個(gè)pia，即??p??＝0，從

?i??a?而??＝0。?m?a＝15，m＝39，則

?a??15??15??15?J(a,m)＝??＝??＝????

?m??39??3??13??2??0??2?＝????＝0??＝0

?13??3??13?

?1???＝1

?m?20/49

《數(shù)論算法》第四章二次同余方程與平方剩余

?1??1??1??1?????（證）J(1,m)＝??＝?＝1?????????m??p1??p2??pk?

m?1??1???＝??1?2

?m?（證）由于

m＝?pi＝??1??pi?1??

i?1i?1kk＝1＋??pi?1?＋??pi?1?pj?1＋…??pi?1?

i?1i?1k??k故m≡1＋??pi?1?（mod4），即

i?1km－1≡??pi?1?（mod4）

kp?1m?1≡?i（mod2）

22i?1所以

i?1k??1???1???1????1?J(－1,m)＝??＝???????m??p1??p2??pk?＝??1?p1?1p2?1p?1???k222??????＝??1?m?12

??1??1,m?1?mod4???＝??m???1,m?3?mod4?（證）m≡1mod4?m＝4k＋1?

m?1??1?2k??＝??1?2＝??1?＝1?m?m≡3mod4

?m＝4k＋3?

m?12k?1??1?＝－1??＝??1?2＝??1??m?21/49

《數(shù)論算法》第四章二次同余方程與平方剩余

??1???1??＝1，???＝－1

?33??51?

?a?m??a???＝??

?m??m?（證）首先，由m＝p1p2…pk和m＋a≡a（modm）知

m＋a≡a（modpi）

其次，由雅可比符號和勒讓德符號性質(zhì)知

?a?m??a?m??a?m??a?m?????????＝????????m??p1??p2??pk??a??a??a??a?＝???p????p?????p??＝??1??2??k??m?

?a??b?若a≡b（modm），則??＝??

?m??m?（證）顯然

?ab??a??b???＝????

?m??m??m??ab??ab??ab??ab?????（證）因??＝??????????m??p1??p2??pk??a??b??a??b??a??b?＝??p????p????p??·…·??p??·??p????p???1??1??2??2??k??k??a??a??a??b??b??b?＝??p????p??…??p??…??p????p??·??p???1??2??k??1??2??k?22/49

《數(shù)論算法》第四章二次同余方程與平方剩余

?a??b?＝?????m??m?

k?ak??a???m??＝?m?

?????a2?當(dāng)(m,a)＝1時(shí)，??m??＝1

??

m2?18

?2???＝??1??m?（證）由于

kkm2＝?pi2＝?1?pi2?1

i?1i?12＝1＋?pi2?1＋?pi2?1p2j?1＋…＋?pi?1

i?1i?1kk??????????k??∴m－1≡?pi2?1（mod64）

2??i?1而對任何奇數(shù)q，都有q≡1（mod8）（i＝1,2,…,k），故

kpi2?1m2?1≡?（mod8）

88i?1kpi2?1m2?1≡?（mod2）

88i?12?2??2??2??2?????所以J(2,m)＝??＝?…????????m??p1??p2??pk?＝

??1?222p1?1p2?1pk?1???888＝

??1?m2?18

m為奇數(shù)，則

23/49

《數(shù)論算法》第四章二次同余方程與平方剩余

?2??1,m??1?mod8???＝??m???1m??3?mod8?（證）由于當(dāng)m＝8k＋1時(shí)

m2?1?m?1??m?1??8k?2?8k＝＝＝k(8k＋2)＝偶數(shù)888當(dāng)m＝8k＋3時(shí)

m2?1?8k?4??8k?2?＝＝(2k＋1)(4k＋1)＝奇數(shù)88

?2??2??2??2???＝??＝1，??＝??＝－1。

?3?19??57??5?7??35?

（二次互反律，高斯定理）設(shè)m、n都是奇數(shù)，

則

m?1n?1m?n???22???1＝?????n??m?m?1n?1?n??m?或????＝??1?22

?m??n?

m1、m2、a為整數(shù)，則

?a??a??a???mm??＝??m????m???12??1??2?（證）設(shè)m1＝p1p2…ps，m2＝q1q2…qs，則

?a??a??a??a左邊＝J(n,m1m2)＝??p??…??q??…??p????q?1??s??1??t24/49

????《數(shù)論算法》第四章二次同余方程與平方剩余

＝J(a,m1)·J(a,m2)＝右邊

這樣，計(jì)算勒讓德符號的值就轉(zhuǎn)化為了計(jì)算雅可比符號

的值。而后者的求值要比前者快了大量。

用雅可比符號計(jì)算：(i)L(51,71)(ii)L(－35,97)(iii)L(313,401)(iiii)L(165,503)

71?151?171?51????20?（解）(i)??＝??1?22??＝－??

?71??51??51?51?15?151?22?5??5???22?????1＝－?＝－＝－????51??51??5????1?＝－??＝－1

?5?97?13597?135?197??35?????(ii)??＝??1?2??＝??1?22??

?97??35??97?35?127?1?27??8??2?22???1＝??＝??＝－???35??27??27?＝－??1?272?18＝1

401?1313?1401???88??313?????1(iii)?＝22??＝????401??313??313?313?1313?111?1?2??11??5??22＝????＝??1?8??1???

?11??313??313?2＝??1?11?15?11???22??＝1

?5?25/49

《數(shù)論算法》第四章二次同余方程與平方剩余

503?1165?1503???8??2??165??(iv)?2??＝??＝???＝??1?2?503??165??165??165?

＝??1?

1652?1＝－18同余方程x2≡286（mod563）是否有解。（解）563為素?cái)?shù)，計(jì)算勒讓德符號

?286??2??143???＝????＝??1??563??563??563?5632?18??1?563?1143?122?563????143?143?1??9???1?＝??＝??＝??1?2＝－1?143??143?所以，原方程無解。

判斷同余方程x2≡88（mod105）是否有解。（解）105＝3·5·7為合數(shù)，直接計(jì)算雅可比符號

3105?111?11051052?1?88??2??11????228????1??＝?1??＝????????105??105??105??11?143?1?6???1?＝－??＝??＝??1?2＝－1

?11??143?

所以，原方程無解。（由于原方程等價(jià)于方程組?x2?88?2?x?88?2?x?88?mod?mod?mod3?5?，而方程組有解的充分必要條件是勒讓7??88??88??88??88??88??88?德符號??＝??＝??＝1。但??????＝?3??5??7??3??5??7??88??88??88??88???＝－1，說明??、??、??三者中至少有一個(gè)?105??3??5??7?26/49

《數(shù)論算法》第四章二次同余方程與平方剩余

為－1，即方程組中至少有一個(gè)方程無解，從而原方程無解）。

再次說明雅可比符號可以用來否定方程有解，但不能確定方程有解。

求同余方程x2≡38（mod385）的解數(shù)。（解）385＝7·5·11為合數(shù)，直接計(jì)算雅可比符號

315?119?1315315?1?38??2??19????2???＝????＝??1?8??1?2?

?315??315??315??19?2＝??11??＝??1??19?19?111?1??22?8??＝－??1??11?112?18＝1

?38???＝1?315??x2??2斷方程組?x??2?x?并不能確定原方程是否有解。所以，還須判

383838?mod?mod?mod5?7?中的每個(gè)方程是否有解。故再11??38??3?計(jì)算勒讓德符號??＝??＝－1，因此方程x2≡38（mod

?5??5?5）無解，最終說明原方程解數(shù)為零。

4.6模p平方根

（1）目的：解同余方程

x2≡a（modp），p為素?cái)?shù)且pa（1）

（2）方法：逐步迭代

設(shè)p－1＝2ts。

27/49

《數(shù)論算法》第四章二次同余方程與平方剩余

(一)理論基礎(chǔ)

理論基礎(chǔ)：a是模p的平方剩余的充要條件（歐拉定理）

Z＝a若t>1則（p?12≡1（modp）

p?1?2t?1s＝偶數(shù)）2p?12Z≡a2≡±1（modp）

若Z≡1（modp）且t＞2，繼續(xù)開方；否則，構(gòu)造N，使

NrZ≡1（modp）

又可以繼續(xù)開方。其中N為模p的平方非剩余（即

Np?12??1?modp?）。

g?目標(biāo)：構(gòu)造N，使得：??a?從而得方程（1）的解：x≡±(二)算法

s?12?N??≡a（modp）

?g2s?1a2Ng（modp）

將偶數(shù)p－1表為p－1＝2s，t≥1，s為奇數(shù)。

t?N?sN?（1）選模p的平方非剩余N，即?＝－1，令b≡?p???（modp），則有

b＝?N2tt?1ts2?＝Nt?12ts＝Np?12p?1≡1（modp）

b2＝N2s＝N≡－1（modp）

tt?1即b是模p的2次單位根，但非模p的2次單位根。

（2）計(jì)算：xt?1≡

s?1a2（modp）

28/49

《數(shù)論算法》第四章二次同余方程與平方剩余

則y＝a（因y2?1x2t?1滿足方程：

y22t?1≡1（modp）

p?12t?1＝a?1xt2?12??2t?1＝at?1s＝a≡1（modp））

即y＝a?1xt?1是模p的2t?1次單位根。

s?1a2（3）若t＝1，則x＝xt?1＝x0≡程

（modp）滿足方

x2≡a（modp）

（此時(shí)p－1＝2s，x2＝as?1＝a已經(jīng)解出）p?1?12≡a（modp）。即方程2否則，t≥2，尋覓xt?2，使得y＝a?1xt?2滿足方程

y22t?2≡1（modp）

t?2即y＝a?1xt?2是模p的2（a）若

次單位根。

?a（b）若

?1x2t?22t?1?≡1（modp）

令j0＝0，xt?2＝xt?1b0≡xt?1（modp），則xt?2即為所求。

j?a2t?2?1x2t?22t?1?j≡－1（modp）

令j0＝1，xt?2＝xt?1b0＝xt?1b（modp），則xt?2即為所求。（因y

29/49

＝ax＝axb≡(－1)(－1)≡1（modp））

??12t?22t?2???1t?2222t?1?＝ax??1t?222t?1?b2t?1《數(shù)論算法》第四章二次同余方程與平方剩余

（4）若t＝2，則x＝xt?2＝x0＝x1b0≡p）滿足方程

js?1a2bj0（mod

x2≡a（modp）p?1（此時(shí)p－1＝2s，x≡ap））22s?1b2j0≡a22?1b2j0≡a（mod2否則，t≥3，尋覓xt?3，使得y＝a?1xt?3滿足方程

y22t?3≡1（modp）

t?3即y＝a?1xt?3是模p的2（a）若

次單位根。

?a（b）若

?1x2t?32t?2?≡1（modp）

令j1＝0，xt?3＝xt?2b所求。

j12≡xt?2（modp），則xt?3即為

?a……依次類推

?1x2t?32t?2?≡－1（modp）

令j1＝1，xt?3＝xt?2b所求。

j12≡xt?2b2（modp），則xt?3即為

（k＋1）設(shè)找到整數(shù)xt?k滿足

y即y＝a?12t?k≡1（modp）

xt2?k是模p的2t?k次單位根：

30/49

《數(shù)論算法》第四章二次同余方程與平方剩余

?a?1x2t?k2≡1（modp）t?k?（k＋2）若t＝k，則x≡xt?k≡x0（modp）滿足方程

x2≡a（modp）

否則，t≥k＋1，尋覓整數(shù)xt??k?1?，使得y＝a?1xt??k?1?滿足方程

2y22t??k?1?≡1（modp）

t??k?1?即y＝a?1xt??k?1?是模p的2（a）若

次單位根。

?a?1x2t??k?1?2t?k?≡1（modp）

＝xt?k（modp），則

令jk?1＝0，xt??k?1?≡xt?kbjk?12k?1xt??k?1?即為所求。

（b）若

?a?1x2t??k?1?2t?k?≡－1（modp）

＝xt?kb2k?1令j0＝1，xt??k?1?≡xt?kb則xt??k?1?即為所求。

最終，k＝t－1：

jk?12k?1（modp），

x＝x0

≡x1bjt?22t?2

（modp）

≡x2b…………≡xt?1b≡

s?1a2jt?32t?3?jt?22t?2j0?j12?j222???jt?32t?3?jt?22t?2j0?j12?j222???jt?32t?3?jt?22t?2b31/49

《數(shù)論算法》第四章二次同余方程與平方剩余

滿足方程：x2≡a（modp），p為素?cái)?shù)且pa

(三)例

用上述方法解同余方程x2≡186（mod401）（解）a＝186，p＝401。

判斷：p＝401為素?cái)?shù)，且（用雅可比符號計(jì)算）

?186??2??93???＝????＝1·1＝1?401??401??401?或（用勒讓德符號計(jì)算）

?186??2??3??31?(－1)·(－1)＝1??＝??????＝1·

?401??401??401??401?故原方程有解。

準(zhǔn)備：p－1＝401－1＝400＝2·25，其中t＝4，s＝25。

4?3?（1）由上邊計(jì)算，??＝－1，即N＝3是模401的

?401?s25平方非剩余。令b≡N≡3≡268（mod401）。

（2）計(jì)算

s?1a225?12x3≡

（3）由于

≡186≡103（mod401）

a?1≡ap?2≡186399≡235（mod401）

?a?1x2223?≡235?103j?222?≡?98?≡－1（mod401）

4故令j0＝1，x2≡x3b0≡103·268≡336（mod401）。（此時(shí)，x3?a（4）由于

s?12?18613，x2?as?12b?18613?325）

32/49

《數(shù)論算法》第四章二次同余方程與平方剩余

?a?122x2≡

??235?336?≡1（mod401）

22故令j1＝0，x1?x2bj1?2?x2≡336（mod401）。（此時(shí)，x1?x2b0?a（5）由于

s?12b?18613?325）

?a?1x0221?3362≡－1（mod401）≡235·

2故令j2＝1，x0≡x1bj2?2≡336·2684≡304（mod401）。（此時(shí)，x1?x1b4?a則

s?152b?18613?3175）

x≡x0≡304（mod401）

滿足原方程。

2（驗(yàn)證，x0）?3042＝92416＝186（mod401）

設(shè)p是形為4k＋3的素?cái)?shù)，若方程

x2≡a（modp）

有非零解，則其解為

x≡±ap?14（modp）

p?1為奇數(shù)，而方程2（解）由于p＝4k＋3，故q＝

x2≡a（modp）

有解，則a是模p的二次剩余，從而有

p?12aq≡1（modp）

即a≡1（modp）

33/49

《數(shù)論算法》第四章二次同余方程與平方剩余

已知原方程有非零解，即（a,p）＝1，故有

aq?1≡a（modp）

即

aq?1≡

?q?1?a2????≡a（modp）??2?122∴x≡±

q?1a2?p?1?≡±a≡±ap?14（modp）

?a??a?設(shè)p≠q均為形如4k＋3的素?cái)?shù)，且??q??＝?p??＝?????1，求解同余方程：

x2≡a（modpq）

（解）首先

2?x?a?modp?2x≡a（modpq）??2?x?a?modq?而兩個(gè)方程的解分別為

x??a?p?1?4（modp）和x??a?q?1?4（modq）利用中國剩余定理解聯(lián)立方程

p?1??x??a4?modp??q?1?x??a4?modq??得原方程的解為

x??（a其中，

p?14

（modp））uq±（aq?14（modq））vp（modpq）

34/49

《數(shù)論算法》第四章二次同余方程與平方剩余

，vp≡1（modq）uq≡1（modp）

解同余方程x2≡3（mod253）。

（解）253＝11·23，11≠23，二者均為形如4k＋3的素?cái)?shù)，

且??3??11??＝??3??23??＝1，解方程x2≡3（mod11），得

11?1x??34≡±33≡±5（mod11）

解方程x2≡3（mod23），得

23?1x??34≡±36≡±7（mod23）

利用中國剩余定理解聯(lián)立方程

??x??5?mod11??x??7?mod23?M＝11·23＝253，M1?23，M2＝11，計(jì)算

M?11＝1（mod11）

，M?12＝21（mod23）∴x≡±5·23·1±7·11·21（mod253）

≡±115±99

≡±16，±39，（mod253）

4.7合數(shù)的情形

方程

x2≡a（modm）

，（a,m）＝1m＝2?p?11p?p?22?kkx2≡a（modp?）

，（a,p）＝1，?＞135/49

1）3）（（

《數(shù)論算法》第四章二次同余方程與平方剩余

(一)P為奇素?cái)?shù)

?a?設(shè)p是奇素?cái)?shù)，則（3）有解???p??＝1。

??且有解時(shí)，（3）的解數(shù)為2。（證）必要性

?a?2?x≡a（mod）有解≡a（modp）有解p???x?p??＝1

??2?a?充分性：設(shè)??p??＝1，則存在整數(shù)x≡x1（modp）使得

??2≡a（modp）x1令f(x)＝x2－a，則f??x?＝2x，?f??x1?,＝1，故方程（3）的解數(shù)為2。

同余方程（3）的解數(shù)為

p?＝（2x1，p）

?a?T＝1＋??p??

??(二)P＝2

，（a,2）＝1，?＞1（4）x2≡a（mod2?）

（當(dāng)α＝1時(shí)，方程x≡a≡1（mod2）有一個(gè)解x≡1（mod2））

設(shè)?＞1，則同余方程（4）有解的必要條件

是

（i）當(dāng)?＝2時(shí)，a≡1（mod4）；（ii）當(dāng)?≥3時(shí)，a≡1（mod8）。

若上述條件成立，則（4）有解。且當(dāng)?＝2時(shí)，解數(shù)是2；

36/49

2《數(shù)論算法》第四章二次同余方程與平方剩余

當(dāng)?≥3時(shí)，解數(shù)是4。

（證）必要性：若（4）有解，則存在整數(shù)z，使得

z2≡a（mod2?）

由（a,2）＝1知（z,2）＝1，記z＝1＋2t，則上式可表為

a≡1＋4t(t＋1)（mod2）（5）

?（注：z2＝?1?2t?2＝1＋4t＋4t2）

所以當(dāng)?＝2時(shí)，a≡1（mod4）。

而當(dāng)?≥3時(shí)，由（5）知

a≡1＋4t(t＋1)（mod23＝8）

又由2│t(t＋1)知，a≡1（mod8）。

充分性：

（i）當(dāng)?＝2時(shí)，a≡1（mod4），方程

x2≡a≡1（mod22）

顯然有兩個(gè)解x≡1，3（mod22）

（ii）當(dāng)?≥3時(shí)，a≡1（mod8）。此時(shí)，若?＝3，易驗(yàn)證方程

x2≡a≡1（mod23）的解為x≡±1，±5（mod23），即

x＝±(1＋22t3)，t3＝0,±1,±2…

或x＝±(x23＋2t3)，t3＝0,±1,±2…其中，x3＝1,5。

若?＝4，方程為

37/49

6）

7）（（《數(shù)論算法》第四章二次同余方程與平方剩余

x2≡a（mod24）（8）

令x3?22t3≡a（mod24）

（由第三章結(jié)論，希望從方程（6）的解的值（7）中去找方程（8）的解，即確定t3）

22即x3＋2x3(22t3)＋24t3≡a（mod24）2亦即x3＋23x3t3≡a（mod24）

??24223x3t3≡a－x3（mod2）

2a?x3所以x3t3≡（mod2）322a?x3t3≡3（mod2）

2（注意x3≡1（mod2））或

2a?x3＋2t4，t4＝0,±1,±2…t3＝32代入（7），方程（8）的解可表為

（x＝±(x3＋2t3)，t3＝0,±1,±2…（7））

2a?x3x＝±(x3＋2t3)，t3＝3＋2t4，t4＝0,±1,±2…

2222a?x332＋t4)，t4＝0,±1,±2…x＝±(x3＋2322或x＝±(x4＋2t4)，t4＝0,±1,±2…

2a?x23其中x4＝x3＋2，且x4≡1（mod2）。323（由于a≡a?x32x3≡1（mod8），故3238/49

22a?x3＝整數(shù)，從而2322《數(shù)論算法》第四章二次同余方程與平方剩余

為偶數(shù)）

……

依次類推，對于α≥4，設(shè)同余方程

x2≡a（mod2??1）（9）

的解為

x＝±(x??1＋2??2t??1)，t??1＝0,±1,±2…（10）

或

，t??1＝0,1x≡±(x??1＋2??2t??1)（mod2??1）且x??1≡1（mod2）。

為了從方程（9）的上述解的值（10）中找出方程

x2≡a（mod2?）（11）

的解，令

?x即

??1?2??2t??1?≡a（mod2?）

2??22???2?22?22tx?2＋2()＋≡a（mod）xt??1?1??1??1亦即

??1?222＋≡a（mod）tx?x?1??1??1?22??1x??1t??1≡a－x?2（mod）（12）?1所以

2a?x?x??1t??1≡??1?1（mod2）

22a?x?t??1≡??1?1（mod2）

239/49

《數(shù)論算法》第四章二次同余方程與平方剩余

或

2a?x?t??1＝??1?1＋2t?，t?＝0,±1,±2…

2代入（10）式，方程（11）的解可表為

（x＝±(x??1＋2??2t??1)，t??1＝0,±1,±2…（10））

2a?x?1＋2t?，x＝±(x??1＋2??2t??1)，t??1＝???12t?＝0,±1,±2…

即x＝±(x??1＋2??22a?x???1?12＋t?)，??12t?＝0,±1,±2…

或

x＝±(x?＋2??1t?)，t?＝0,±1,±2…

其中x?＝x??1＋2??22a?x??1，且x?≡1（mod2）。??1222a?x?a?x??2??1（由于由式（12）可知??1?1＝整數(shù)，從而2為??122偶數(shù)）

解方程x≡57（mod64）。

（解）64＝2，即?＝6。因57≡1（mod8），故方程有4個(gè)解。

62?＝3時(shí)，解的值為

x＝±(1＋2t3)，t3＝0,±1,±2…（13）

（解的表示：x≡1，3，5，7（mod8），

40/49

2

《數(shù)論算法》第四章二次同余方程與平方剩余

或x≡±1，±5≡±7，±3（mod8）

或x≡±(1＋4t)≡±(3＋4t)（mod8），t＝0,1

還可表為：x≡±1，±3≡±7，±5（mod8）

或x≡±(1＋2t)≡±(5＋2t)（mod8），t＝0,1

此時(shí)方程為x2≡57≡1（mod8））（x3＝1）

?＝4時(shí)，在式（13）的所有值中找方程

x2≡57（mod2）（14）

的解。

4為此，令?1?2t?≡57（mod2）則

223442412＋2·1·(4t3)＋2t3≡57（mod2）