《数论算法》 第四章 二次同余方程与平方剩余
第 4 章 二次同余方程与平方剩余
内容 1. 二次同余方程，平方剩余 2. 模为奇素数的平方剩余 3. 勒让德符号、雅可比符号 4. 二次同余方程的求解 二次同余方程有解的判断与求解 要点 4.1 一般二次同余方程
(一) 二次同余方程
ax2＋bx＋c≡0（mod m），（a
(二) 化简
0（mod m）） （1）
?1?2设m＝p1p2?pkk，则方程（1）等价于同余方程
??ax2?bx?c?0（mod?2?ax?bx?c?0（mod?????ax2?bx?c?0（mod?问题归结为讨论同余方程
?1p1）?2p2） ?kpk）ax2＋bx＋c≡0（mod p?）， （pa） （2）
(三) 化为标准形式
p≠2，方程（2）两边同乘以4a，
4a2x2＋4abx＋4ac≡0（mod p?）
?2ax?b?2≡b2－4ac（mod
1/49
p?）
《数论算法》 第四章 二次同余方程与平方剩余
变量代换，
y＝2ax＋b （3）
有
y2≡b2－4ac（mod p?） （4）
当p为奇素数时，方程（4）与（2）等价。即 ? 两者同时有解或无解；有解时，对（4）的每个解
通过式（3）（x的一次同余方程，且（p, y?y0?modp?，
2a）＝1，所以解数为1）给出（2）的一个解x?x0?modp?，由（4）的不同的解给出（2）的不同的解；反之亦然。 ? 两者解数相同。
结论：只须讨论以下同余方程
x2≡a（mod p?） （5）
【例】化简方程7x2＋5x－2≡0（mod 9）为标准形式。 （解）方程两边同乘以4a＝4×7＝28，得
196x2＋140x－56≡0（mod 9）
配方 (14x＋5) 2－25－56≡0（mod 9） 移项 (14x＋5) 2≡81（mod 9） 变量代换 y＝14x＋5 得 y2≡0（mod 9）
（解之得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（mod 9））
2/49
《数论算法》 第四章 二次同余方程与平方剩余
(四) 二次剩余
【定义4.1.1】设m是正整数，a是整数，ma。若同余方程
x2≡a（mod m） （6）
有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的平方非剩余（或二次非剩余）。
问题：
（1） 设正整数a是模p的平方剩余，若记方程（6）中的
解为x≡a（mod m），那么此处的平方根a（mod m）与通常的代数方程x2＝a的解a有何区别？ （2） 如何判断方程（6）有解？ （3） 如何求方程（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，3，5，7，8，11，12，13，14
【例4】求满足方程E：y2≡x3＋x＋1（mod 7）的所有点。
（解）对 x＝0，1，2，3，4，5，6分别解出y： ，y≡1，6（mod 7） x＝0，y2≡1（mod 7）
3/49
《数论算法》 第四章 二次同余方程与平方剩余
，无解 x＝1，y2≡3（mod 7）
，y≡2，5（mod 7） x＝2，y2≡4（mod 7），无解 x＝3，y2≡3（mod 7），无解 x＝4，y2≡6（mod 7），无解 x＝5，y2≡5（mod 7），无解 x＝6，y2≡6（mod 7）
所以，满足方程的点为（0, 1），（0, 6），（2, 2），（2, 5）。 说明：方程E：y2≡x3＋x＋1的图形称为椭圆曲线。
4.2 模为奇素数的平方剩余与平方非剩余
模为素数的二次方程
x2≡a（mod p）, (a, p)＝1 （1）
因为??x?＝x2，故方程（1）要么无解，要么有两个
解。
2(一) 平方剩余的判断条件
【定理4.2.1】（欧拉判别条件）设p是奇素数，(a, p)＝1，则
（i）a是模p的平方剩余的充要条件是
a?p?1?2 ≡1（mod p） （2）
（ii）a是模p的平方非剩余的充要条件是
a?p?1?2 ≡－1（mod p） （3）
并且当a是模p的平方剩余时，同余方程（1）恰有两个解。
（证）先证pa时，式（2）或（3）有且仅有一个成立。 由费马定理 ap?1≡1（mod p）
4/49
《数论算法》 第四章 二次同余方程与平方剩余
?a??a?p?1?2?－1≡0（mod p）
?1??a???1?≡0（mod p） （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
且素数p>2。所以，p能整除a?p?1?2?1a?p?1?2?1，但p不能同时整除a?p?1?2?1和a?p?1?2?1（否则，p能整除它们的最大公因子1或2）
所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。
（i）必要性。若a是模p的二次剩余，则必有x0使得
2≡a（mod p）， x0??????????因而有
??2?p?1?2x0≡a?p?1?2（mod p）。
即 x0p?1?a?p?1?2（mod p）。 由于pa，所以p
x0，因此由欧拉定理知
。 x0p?1≡1（mod p）
即（2）式成立。 充分性。已知a一次同余方程
?p?1?2 ≡1（mod p），这时必有pa。故
bx≡a（mod p）, (1≤b≤p－1) （5）
有唯一解，对既约剩余系
－(p－1)/2，…，－1，1，…，(p－1)/2 （6）
由式（6）给出的模p的既约剩余系中的每个j，当b＝j时，
必有唯一的x?xj属于既约剩余系（6），使得式（5）成立。若a不是模p的二次剩余，则必有j?xj。这样，既约剩余
5/49
《数论算法》 第四章 二次同余方程与平方剩余
系（6）中的p－1个数就可按j、xj作为一对，两两分完。 （b1≠b2，则相应的解x1≠x2，且除了±1之外，每个数的逆不是它本身） 因此有
(p?1)!?a?p?1?2?modp?.
由威尔逊定理知
a?p?1?2??1?modp?.
与式（2）矛盾。所以必有某一j0，使j0?xj0，由此及式（5）知，a是模p的二次剩余。
（ii）由已经证明的这两部分结论，立即推出第（ii）条成立。
其次，若x00（mod p）是方程（1）的解，则－x0也是其解，且必有x0－x0（mod p）。故当(a, p)＝1时，方程（1）要么无解，要么同时有两个解。
（说明：本定理只是一个理论结果，当p>>1时，它并不是一个实用的判断方法）
小结：对于任何整数a，方程（1）的解数可能为
T(x2－a；p)＝0, 1, 2
【例1】设p＝19，验证定理4.2.1的证明过程。 （解）由费马定理知，对任何a＝1, 2, …, 18，都有a18≡1（mod 19）。方程x2≡1（mod 19）只有两个解，即x≡±1（mod 19）。从而必有
a9≡±1（mod 19）
（视a18?a9≡1（mod 19），即x?a9）
针对必要性：例如a＝17是模19的二次剩余，即存在x0≡6使得62≡17（mod 19）。那么必有
6/49
??2《数论算法》 第四章 二次同余方程与平方剩余
a?p?1?2≡179≡618≡1（mod 19）
针对充分性：例如a＝6，a?p?1?2≡69≡1（mod 19），验证6是二次剩余。解方程
bx≡6（mod 19）, (1≤b≤18)
当b≡1, 2, 3, 4, 5, …, 17, 18（mod 19）时，方程有唯一解x≡6, 3, 2, 11, 5, …, 16, 13（mod 19） 其中 5?5≡6（mod 19）
即当b≡5时，x≡5。所以6是二次剩余。
又选a＝8，a?p?1?2≡89≡－1（mod 19），验证：解方程
bx≡8（mod 19）, (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（mod 19）
【例2】判断137是否为模227的平方剩余。 （解）首先，227是素数。其次，计算
137?227?1?2≡－1（mod 227）
所以，137是模227的平方非剩余。
【推论】设p是奇素数，(a1, p)＝1，(a2, p)＝1，则 （i）若a1，a2都是模p的平方剩余，则a1a2是模p的平方剩余；
（ii）若a1，a2都是模p的平方非剩余，则a1a2是模p
7/49
《数论算法》 第四章 二次同余方程与平方剩余
的平方剩余；
（iii）若a1是模p的平方剩余，a2是模p的平方非剩余，则a1a2是模p的平方非剩余。
（证）因?a1a2??p?1?2＝a1?p?1?2a2?p?1?2
(二) 平方剩余的个数
【定理4.2.2】设p是奇素数，则模p的既约剩余系中平方剩余与平方非剩余的个数各为(p－1)／2，且(p－1)／2个平方剩余恰与序列
?p?1?221，2，…，?? ?2?中的一个数同余。
（证）由定理4.2.1，模p的平方剩余个数等于方程
2x的解数。但
p?12≡1（mod p）
xp?12?1xp?1
p?1由定理3.4.5知，方程的解数为，即平方剩余的个数是
2p?1p?1p?1，且平方非剩余的个数是(p－1)－＝。 222p?1p?1其次，可以证明当1≤k1≤，1≤k2≤，且k1
222≠k2时，有k12 mod p。故结论成立。 k2（定理3.4.5：设p为素数，n为正整数，n≤p。则同余方程
nn?1f?x?＝x?an?1x???a1x?a0≡0 mod p有n个解
?xp?x被f?x?除所得余式的所有系数都是p的倍数）
8/49
《数论算法》 第四章 二次同余方程与平方剩余
4.3 勒让德符号
目的：快速判断整数a是否为素数p的平方剩余。 (一) 勒让德符号
【定义4.3.1】设p是素数，定义勒让德（Legendre）符号为：
?1,当a是模p的二次剩余；?a??L(a, p)＝? ?p??＝??1,当a是模p的二次非剩余；????0,当pa。?a?【推论】整数a是素数p的平方剩余的充要条件是??p??＝
??1。
（证）由定义4.3.1。
因此，判断平方剩余转化为计算勒让德符号的值。
【例1】直接计算，得
?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 （注：本例仍是利用平方剩余而得到勒让德符号值）
问题：反过来，如何快速计算勒让德符号的值，以判断平方剩余。
9/49
《数论算法》 第四章 二次同余方程与平方剩余
(二) （勒让德符号的）性质
【性质1】（欧拉判别法则）设p是奇素数，则对任意整数a，有
?a???p??＝a??
p?12（mod p）
（证）由定理4.2.1即知。
?1?【性质2】??p??＝1
??（证）显然（因为方程x2≡1（mod p）始终有解x≡±1（mod p），或者由性质1立得）。
??1??p?1?2??【性质3】?＝。 ?1??p???（证）由性质1即得。
??1???1?【例2】??＝1，??＝－1
?17??19?
??1??1,p?1?mod4?【推论】??p??＝??1,p?3?mod4? ???（证）p≡1（mod 4）? p＝4k＋1?
??1??p?1?22k????＝＝＝1 ?1?1???p???p≡3（mod 4）? p＝4k＋3?
10/49
《数论算法》 第四章 二次同余方程与平方剩余
??1??p?1?22k?1????＝＝＝－1 ?1?1???p???另一种描述：设素数p>2，则－1是模p的二次剩余的充
分必要条件是p≡1（mod 4）。
【性质4】???a?p??a???＝? ????p??p?（证）因x2≡a＋p（mod p）? x2≡a（mod p）
?a??b?【推论】若a≡b（mod p），则??p??＝??p??
????
?ab??a??b?【性质5】??p??＝??p????p??
??????p?1?ab?（证）因??p??＝?ab?2＝a??p?1p?1?2b2＝?a??b??p????p?? ?????ak【推论1】??p???a??＝?? ??p????k?a2??【推论2】当pa时，??p?＝1 ??
讨论：确定a是否是模p的平方剩余就变为如何计算
?a??a?Legendre符号?的值。上述性质可以用来计算???p??p??，并由
????算术基本定理，设a 的分解式为
11/49
《数论算法》 第四章 二次同余方程与平方剩余
?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）故只要能计算出
??1??2??q???p??，??p?? ?p??，????????a?就可以计算出任意的??p??，其中q?2是小于p的素数。
????1?已经解决的计算：??p?? ??剩余的问题：???2??q???，?的计算。 ????p??p?解决这些问题的基础是下面的二次互反律（Gauss定理）。
p?1?2?【性质6】??p??＝??1?8
??17?11816?2??【例3】??＝??1?8＝??1?24＝1，
?17?2219?12018?2????＝??1?8＝??1?42＝－1，故2是模17的平方?19?2剩余，但不是模19的平方剩余。
【推论】p为奇素数，则
12/49
《数论算法》 第四章 二次同余方程与平方剩余
?2??1,p??1?mod8???p??＝??1p??3?mod8? ???（证）因为 当p＝8k＋1时
p2?1?p?1??p?1??8k?2?8k＝＝＝k(8k＋2)＝偶数 888当p＝8k＋3时
p2?1?8k?4??8k?2?＝＝(2k＋1)(4k＋1)＝奇数
88?2?【例4】由于31≡7≡－1（mod 8），59≡3（mod 8），故???31??2?＝1，??＝－1，即2是模31的平方剩余，但不是模59
?59?的平方剩余。
【性质7】（二次互反律，高斯定理）p≠q且均为奇素数，则
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（mod p）
和
x2≡p（mod q）
13/49
《数论算法》 第四章 二次同余方程与平方剩余
是否有解，即q是否是模p的二次剩余和p是否是模q的二次剩余，其中正好是模与剩余互换了位置，而性质7恰好刻画了两者之间的关系，故称为二次互反律。
说明2：由欧拉提出，高斯首先证明。已有一百五十多个
不同的证明。由二次互反律引伸出来的工作，导致了代数数论的发展和类域论的形成。
【推论】（i）设奇素数p、q中至少有一个模4为1，则 方程x2≡q（mod p）有解?方程x2≡p（mod q）有解 （ii） 若p≡q≡3（mod 4），则
方程x2≡q（mod p）有解?方程x2≡p（mod q）无解 （证）（i）设p≡1（mod 4），即p＝4k＋1，则
p?1p?1?p?4kp?1?p??p??q???2222????p??＝??1??q??＝??1??q??＝??q??
????????（ii）此时，p＝4s＋3，q＝4t＋3，则
p?1p?1?p?4s?24t?2?p??p??q???2222????p??＝??1??q??＝??1??q??＝－??q??
????????
【例5】判断3是否是模17的平方剩余。
17?13?117?3????2??（解）??＝??1?22??＝??＝－1
?17??3??3?所以，3是模17的平方非剩余。（不但如此，17也是3的平方非剩余，即2是3的平方非剩余）
【例6】判断同余方程x2≡137（mod 227）是否有解。 （解）已知137与227均为奇素数，所以
14/49
《数论算法》 第四章 二次同余方程与平方剩余
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?【例7】判断同余方程x2≡－1（mod 365）是否有解，若有解，求解数。
（解）由于365＝5·73，所以
2?x??12
x≡－1（mod 365）? ?2?x??1?mod5?
?mod73???1???1???＝??＝1 ?5??73?所以方程有解，且解数为4。
【例8】判断同余方程x≡2（mod 3599）是否有解，若有解，求解数。
（解）由于3599＝59·61，所以
215/49
《数论算法》 第四章 二次同余方程与平方剩余
2?x?22x≡2（mod 3599） ? ?2?x?2?mod59?
?mod61??2?因为59≡3（mod 8），即??＝－1，故方程x2≡2（mod 59）
?59?无解，从而原方程无解。
【例9】证明形如4k＋1的素数有无穷多。
（证）反证法：不然，形如4k＋1的素数为有限个，设为p1，p2，…，pk，令
a＝?2p1p2?pk?2?1＝4b＋1
即a 也形如4k＋1且a＞pi（i＝1,2,…, k）。所以a 为合数，设其素因数p 为奇数，则
2??1???1?a???2p1p2?pk???＝1 ??p??＝??p??＝???p??????所以－1为模p平方剩余。由性质3的推论，p≡1（mod 4），??1?即p也是形如4k＋1的素数。（【推论】??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
《数论算法》 第四章 二次同余方程与平方剩余
(二) 应用
【例1】求所有奇素数p，它以3为其平方剩余。
?3?（解）即求所有奇素数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?（排除偶数） ??＝??3????1???,p??1?mod6????3?知
?3???p??＝1 ??即
?p?1? ??p?1?mod4??p??1?mod4? 或 ? ?mod6??p??1?mod6?p≡1（mod 12）或p≡－1（mod 12）
故3是模p二次剩余 ? p≡±1（mod 12）
?d?【例2】设p为奇素数，d是整数。若??p??＝－1，则p一
??定不能表示为x2?dy2的形式。
（证）用反证法。设p有表达式x2?dy2，则由p是素数
17/49
《数论算法》 第四章 二次同余方程与平方剩余
可知(x, p)＝(y, p)＝1。这是因为若(x, p)≠1，则必有
px
?
px2?p?dy2
?d?2
但由?＝－1知(d, p)＝1，所以p│y，进而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
????????????与题设矛盾。
?a?【性质8】同余方程x2?a?modp?的解数是1???p??。
??
【问题】求所有奇素数p，它以5或－2为其平方剩余。
4.5 雅可比符号
?a?（1） 问题：在计算勒让德符号??p??时，若a为奇数，但非
???a?素数，如何快速计算??p??。
??（2） 目的：为了快速计算勒让德符号。 (一) 雅可比符号
18/49
《数论算法》 第四章 二次同余方程与平方剩余
【定义4.5.1】设m＝p1p2…pk是奇素数pi的连乘积（pi可以重复），对任意整数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） 两者的本质区别：勒让德符号可用来判断平方剩余，
但雅可比符号却不能。即当k＞1时，如果J(a, m)＝－1，则方程x2≡a（mod m）无解（因为至少存?a?2?在一个pi，使得?＝－1，即方程≡a（mod x?p??i?，pi）无解，从而原方程x2≡a（mod m）也无解）但当J(a, m)＝1时，方程x≡a（mod m）则不一
定有解。
（4） 当k＝1时，J(a, m)＝ L(a, m)，即此时勒让德符号
的值与雅可比符号的值相等。 （5） 因此，求勒让德符号的值转化为计算雅可比符号。
【例1】由定义4.5.1
2?2??2??2???＝????＝(－1)(－1)＝1 ?9??3??3?但可以验证2是模9的平方非剩余。
19/49
《数论算法》 第四章 二次同余方程与平方剩余
又如当奇素数p≡3（mod 4）时，由勒让德符号的性质知，－1是模P的非平方剩余，即方程x2≡－1（mod p）无解，从而方程x2≡－1（mod p）也无解。即－1是模p的平方非剩余。但若取m＝p，则总有
222??1???1???1???p????p??＝(－1)(－1)＝1 ?p2??＝???????
问题：如何快速计算雅可比符号的值，以帮助加速勒让
德符号的求值过程，从而加速判断平方剩余。 (二) （雅可比符号的）性质
?a?【性质1】若(a, m)＝1，则J(a, m)＝??＝±1；若(a, m)
?m??a?＞1，则J(a, m)＝??＝0。
?m??a?（证）因(a, m)＞1时，至少有某个pia，即??p??＝0，从
?i??a?而??＝0。 ?m?【例2】a＝15，m＝39，则
?a??15??15??15?J(a, m)＝??＝??＝????
?m??39??3??13??2??0??2?＝????＝0??＝0
?13??3??13?
?1?【性质2】??＝1
?m?20/49
《数论算法》 第四章 二次同余方程与平方剩余
?1??1??1??1?????（证）J(1, m)＝??＝?＝1 ?????????m??p1??p2??pk?
m?1??1?【性质3】??＝??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?（mod 4），即
i?1km－1≡??pi?1?（mod 4）
kp?1m?1≡?i（mod 2）
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≡1 mod 4 ? m＝4k＋1?
m?1??1?2k??＝??1?2＝??1?＝1 ?m?m≡3 mod 4
? m＝4k＋3?
m?12k?1??1?＝－1 ??＝??1?2＝??1??m?21/49
《数论算法》 第四章 二次同余方程与平方剩余
??1???1?【例3】?＝1，???＝－1
?33??51?
?a?m??a?【性质4】??＝??
?m??m?（证）首先，由m＝p1p2…pk和m＋a≡a（mod m）知
m＋a≡a（mod pi）
其次，由雅可比符号和勒让德符号性质知
?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（mod m），则??＝??
?m??m?（证）显然
?ab??a??b?【性质5】??＝????
?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
《数论算法》 第四章 二次同余方程与平方剩余
?a??b?＝???? ?m??m?
k?ak??a?【推论1】??m??＝?m?
?????a2?【推论2】当(m, a)＝1时，??m??＝1
??
m2?18
?2?【性质6】??＝??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（mod 64）
2??i?1而对任何奇数q，都有q≡1（mod 8）（i＝1,2,…, k），故
kpi2?1m2?1≡?（mod 8）
88i?1kpi2?1m2?1≡?（mod 2）
88i?12?2??2??2??2?????所以 J(2, m)＝ ??＝?…? ???????m??p1??p2??pk?＝
??1?222p1?1p2?1pk?1???888＝
??1?m2?18
【推论】m为奇数，则
23/49
《数论算法》 第四章 二次同余方程与平方剩余
?2??1,m??1?mod8? ??＝??m???1m??3?mod8?（证）因为 当m＝8k＋1时
m2?1?m?1??m?1??8k?2?8k＝＝＝k(8k＋2)＝偶数 888当m＝8k＋3时
m2?1?8k?4??8k?2?＝＝(2k＋1)(4k＋1)＝奇数 88
?2??2??2??2?【例4】??＝??＝1，??＝??＝－1。
?3?19??57??5?7??35?
【性质7】（二次互反律，高斯定理）设m、n都是奇数，
则
m?1n?1m?n???22???1＝?? ???n??m?m?1n?1?n??m?或 ????＝??1?22
?m??n?
【性质8】m1、m2、a为整数，则
?a??a??a???mm??＝??m????m?? ?12??1??2?（证）设m1＝p1p2…ps，m2＝q1q2…qs，则
?a??a??a??a左边＝J(n, m1m2)＝??p??…??q??…??p????q?1??s??1??t24/49
??? ?《数论算法》 第四章 二次同余方程与平方剩余
＝ J(a, m1)·J(a, m2)＝右边
这样，计算勒让德符号的值就转化为了计算雅可比符号
的值。而后者的求值要比前者快了许多。
【例5】用雅可比符号计算： (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
《数论算法》 第四章 二次同余方程与平方剩余
503?1165?1503???8??2??165??(iv) ?2??＝??＝?? ?＝??1?2?503??165??165??165?
＝??1?
1652?1＝－1 8【例6】同余方程x2≡286（mod 563）是否有解。 （解）563为素数，计算勒让德符号
?286??2??143???＝????＝??1??563??563??563?5632?18??1?563?1143?122?563??? ?143?143?1??9???1?＝??＝??＝??1?2＝－1 ?143??143?所以，原方程无解。
【例7】判断同余方程x2≡88（mod 105）是否有解。 （解）105＝3·5·7为合数，直接计算雅可比符号
3105?111?11051052?1?88??2??11????228????1??＝?1??＝??? ?????105??105??105??11?143?1?6???1?＝－??＝??＝??1?2＝－1
?11??143?
所以，原方程无解。（因为原方程等价于方程组?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，说明??、??、??三者中至少有一个?105??3??5??7?26/49
《数论算法》 第四章 二次同余方程与平方剩余
为－1，即方程组中至少有一个方程无解，从而原方程无解）。
再次说明雅可比符号可以用来否定方程有解，但不能肯定方程有解。
【例8】求同余方程x2≡38（mod 385）的解数。 （解）385＝7·5·11为合数，直接计算雅可比符号
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?中的每个方程是否有解。故再11??38??3?计算勒让德符号??＝??＝－1，因此方程x2≡38（mod
?5??5?5）无解，最终说明原方程解数为零。
4.6 模p平方根
（1） 目的：解同余方程
x2≡a（mod p），p为素数且pa （1）
（2） 方法：逐步迭代
设p－1＝2ts。
27/49
《数论算法》 第四章 二次同余方程与平方剩余
(一) 理论基础
理论基础：a是模p的平方剩余的充要条件（欧拉定理）
Z＝a若t>1则（p?12≡1（mod p）
p?1?2t?1s＝偶数） 2p?12Z≡a2≡±1（mod p）
若Z≡1（mod p）且t＞2，继续开方；否则，构造N，使
NrZ≡1（mod p）
又可以继续开方。其中N为模p的平方非剩余（即
Np?12??1?modp?）。
g?目标：构造N，使得：??a?从而得方程（1）的解：x≡±(二) 算法
s?12?N??≡a（mod p）
?g2s?1a2Ng（mod p）
将偶数p－1表为p－1＝2s，t≥1，s为奇数。
t?N?sN?（1）选模p的平方非剩余N，即?＝－1，令b≡?p???（mod p），则有
b＝?N2tt?1ts2?＝Nt?12ts＝Np?12p?1≡1（mod p）
b2＝N2s＝N≡－1（mod p）
tt?1即b是模p的2次单位根，但非模p的2次单位根。
（2）计算： xt?1≡
s?1a2（mod p）
28/49
《数论算法》 第四章 二次同余方程与平方剩余
则y＝a（因y2?1x2t?1满足方程：
y22t?1≡1（mod p）
p?12t?1＝a?1xt2?12??2t?1＝at?1s＝a≡1（mod p））
即y＝a?1xt?1是模p的2t?1次单位根。
s?1a2（3）若t＝1，则x＝xt?1＝x0≡程
（mod p）满足方
x2≡a（mod p）
（此时p－1＝2s，x2＝as?1＝a已经解出） p?1?12≡a（mod p）。即方程2否则，t≥2，寻找xt?2，使得y＝a?1xt?2满足方程
y22t?2≡1（mod p）
t?2即y＝a?1xt?2是模p的2（a）若
次单位根。
?a（b）若
?1x2t?22t?1?≡1（mod p）
令j0＝0，xt?2＝xt?1b0≡xt?1（mod p），则xt?2即为所求。
j?a2t?2?1x2t?22t?1?j≡－1（mod p）
令j0＝1，xt?2＝xt?1b0＝xt?1b（mod p），则xt?2即为所求。 （因y
29/49
＝ax＝axb≡(－1)(－1)≡1（mod p））
??12t?22t?2???1t?2222t?1?＝ax??1t?222t?1?b2t?1《数论算法》 第四章 二次同余方程与平方剩余
（4）若t＝2，则x＝xt?2＝x0＝x1b0≡p）满足方程
js?1a2bj0（mod
x2≡a（mod p） p?1（此时p－1＝2s，x≡ap）） 22s?1b2j0≡a22?1b2j0≡a（mod 2否则，t≥3，寻找xt?3，使得y＝a?1xt?3满足方程
y22t?3≡1（mod p）
t?3即y＝a?1xt?3是模p的2（a）若
次单位根。
?a（b）若
?1x2t?32t?2?≡1（mod p）
令j1＝0， xt?3＝xt?2b所求。
j12≡xt?2（mod p），则xt?3即为
?a…… 依次类推
?1x2t?32t?2?≡－1（mod p）
令j1＝1，xt?3＝xt?2b所求。
j12≡xt?2b2（mod p），则xt?3即为
（k＋1）设找到整数xt?k满足
y即y＝a?12t?k≡1（mod p）
xt2?k是模p的2t?k次单位根：
30/49
《数论算法》 第四章 二次同余方程与平方剩余
?a?1x2t?k2≡1（mod p） t?k?（k＋2）若t＝k，则x≡xt?k≡x0（mod p）满足方程
x2≡a（mod p）
否则，t≥k＋1，寻找整数xt??k?1?，使得y＝a?1xt??k?1?满足方程
2y22t??k?1?≡1（mod p）
t??k?1?即y＝a?1xt??k?1?是模p的2（a）若
次单位根。
?a?1x2t??k?1?2t?k?≡1（mod p）
＝xt?k（mod p），则
令jk?1＝0，xt??k?1?≡xt?kbjk?12k?1xt??k?1?即为所求。
（b）若
?a?1x2t??k?1?2t?k?≡－1（mod p）
＝xt?kb2k?1令j0＝1，xt??k?1?≡xt?kb则xt??k?1?即为所求。
最后，k＝t－1：
jk?12k?1（mod p），
x＝x0
≡x1bjt?22t?2
（mod p）
≡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
《数论算法》 第四章 二次同余方程与平方剩余
满足方程：x2≡a（mod p），p为素数且pa
(三) 例
【例1】用上述方法解同余方程x2≡186（mod 401） （解）a＝186，p＝401。
判断：p＝401为素数，且（用雅可比符号计算）
?186??2??93???＝????＝1·1＝1 ?401??401??401?或（用勒让德符号计算）
?186??2??3??31?(－1) ·(－1)＝1 ??＝??????＝1·
?401??401??401??401?故原方程有解。
准备：p－1＝401－1＝400＝2·25，其中t＝4，s＝25。
4?3?（1）由上边计算，??＝－1，即N＝3是模401的
?401?s25平方非剩余。令b≡N≡3≡268（mod 401）。
（2）计算
s?1a225?12x3≡
（3）因为
≡186≡103（mod 401）
a?1≡ap?2≡186399≡235（mod 401）
?a?1x2223?≡235?103j?222?≡?98?≡－1（mod 401）
4故令j0＝1，x2≡x3b0≡103·268≡336（mod 401）。 （此时，x3?a（4）因为
s?12?18613，x2?as?12b?18613?325）
32/49
《数论算法》 第四章 二次同余方程与平方剩余
?a?122x2≡
??235?336?≡1（mod 401）
22故令j1＝0，x1?x2bj1?2?x2≡336（mod 401）。 （此时，x1?x2b0?a（5）因为
s?12b?18613?325）
?a?1x0221?3362≡－1（mod 401） ≡235·
2故令j2＝1，x0≡x1bj2?2≡336·2684≡304（mod 401）。 （此时，x1?x1b4?a则
s?152b?18613?3175）
x≡x0≡304（mod 401）
满足原方程。
2（验证，x0） ?3042＝92416＝186（mod 401）
【例2】设p是形为4k＋3的素数，若方程
x2≡a（mod p）
有非零解，则其解为
x≡±ap?14（mod p）
p?1为奇数，而方程 2（解）因为p＝4k＋3，故q＝
x2≡a（mod p）
有解，则a是模p的二次剩余，从而有
p?12aq≡1（mod p）
即 a≡1（mod p）
33/49
《数论算法》 第四章 二次同余方程与平方剩余
已知原方程有非零解，即（a, p）＝1，故有
aq?1≡a（mod p）
即
aq?1≡
?q?1?a2????≡a（mod p） ??2?122∴ x≡±
q?1a2?p?1?≡±a≡±ap?14（mod p）
?a??a?【例3】设p≠q均为形如4k＋3的素数，且??q??＝?p??＝?????1，求解同余方程：
x2≡a（mod pq）
（解）首先
2?x?a?modp?2 x≡a（mod pq）??2?x?a?modq?而两个方程的解分别为
x??a?p?1?4（mod p）和x??a?q?1?4（mod q） 利用中国剩余定理解联立方程
p?1??x??a4?modp? ?q?1?x??a4?modq??得原方程的解为
x??（a其中，
p?14
（mod p））uq±（aq?14（mod q））vp （mod pq）
34/49
《数论算法》 第四章 二次同余方程与平方剩余
， vp≡1（mod q） uq≡1（mod p）
【例3】解同余方程x2≡3（mod 253）。
（解）253＝11·23，11≠23，二者均为形如4k＋3的素数，
且??3??11??＝??3??23??＝1， 解方程 x2≡3（mod 11），得
11?1x??34≡±33≡±5（mod 11）
解方程x2≡3（mod 23），得
23?1x??34≡±36≡±7（mod 23）
利用中国剩余定理解联立方程
??x??5?mod11??x??7?mod23? M＝11·23＝253，M1?23，M2＝11，计算
M?11＝1（mod 11）
，M?12＝21（mod 23） ∴ x≡±5·23·1±7·11·21（mod 253）
≡±115±99
≡±16，±39，（mod 253）
4.7 合数的情形
方程
x2≡a（mod m）
，（a, m）＝1 m＝2?p?11p?p?22?kk x2≡a（mod p?）
，（a, p）＝1 ，?＞1 35/49
1） 3） （ （《数论算法》 第四章 二次同余方程与平方剩余
(一) P为奇素数
?a?【定理4.7.1】设p是奇素数，则（3）有解???p??＝1。
??且有解时，（3）的解数为2。 （证）必要性
?a?2?x≡a（mod ）有解≡a（mod p）有解p???x?p??＝1
??2?a?充分性：设??p??＝1，则存在整数x≡x1（mod p）使得
??2≡a（mod p） x1令f(x)＝x2－a，则f??x?＝2x，?f??x1?,＝1，故方程（3）的解数为2。
【推论】同余方程（3）的解数为
p?＝（2x1，p）
?a?T＝1＋??p??
??(二) P＝2
，（a, 2）＝1 ，?＞1 （4） x2≡a（mod 2?）
（当α＝1时，方程x≡a≡1（mod 2）有一个解x≡1（mod 2））
【定理4.7.2】设?＞1，则同余方程（4）有解的必要条件
是
（i） 当?＝2时，a≡1（mod 4）； （ii） 当?≥3时，a≡1（mod 8）。
若上述条件成立，则（4）有解。且当?＝2时，解数是2；
36/49
2《数论算法》 第四章 二次同余方程与平方剩余
当?≥3时，解数是4。
（证）必要性：若（4）有解，则存在整数z，使得
z2≡a（mod 2?）
由（a, 2）＝1知（z, 2）＝1，记z＝1＋2t，则上式可表为
a≡1＋4t(t＋1) （mod 2） （5）
?（注：z2＝?1?2t?2＝1＋4t＋4t2）
所以当?＝2时，a≡1（mod 4）。
而当?≥3时，由（5）知
a≡1＋4t(t＋1) （mod 23＝8）
又由2│t(t＋1)知，a≡1（mod 8）。
充分性：
（i）当?＝2时，a≡1（mod 4），方程
x2≡a≡1（mod 22）
显然有两个解 x≡1，3（mod 22）
（ii）当?≥3时，a≡1（mod 8）。此时， 若?＝3，易验证方程
x2≡a≡1（mod 23） 的解为 x≡±1，±5（mod 23），即
x＝±(1＋22t3)，t3＝0, ±1, ±2…
或 x＝±(x23＋2t3)，t3＝0, ±1, ±2… 其中，x3＝1, 5。
若?＝4，方程为
37/49
6）
7） （（《数论算法》 第四章 二次同余方程与平方剩余
x2≡a（mod 24） （8）
令 x3?22t3≡a（mod 24）
（由第三章结论，希望从方程（6）的解的值（7）中去找方程（8）的解，即确定t3）
22即 x3＋2x3(22t3)＋24t3≡a（mod 24） 2亦即 x3＋23x3t3≡a（mod 24）
??24223x3t3≡a－x3（mod 2）
2a?x3所以 x3t3≡（mod 2） 322a?x3t3≡3（mod 2）
2（注意x3≡1（mod 2））或
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（mod 2）。 323（因为a≡a?x32x3≡1（mod 8），故3238/49
22a?x3＝整数，从而2322《数论算法》 第四章 二次同余方程与平方剩余
为偶数）
……………………
依次类推，对于α≥4，设同余方程
x2≡a（mod 2??1） （9）
的解为
x＝±(x??1＋2??2t??1)，t??1＝0, ±1, ±2… （10）
或
，t??1＝0, 1 x≡±(x??1＋2??2t??1)（mod 2??1）且x??1≡1（mod 2）。
为了从方程（9）的上述解的值（10）中找出方程
x2≡a（mod 2?） （11）
的解，令
?x即
??1?2??2t??1?≡a（mod 2?）
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（mod 2）
22a?x?t??1≡??1?1（mod 2）
239/49
《数论算法》 第四章 二次同余方程与平方剩余
或
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（mod 2）。 ??1222a?x?a?x??2??1（因为由式（12）可知??1?1＝整数，从而2为??122偶数）
【例1】解方程x≡57（mod 64）。
（解）64＝2，即?＝6。因57≡1（mod 8），故方程有4个解。
62?＝3时，解的值为
x＝±(1＋2t3)，t3＝0, ±1, ±2… （13）
（解的表示：x≡1，3，5，7（mod 8），
40/49
2《数论算法》 第四章 二次同余方程与平方剩余
或 x≡±1，±5≡±7，±3（mod 8）
或 x≡±(1＋4t)≡±(3＋4 t)（mod 8），t ＝0, 1
还可表为： x≡±1，±3≡±7，±5（mod 8）
或 x≡±(1＋2t)≡±(5＋2 t)（mod 8），t ＝0, 1
此时方程为x2≡57≡1（mod 8）） （x3＝1）
?＝4时，在式（13）的所有值中找方程
x2≡57（mod 2） （14）
的解。
4为此，令 ?1?2t?≡57（mod 2）则
223442412＋2·1· (4t3)＋2t3≡57（mod 2）
即
12＋23·1·t3≡57（mod 24）
23·1·t3≡57－12（mod 24）
57?121·t3≡3≡1（mod 2）
257?12t3≡3≡1（mod 2）
2或
57?12t3＝3＋2t4＝1＋2t4，t4＝0, ±1, ±2…
2代入（13）式得方程（14）的解为
（x＝±(1＋2t3)，t3＝0, ±1, ±2… （13））
41/49
2《数论算法》 第四章 二次同余方程与平方剩余
x＝±(1＋2·1＋2t4)＝±(5＋2t4)，t4＝0, ±1, ±2… 或 x≡±(5＋2t4)（mod 2），t4＝0, 1 或 x≡±5，±13≡±3，±5（mod 2） （x4＝5）
2，则 ?＝5时，令 ?5?8t4?≡57（mod 25）
23334462552＋2·5· (23t4)＋2t4≡57（mod 2）
24·5·t4≡57－52（mod 25）
57?525·t4≡≡0（mod 2） 4257?52≡0（mod 2） t4≡42或 t4＝0＋2t5＝2t5，t5＝0, ±1, ±2… 故方程 x2≡57（mod 25）的解为
x＝±(5＋2·0＋2t5)＝±(5＋2t5)，t5＝0, ±1, ±2… 或 x≡±(5＋2t5)（mod 2），t5＝0, 1 或 x≡±5，±21≡±5，±11（mod 2） （x5＝5）
，则 ?＝6时，令 ?5?24t5?≡57（mod 26）
23444554252＋2·5· (2t5)＋28t5≡57（mod 26）
25·5·t5≡57－52（mod 26）
42/49
《数论算法》 第四章 二次同余方程与平方剩余
57?525·≡1（mod 2） t5≡5257?52≡1（mod 2） t5≡52或
t5＝1＋2t6，t6＝0, ±1, ±2…
故方程 x2≡57（mod 26）的解为
1＋25t6)＝±(21＋25t6)，t6＝0, ±1, ±2… x＝±(5＋24·或
56，t6＝0, 1 x??(21＋2t6)（mod 2）
或
6x≡±21，±53≡±11，±21（mod 2）
（x6＝21）
4.8 解同余方程总结
(一) 方法
（1） 一般方程方程 f(x) ≡0（mod m）化为等价方程组
?f?x??0??f?x??0??f?x??0?????f?x??0??k?1?2其中m＝2?p1 p2?pkmodmodmodmod2??1p1?2 p2?kpk（2） 解素数幂方程
43/49
《数论算法》 第四章 二次同余方程与平方剩余
f(x)≡0（mod p?）， p为素数
（3） deg(f)＝2，?＝1，p＝2或奇素数的解法 （4） deg(f)＝2，?≥2，p＝2或奇素数的解法 （5） deg(f)＞2，若已知?＝1时的解，求?≥2时的解
(二) 问题
（1）m的分解
（2）deg(f)＞2，?＝1时的解法
习题4
1． 求满足下列方程的所有整点： （1）E：y2?x3?2x?3（mod 7）； （2）E：y2?x3?5x?1（mod 7）； （3）E：y2?x3?x?1（mod 17）； （4）E：y2?x3?3x?1（mod 17）。 2． 利用欧拉判别条件判断：
（1）－8是否是模53的二次剩余； （2）8是否是模67的二次剩余。 3． 求下列同余方程的解数： （1）x2≡2（mod 67）； （2）x2≡－2（mod 67）； （3）x2≡2（mod 37）； （4）x2≡－2（mod 37）； （5）x2≡1（mod 221）； （6）x2≡－1（mod 427）； 4． 计算下列勒让德符号：
44/49
《数论算法》 第四章 二次同余方程与平方剩余
?143??13??30?（1）??； （2）??； （3）??；
?47??53??53??71???35???23?（4）??； （5）?； （6）???；
?73??97??131??7???105??91?（7）?； （8）； （9）????； ??223??563??223???70???286??789?（10）?； （11）； （12） ??。????1193??571??647?5． 判断下列同余方程是否有解，若有解，请求其解数：
（1）x2≡7（mod 227）； （2）x2≡249（mod 257） （3）x2≡79（mod 433）； （4）x2≡365（mod 389） （5）x2≡11（mod 511）； （6）x2≡2495（mod 5249）； （7）11x2≡－6（mod 91）； （8）5x2≡－14（mod 6193）。 6． 解下列同余方程：
（1）8x2?15x－6≡0（mod 56）； （2）x2?x＋4≡0（mod 32）
7． 按要求完成下列问题： （1） 求以－3为其二次剩余的全体素数； （2） 求以±3为其二次剩余的全体素数； （3） 求以±3为其二次非剩余的全体素数； （4） 求以3为二次剩余、以－3为二次非剩余的全体
素数； （5） 求以－3为二次剩余、以3为二次非剩余的全体
素数； 8． 求以3为二次非剩余、以2为二次剩余的全体素数（即以3为正的最小二次非剩余的全体素数）。
9． 完成以下问题：
?5?（1） 求满足??p??＝1的全体素数p；
??45/49
《数论算法》 第四章 二次同余方程与平方剩余
??5?（2） 求满足??p??＝1的全体素数p；
??（3） 求1212?5，822?5?112，2732?5?112的素因
数分解式；
（4） 判断方程x4≡25（mod 1013）是否有解。 ?d?10． 设素数p＝4m＋1，d│m。证明： ??p??＝1。
??11． 设p是奇素数，pa。证明：存在整数u和v，使得u2?av2≡0（mod p）的充分必要条件是－a是模p的二次剩余。其中?u,v?＝1。
12． 设p是奇素数，证明：
（1） 模p的所有二次剩余的乘积对模p的剩余是
??1??p?1?2；
（2） 模p的所有二次非剩余的乘积对模p的剩余是
??1??p?1?2；
（3） 模p的所有二次剩余之和对模p的剩余是（1当
； p＝3时）或0（当p＞3时）
（4） 所有模p的二次非剩余之和是多少？ 13． 证明下列形式的素数均有无穷多个： （1）8k－1，8k＋3，8k－3；
（2）3k＋1，6k＋1，12k＋1，12k＋7； （3）十进制表示末尾为9的数。
14． 设n4?n2?1的素因数为p，证明：p≡1（mod 12）。 15． 设p是奇素数，且p≡1（mod 4）。证明：
（1） 1, 2, …, (p－1)/2中模p的二次剩余与非剩余
的个数均为个(p－1)/4；
（2） 1, 2, …, p－1中有(p－1)/4个偶数为模p的
二次剩余，(p－1)/4个奇数为模p的二次剩余； （3） 1, 2, …, p－1中有(p－1)/4个偶数为模p的
46/49
《数论算法》 第四章 二次同余方程与平方剩余
二次非剩余，(p－1)/4个奇数为模p的二次非剩余；
（4） 1, 2, …, p－1中全体模p的二次剩余之和等
于p(p－1)/4；
（5） 1, 2, …, p－1中全体模p的二次非剩余之和
等于p(p－1)/4。 16． 设p是奇素数。把集合Z?p??1,2,?,?p?1??分为两个非空子集S1和S2，且满足：属于同一个子集中的两个数的乘积必与S1中的某个数同余于模p，属于不同子集的两个数的乘积必与S2中的某个数同余于模p。证明：S1由Z?中的所以模p的二次剩余组成，S2则由其中的所以模p的二次非剩余组成，且各有?p?1?2个数。
17． 利用雅可比符号性质计算：
?51???35?（1）??； （2）??；
?71??97??165??313?（3）?? ?； （4）??503??401?18． 设p为奇素数，证明：方程x2≡－4（mod p）有
解的充分必要条件是p≡1（mod 4）。
19． 设p为素数且p≡3（mod 4），证明2p＋1是素数的充分必要条件是2p?1?mod2p?1?。
20． 设素数p≥3且pa。证明：??21． 设素数p≥3且p－1。
22． 设x mod m表示x遍历模数m的完全剩余系，证明：
（1）若?a,m?=?b,m?＝1，则
p?ax?b??＝0。 p?x?1?p?x2?ax?p?x2?x?a。证明：??????＝?ppx?1??x?1??47/49
《数论算法》 第四章 二次同余方程与平方剩余
?ax2?bx?m?1?ax?b??a????????????； mm??m?x?1??x?1?m?1（2）?a,m?＝1时，
?ax?b???＝0 m?xmodm??（3）设f?x?为整系数多项式，则当?a,m?＝1时，有； ?f?ax?b???f?x???????； ??xmodm?m?xmodm?m?23． 设p为奇素数，证明以下等式： （1）若p≡1（mod 4），则?r?r?＝0；
r?1p?1???p?2p?1?r??r?r?pr???； （2）若p≡3（mod 4），则???r?1r?1?p??p?p?1（3）若
p?1?r?3p?12?r?，则?r???p?r??； p≡1（mod 4）
r?1?p?2r?1?p?3p?1（4）若
4p≡3（mod 4），则
p?1p?1?r?3?r?22?r?r?2pr?pr?????????； ppr?1r?1r?1?????p?24． 设a，b为正整数，b为奇数。证明对Jacobi符号有公式
??a???b?,a?0,1?mod4??a???? ?????2a?b???a????,a?2,3?mod4????b?25． 设a，b，c为正整数，b为奇数，?a,b?＝1且b?4ac。
证明对Jacobi符号有公式
?a??a?????? ?4ac?b??b?26． 证明：
（1）若p为奇素数，q为2p?1的素因数，则q??1?mod8?。
（2）不用计算，证明：23211?1，47223?1，5032251?1。
27． 证明：对于任给的n＞1，存在m＞0，使同余方程
48/49
《数论算法》 第四章 二次同余方程与平方剩余
x2?1?modm?的解数大于n。
???pk28． 设m?2?p1?p2，pi是不同的奇素数，?i≥1
012k（1?i?k），?0≥0，求同余方程x2?1?modm?的解数。 29． 设k是模数m的不同素因数的个数，求同余方程
x2?x?modm?的解数。
x2?a?modm?的解数。其中pi是不同的奇素数。
30． 设m?p1p2?pk，a为任意整数，求同余方程
31． 设正整数m＞1，a为任意整数，求同余方程x2?a?modm?的解数。
32． 把
同
余
方
程
x2?1?modm?0写为
?k?1?2时，利p1p2?pk用把同余方程化为同余方程组的方法，给出一种求x2?1?modm?的全部解的具体方法。并用以求解m?23?32?52和m?2?32?5?7的情形。其中pi是不同的奇素数，?i≥（1?i?k），?0≥0。
?x?1??x?1??0?modm?。当m?2?
49/49