《数论算法》教案 4章(二次同余方程与平方剩余).doc

《数论算法》 第四章 二次同余方程与平方剩余
第 4 章 二次同余方程与平方剩余
内容
1. 二次同余方程，平方剩余
2. 模为奇素数的平方剩余
3. 勒让德符号、雅可比符号
4. 二次同余方程的求解
要点
二次同余方程有解的判断与求解
4.1 一般二次同余方程
(一) 二次同余方程
＋bx＋c≡0（mod m），（a0（mod m）） （1）
(二) 化简
设m＝，则方程（1）等价于同余方程

问题归结为讨论同余方程
＋bx＋c≡0（mod ）， （pa） （2）
(三) 化为标准形式
p≠2，方程（2）两边同乘以4a，
4＋4abx＋4ac≡0（mod ）
≡－4ac（mod ）
变量代换，
y＝2ax＋b （3）
有
≡－4ac（mod ） （4）
当p为奇素数时，方程（4）与（2）等价。即
l 两者同时有解或无解；有解时，对（4）的每个解，通过式（3）（x的一次同余方程，且（p, 2a）＝1，所以解数为1）给出（2）的一个解，由（4）的不同的解给出（2）的不同的解；反之亦然。
l 两者解数相同。
结论：只须讨论以下同余方程
≡a（mod ） （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≡(y－5)≡ (y－5)
≡2(y－5)≡2y－10≡2y－1
≡－7, －1, 5≡－4, －1, 2（mod 9））
(四) 二次剩余
【定义4.1.1】设m是正整数，a是整数，ma。若同余方程
≡a（mod m） （6）
有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的平方非剩余（或二次非剩余）。
问题：
（1） 设正整数a是模p的平方剩余，若记方程（6）中的解为x≡（mod m），那么此处的平方根（mod m）与通常的代数方程＝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：≡＋x＋1（mod 7）的所有点。
（解）对 x＝0，1，2，3，4，5，6分别解出y：
＝0，≡1（mod 7），y≡1，6（mod 7）
＝1，≡3（mod 7），无解
＝2，≡4（mod 7），y≡2，5（mod 7）
＝3，≡3（mod 7），无解
＝4，≡6（mod 7），无解
＝5，≡5（mod 7），无解
＝6，≡6（mod 7），无解
所以，满足方程的点为（0, 1），（0, 6），（2, 2），（2, 5）。
说明：方程E：≡＋x＋1的图形称为椭圆曲线。

4.2 模为奇素数的平方剩余与平方非剩余
模为素数的二次方程
≡a（mod p）, (a, p)＝1 （1）
因为＝，故方程（1）要么无解，要么有两个解。
(一) 平方剩余的判断条件
【定理4.2.1】（欧拉判别条件）设p是奇素数，(a, p)＝1，则
（i）a是模p的平方剩余的充要条件是
≡1（mod p） （2）
（ii）a是模p的平方非剩余的充要条件是
≡－1（mod p） （3）
并且当a是模p的平方剩余时，同余方程（1）恰有两个解。
（证）先证pa时，式（2）或（3）有且仅有一个成立。
由费马定理 ≡1（mod p）
－1≡0（mod p）
≡0（mod p） （4）
即 ＝
但 ＝1或2
且素数p>2。所以，p能整除，但p不能同时整除和（否则，p能整除它们的最大公因子1或2）
所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。
（i）必要性。若a是模p的二次剩余，则必有使得
≡a（mod p），
因而有 ≡（mod p）。
即 （mod p）。
由于pa，所以p，因此由欧拉定理知
≡1（mod p）。
即（2）式成立。
充分性。已知 ≡1（mod p），这时必有pa。故一次同余方程
≡a（mod p）, (1≤b≤p－1) （5）
有唯一解，对既约剩余系
－(p－1)/2，…，－1，1，…，(p－1)/2 （6）
由式（6）给出的模p的既约剩余系中的每个j，当b＝j时，必有唯一的属于既约剩余系（6），使得式（5）成立。若a不是模p的二次剩余，则必有。这样，既约剩余系（6）中的p－1个数就可按j、xj作为一对，两两分完。
（b1≠b2，则相应的解x1≠x2，且除了±1之外，每个数的逆不是它本身）
因此有

由威尔逊定理知

与式（2）矛盾。所以必有某一，使，由此及式（5）知，a是模p的二次剩余。
（ii）由已经证明的这两部分结论，立即推出第（ii）条成立。
其次，若0（mod p）是方程（1）的解，则－也是其解，且必有－（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，都有≡1（mod 19）。方程≡1（mod 19）只有两个解，即x≡±1（mod 19）。从而必有
≡±1（mod 19）
（视≡1（mod 19），即）
针对必要性：例如a＝17是模19的二次剩余，即存在≡6使得≡17（mod 19）。那么必有
≡≡≡1（mod 19）
针对充分性：例如a＝6，≡≡1（mod 19），验证6是二次剩余。解方程
≡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，≡≡－1（mod 19），验证：解方程
≡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)
≡≡－1（mod 19）

【例2】判断137是否为模227的平方剩余。
（解）首先，227是素数。其次，计算
≡－1（mod 227）
所以，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的既约剩余系中平方剩余与平方非剩余的个数各为(p－1)／2，且(p－1)／2个平方剩余恰与序列
12，22，…，
中的一个数同余。
（证）由定理4.2.1，模p的平方剩余个数等于方程
≡1（mod p）
的解数。但

由定理3.4.5知，方程的解数为，即平方剩余的个数是，且平方非剩余的个数是(p－1)－＝。
其次，可以证明当1≤k1≤，1≤k2≤，且k1≠k2时，有 mod p。故结论成立。
（定理3.4.5：设p为素数，n为正整数，n≤p。则同余方程＝≡0 mod p有n个解被除所得余式的所有系数都是p的倍数）
4.3 勒让德符号
目的：快速判断整数a是否为素数p的平方剩余。
(一) 勒让德符号
【定义4.3.1】设p是素数，定义勒让德（Legendre）符号为：
L(a, p)＝＝
【推论】整数a是素数p的平方剩余的充要条件是＝1。
（证）由定义4.3.1。
因此，判断平方剩余转化为计算勒让德符号的值。

【例1】直接计算，得
＝1
＝－1
（注：本例仍是利用平方剩余而得到勒让德符号值）
问题：反过来，如何快速计算勒让德符号的值，以判断平方剩余。
(二) （勒让德符号的）性质
【性质1】（欧拉判别法则）设p是奇素数，则对任意整数a，有
＝（mod p）
（证）由定理4.2.1即知。

【性质2】＝1
（证）显然（因为方程x2≡1（mod p）始终有解x≡±1（mod p），或者由性质1立得）。

【性质3】＝。
（证）由性质1即得。

【例2】＝1，＝－1

【推论】＝
（证）p≡1（mod 4） p＝4k＋1
＝＝＝1
p≡3（mod 4） p＝4k＋3
＝＝＝－1
另一种描述：设素数p>2，则－1是模p的二次剩余的充分必要条件是p≡1（mod 4）。

【性质4】＝
（证）因x2≡a＋p（mod p） x2≡a（mod p）

【推论】若a≡b（mod p），则＝

【性质5】＝
（证）因＝＝＝
【推论1】＝
【推论2】当pa时，＝1

讨论：确定a是否是模p的平方剩余就变为如何计算Legendre符号的值。上述性质可以用来计算，并由算术基本定理，设a 的分解式为
＝±＝， （t＝0, 1）
则
＝
（t＝0, 1）故只要能计算出
，，
就可以计算出任意的，其中是小于p的素数。
已经解决的计算：
剩余的问题：，的计算。
解决这些问题的基础是下面的二次互反律（Gauss定理）。

【性质6】＝
【例3】＝＝＝1，
＝＝＝－1，故2是模17的平方剩余，但不是模19的平方剩余。

【推论】p为奇素数，则
＝
（证）因为
当p＝8k＋1时
＝＝＝k(8k＋2)＝偶数
当p＝8k＋3时
＝＝(2k＋1)(4k＋1)＝奇数
【例4】由于31≡7≡－1（mod 8），59≡3（mod 8），故＝1，＝－1，即2是模31的平方剩余，但不是模59的平方剩余。

【性质7】（二次互反律，高斯定理）p≠q且均为奇素数，则
＝
另一表示形式：＝
说明1：符号和分别刻画了二次同余方程
≡q（mod p）
和
≡p（mod q）
是否有解，即q是否是模p的二次剩余和p是否是模q的二次剩余，其中正好是模与剩余互换了位置，而性质7恰好刻画了两者之间的关系，故称为二次互反律。
说明2：由欧拉提出，高斯首先证明。已有一百五十多个不同的证明。由二次互反律引伸出来的工作，导致了代数数论的发展和类域论的形成。

【推论】（i）设奇素数p、q中至少有一个模4为1，则
方程≡q（mod p）有解方程≡p（mod q）有解
（ii） 若p≡q≡3（mod 4），则
方程≡q（mod p）有解方程≡p（mod q）无解
（证）（i）设p≡1（mod 4），即p＝4k＋1，则
＝＝＝
（ii）此时，p＝4s＋3，q＝4t＋3，则
＝＝＝－

【例5】判断3是否是模17的平方剩余。
（解）＝＝＝－1
所以，3是模17的平方非剩余。（不但如此，17也是3的平方非剩余，即2是3的平方非剩余）

【例6】判断同余方程≡137（mod 227）是否有解。
（解）已知137与227均为奇素数，所以
＝＝
＝＝＝
＝＝＝－1
所以，方程无解。
另法：＝＝
＝－＝
＝＝－1
【例7】判断同余方程≡－1（mod 365）是否有解，若有解，求解数。
（解）由于365＝5·73，所以
≡－1（mod 365）
＝＝1
所以方程有解，且解数为4。

【例8】判断同余方程≡2（mod 3599）是否有解，若有解，求解数。
（解）由于3599＝59·61，所以
≡2（mod 3599）
因为59≡3（mod 8），即＝－1，故方程≡2（mod 59）无解，从而原方程无解。

【例9】证明形如4k＋1的素数有无穷多。
（证）反证法：不然，形如4k＋1的素数为有限个，设为，，…，，令
＝＝4b＋1
即a 也形如4k＋1且a＞（i＝1,2,…, k）。所以a 为合数，设其素因数p 为奇数，则
＝＝＝1
所以－1为模p平方剩余。由性质3的推论，p≡1（mod 4），即p也是形如4k＋1的素数。（【推论】＝）
但显然p≠（i＝1, 2,…, k），矛盾（否则，，且由p│a知p│1）。

4.4 二次互反律的证明
(一) 证明
(二) 应用
【例1】求所有奇素数p，它以3为其平方剩余。
（解）即求所有奇素数p，使得＝1。
易知p＞3。由二次互反律
＝
因为
＝
以及
＝（排除偶数）
知
＝1 或
即
p≡1（mod 12）或p≡－1（mod 12）
故3是模p二次剩余 p≡±1（mod 12）

【例2】设p为奇素数，d是整数。若＝－1，则p一定不能表示为的形式。
（证）用反证法。设p有表达式，则由p是素数可知(x, p)＝(y, p)＝1。这是因为若(x, p)≠1，则必有

但由＝－1知(d, p)＝1，所以p│y2，进而p│y。那么
p2│x2，p2│y2 p2│x2－dy2＝p
矛盾。（即(x, p)＝(y, p)＝1成立）
由(x, p)＝(y, p)＝1知，＝±1，＝±1，从而
＝＝＝＝＝1
与题设矛盾。
【性质8】同余方程的解数是。

【问题】求所有奇素数p，它以5或－2为其平方剩余。

4.5 雅可比符号
（1） 问题：在计算勒让德符号时，若a为奇数，但非素数，如何快速计算。
（2） 目的：为了快速计算勒让德符号。
(一) 雅可比符号
【定义4.5.1】设m＝…是奇素数的连乘积（可以重复），对任意整数a，定义雅可比（Jacobi）符号为：
J(a, m)＝＝
说明：
（1） 上式右端的为勒让德符号，即
J(a, m)＝＝＝
（2） 雅可比符号形式上是勒让德符号符号的推广。但与勒让德符号意义不同。
（3） 两者的本质区别：勒让德符号可用来判断平方剩余，但雅可比符号却不能。即当k＞1时，如果J(a, m)＝－1，则方程≡a（mod m）无解（因为至少存在一个，使得＝－1，即方程≡a（mod ）无解，从而原方程≡a（mod m）也无解），但当J(a, m)＝1时，方程≡a（mod m）则不一定有解。
（4） 当k＝1时，J(a, m)＝ L(a, m)，即此时勒让德符号的值与雅可比符号的值相等。
（5） 因此，求勒让德符号的值转化为计算雅可比符号。

【例1】由定义4.5.1
＝＝(－1)(－1)＝1
但可以验证2是模9的平方非剩余。
又如当奇素数p≡3（mod 4）时，由勒让德符号的性质知，－1是模P的非平方剩余，即方程≡－1（mod p）无解，从而方程≡－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】a＝15，m＝39，则
J(a, m)＝＝＝
＝＝0＝0

【性质2】＝1
（证）J(1, m)＝＝＝1

【性质3】＝
（证）因为
＝＝
＝1＋＋＋…
故 m≡1＋（mod 4），即
m－1≡（mod 4）
≡（mod 2）
所以
J(－1, m)＝ ＝
＝＝
【推论】＝
（证）m≡1 mod 4 m＝4k＋1
＝＝＝1
≡3 mod 4 m＝4k＋3
＝＝＝－1
【例3】＝1，＝－1

【性质4】＝
（证）首先，由m＝…和m＋a≡a（mod m）知
m＋a≡a（mod ）
其次，由雅可比符号和勒让德符号性质知
＝
＝＝

【推论】若a≡b（mod m），则＝
（证）显然

【性质5】＝
（证）因＝
＝··…·
＝…·…
＝

【推论1】＝
【推论2】当(m, a)＝1时，＝1

【性质6】＝
（证）因为
＝＝
＝1＋＋＋…＋
∴ －1≡（mod 64）
而对任何奇数q，都有≡1（mod 8）（i＝1,2,…, k），故
≡（mod 8）
≡（mod 2）
所以 J(2, m)＝ ＝…
＝＝
【推论】m为奇数，则
＝
（证）因为
当m＝8k＋1时
＝＝＝k(8k＋2)＝偶数
当m＝8k＋3时
＝＝(2k＋1)(4k＋1)＝奇数

【例4】＝＝1，＝＝－1。

【性质7】（二次互反律，高斯定理）设m、n都是奇数，则
＝
或 ＝

【性质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（mod 563）是否有解。
（解）563为素数，计算勒让德符号
＝＝
＝＝＝＝－1
所以，原方程无解。

【例7】判断同余方程≡88（mod 105）是否有解。
（解）105＝3·5·7为合数，直接计算雅可比符号
＝＝
＝－＝＝＝－1
所以，原方程无解。（因为原方程等价于方程组，而方程组有解的充分必要条件是勒让德符号＝＝＝1。但＝＝－1，说明、、三者中至少有一个为－1，即方程组中至少有一个方程无解，从而原方程无解）。
再次说明雅可比符号可以用来否定方程有解，但不能肯定方程有解。
【例8】求同余方程≡38（mod 385）的解数。
（解）385＝7·5·11为合数，直接计算雅可比符号
＝＝
＝＝＝－＝1
＝1并不能肯定原方程是否有解。所以，还须判断方程组中的每个方程是否有解。故再计算勒让德符号＝＝－1，因此方程≡38（mod 5）无解，最终说明原方程解数为零。

4.6 模p平方根
（1） 目的：解同余方程
≡a（mod p），p为素数且pa （1）
（2） 方法：逐步迭代
设p－1＝s。
(一) 理论基础
理论基础：a是模p的平方剩余的充要条件（欧拉定理）
Z＝≡1（mod p）
若t>1则（＝偶数）
≡≡±1（mod p）
若≡1（mod p）且t＞2，继续开方；否则，构造N，使
≡1（mod p）
又可以继续开方。其中N为模p的平方非剩余（即）。
目标：构造，使得：≡a（mod p）
从而得方程（1）的解：x≡±（mod p）
(二) 算法
将偶数p－1表为p－1＝s，t≥1，s为奇数。
（1）选模p的平方非剩余N，即＝－1，令b≡（mod p），则有
＝＝＝≡1（mod p）
＝＝≡－1（mod p）
即b是模p的次单位根，但非模p的次单位根。
（2）计算： ≡（mod p）
则y＝满足方程： ≡1（mod p）
（因＝＝＝≡1（mod p））
即y＝是模p的次单位根。
（3）若t＝1，则x＝＝≡（mod p）满足方程
≡a（mod p）
（此时p－1＝2s，＝＝≡a（mod p）。即方程已经解出）
否则，t≥2，寻找，使得y＝满足方程
≡1（mod p）
即y＝是模p的次单位根。
（a）若
≡1（mod p）
令＝0，＝≡（mod p），则即为所求。
（b）若
≡－1（mod p）
令＝1，＝＝b（mod p），则即为所求。
（因＝＝＝≡(－1)(－1)≡1（mod p））

（4）若t＝2，则x＝＝＝≡（mod p）满足方程
≡a（mod p）
（此时p－1＝s，≡≡≡a（mod p））
否则，t≥3，寻找，使得y＝满足方程
≡1（mod p）
即y＝是模p的次单位根。
（a）若
≡1（mod p）
令＝0， ＝≡（mod p），则即为所求。
（b）若
≡－1（mod p）
令＝1，＝≡（mod p），则即为所求。
……
依次类推
（k＋1）设找到整数满足
≡1（mod p）
即y＝是模p的次单位根：
≡1（mod p）
（k＋2）若t＝k，则x≡≡（mod p）满足方程
≡a（mod p）
否则，t≥k＋1，寻找整数，使得y＝满足方程
≡1（mod p）
即y＝是模p的次单位根。
（a）若
≡1（mod p）
令＝0，≡＝（mod p），则即为所求。
（b）若
≡－1（mod p）
令＝1，≡＝（mod p），则即为所求。
最后，k＝t－1：
＝
≡
≡
…………
≡
≡（mod p）
满足方程：≡a（mod p），p为素数且pa

(三) 例
【例1】用上述方法解同余方程≡186（mod 401）
（解）a＝186，p＝401。
判断：p＝401为素数，且（用雅可比符号计算）
＝＝1·1＝1
或（用勒让德符号计算）
＝＝1·(－1) ·(－1)＝1
故原方程有解。
准备：p－1＝401－1＝400＝·25，其中t＝4，s＝25。
（1）由上边计算，＝－1，即N＝3是模401的平方非剩余。令b≡≡≡268（mod 401）。
（2）计算
≡≡≡103（mod 401）
≡≡≡235（mod 401）
（3）因为
≡≡≡－1（mod 401）
故令＝1，≡≡103·268≡336（mod 401）。
（此时，，）
（4）因为
≡≡1（mod 401）
故令＝0，≡336（mod 401）。
（此时，）
（5）因为
≡235·≡－1（mod 401）
故令＝1，≡≡336·≡304（mod 401）。
（此时，）
则
≡≡304（mod 401）
满足原方程。
（验证，＝92416＝186（mod 401））

【例2】设p是形为4k＋3的素数，若方程
≡a（mod p）
有非零解，则其解为
x≡±（mod p）
（解）因为p＝4k＋3，故q＝为奇数，而方程
≡a（mod p）
有解，则a是模p的二次剩余，从而有
≡1（mod p）
即 ≡1（mod p）
已知原方程有非零解，即（a, p）＝1，故有
≡a（mod p）
即
≡≡a（mod p）
∴ x≡±≡±≡±（mod p）

【例3】设p≠q均为形如4k＋3的素数，且＝＝1，求解同余方程：
≡a（mod pq）
（解）首先
≡a（mod pq）
而两个方程的解分别为
（mod p）和（mod q）
利用中国剩余定理解联立方程

得原方程的解为
（（mod p））uq±（（mod q））vp （mod pq）
其中，
≡1（mod p）， vp≡1（mod q）

【例3】解同余方程≡3（mod 253）。
（解）253＝11·23，11≠23，二者均为形如4k＋3的素数，且＝＝1，
解方程 ≡3（mod 11），得
≡±≡±5（mod 11）
解方程≡3（mod 23），得
≡±≡±7（mod 23）
利用中国剩余定理解联立方程

M＝11·23＝253，，＝11，计算
＝1（mod 11），＝21（mod 23）
∴ ≡±5·23·1±7·11·21（mod 253）
≡±115±99
≡±16，±39，（mod 253）
4.7 合数的情形
方程
≡a（mod m），（a, m）＝1 （1）
＝
≡a（mod ），（a, p）＝1 ，＞1 （3）
(一) P为奇素数
【定理4.7.1】设p是奇素数，则（3）有解＝1。且有解时，（3）的解数为2。
（证）必要性
≡a（mod ）有解≡a（mod p）有解＝1
充分性：设＝1，则存在整数x≡（mod p）使得
≡a（mod p）
令f(x)＝－a，则＝2x，＝（2，p）＝1，故方程（3）的解数为2。

【推论】同余方程（3）的解数为
T＝1＋
(二) P＝2
≡a（mod ），（a, 2）＝1 ，＞1 （4）
（当α＝1时，方程≡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；当≥3时，解数是4。
（证）必要性：若（4）有解，则存在整数z，使得
≡a（mod ）
由（a, 2）＝1知（z, 2）＝1，记z＝1＋2t，则上式可表为
a≡1＋4t(t＋1) （mod ） （5）
（注：＝＝1＋4t＋4）
所以当＝2时，a≡1（mod 4）。
而当≥3时，由（5）知
a≡1＋4t(t＋1) （mod ＝8）
又由2│t(t＋1)知，a≡1（mod 8）。
充分性：
（i）当＝2时，a≡1（mod 4），方程
≡a≡1（mod ）
显然有两个解 x≡1，3（mod ）
（ii）当≥3时，a≡1（mod 8）。此时，
若＝3，易验证方程
≡a≡1（mod ） （6）
的解为 x≡±1，±5（mod ），即
＝±(1＋)，＝0, ±1, ±2…
或 ＝±(＋)，＝0, ±1, ±2… （7）
其中，x3＝1, 5。

若＝4，方程为
≡a（mod ） （8）
令 ≡a（mod ）
（由第三章结论，希望从方程（6）的解的值（7）中去找方程（8）的解，即确定）
即 ＋2()＋≡a（mod ）
亦即 ＋≡a（mod ）
≡a－（mod ）
所以 ≡（mod 2）
≡（mod 2）
（注意≡1（mod 2））或
＝＋2，＝0, ±1, ±2…
代入（7），方程（8）的解可表为
（＝±(＋)，＝0, ±1, ±2… （7））
＝±(＋)，＝＋2，＝0, ±1, ±2…
＝±(＋＋)，＝0, ±1, ±2…
或 ＝±(＋)，＝0, ±1, ±2…
其中＝＋，且≡1（mod 2）。
（因为a≡≡1（mod 8），故＝整数，从而为偶数）
……………………

依次类推，对于α≥4，设同余方程
≡a（mod ） （9）
的解为
＝±(＋)，＝0, ±1, ±2… （10）
或
≡±(＋)（mod ），＝0, 1
且≡1（mod 2）。
为了从方程（9）的上述解的值（10）中找出方程
≡a（mod ） （11）
的解，令
≡a（mod ）
即
＋2()＋≡a（mod ）
亦即
＋≡a（mod ）
≡a－（mod ） （12）
所以
≡（mod 2）
≡（mod 2）
或
＝＋2，＝0, ±1, ±2…
代入（10）式，方程（11）的解可表为
（＝±(＋)，＝0, ±1, ±2… （10））
＝±(＋)，＝＋2，
＝0, ±1, ±2…
即 ＝±(＋＋)，
＝0, ±1, ±2…
或
＝±(＋)，＝0, ±1, ±2…
其中＝＋，且≡1（mod 2）。
（因为由式（12）可知＝整数，从而为偶数）

【例1】解方程≡57（mod 64）。
（解）64＝，即＝6。因57≡1（mod 8），故方程有4个解。
＝3时，解的值为
x＝±(1＋)，＝0, ±1, ±2… （13）
（解的表示：x≡1，3，5，7（mod 8），
或 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
此时方程为≡57≡1（mod 8））
（＝1）

＝4时，在式（13）的所有值中找方程
≡57（mod ） （14）
的解。
为此，令 ≡57（mod ）则
＋2·1· (4)＋≡57（mod ）
即
＋·1·≡57（mod ）
·1·≡57－（mod ）
1·≡≡1（mod 2）
≡≡1（mod 2）
或
＝＋2＝1＋2，＝0, ±1, ±2…
代入（13）式得方程（14）的解为
（x＝±(1＋)，＝0, ±1, ±2… （13））
x＝±(1＋·1＋)＝±(5＋)，＝0, ±1, ±2…
或 x≡±(5＋)（mod ），＝0, 1
或 x≡±5，±13≡±3，±5（mod ）
（＝5）

＝5时，令 ≡57（mod ），则
＋2·5· ()＋≡57（mod ）
·5·≡57－（mod ）
5·≡≡0（mod 2）
≡≡0（mod 2）
或 ＝0＋2＝2，＝0, ±1, ±2…
故方程 ≡57（mod ）的解为
x＝±(5＋·0＋)＝±(5＋)，＝0, ±1, ±2…
或 x≡±(5＋)（mod ），＝0, 1
或 x≡±5，±21≡±5，±11（mod ）
（＝5）

＝6时，令 ≡57（mod ），则
＋2·5· ()＋≡57（mod ）
·5·≡57－（mod ）
5·≡≡1（mod 2）
≡≡1（mod 2）
或
＝1＋2，＝0, ±1, ±2…
故方程 ≡57（mod ）的解为
＝±(5＋·1＋)＝±(21＋)，＝0, ±1, ±2…
或
(21＋)（mod ），＝0, 1
或
≡±21，±53≡±11，±21（mod ）
（＝21）
4.8 解同余方程总结
(一) 方法
（1） 一般方程方程 f(x) ≡0（mod m）化为等价方程组

其中＝
（2） 解素数幂方程
f(x)≡0（mod ）， 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：（mod 7）；
（2）E：（mod 7）；
（3）E：（mod 17）；
（4）E：（mod 17）。
2． 利用欧拉判别条件判断：
（1）－8是否是模53的二次剩余；
（2）8是否是模67的二次剩余。
3． 求下列同余方程的解数：
（1）≡2（mod 67）；
（2）≡－2（mod 67）；
（3）≡2（mod 37）；
（4）≡－2（mod 37）；
（5）≡1（mod 221）；
（6）≡－1（mod 427）；
4． 计算下列勒让德符号：
（1）； （2）； （3）；
（4）； （5）； （6）；
（7）； （8）； （9）；
（10）； （11）； （12）。
5． 判断下列同余方程是否有解，若有解，请求其解数：
（1）≡7（mod 227）； （2）≡249（mod 257）
（3）≡79（mod 433）； （4）≡365（mod 389）
（5）≡11（mod 511）；
（6）≡2495（mod 5249）；
（7）11≡－6（mod 91）；
（8）5≡－14（mod 6193）。
6． 解下列同余方程：
（1）－6≡0（mod 56）；
（2）＋4≡0（mod 32）
7． 按要求完成下列问题：
（1） 求以－3为其二次剩余的全体素数；
（2） 求以±3为其二次剩余的全体素数；
（3） 求以±3为其二次非剩余的全体素数；
（4） 求以3为二次剩余、以－3为二次非剩余的全体素数；
（5） 求以－3为二次剩余、以3为二次非剩余的全体素数；
8． 求以3为二次非剩余、以2为二次剩余的全体素数（即以3为正的最小二次非剩余的全体素数）。
9． 完成以下问题：
（1） 求满足＝1的全体素数；
（2） 求满足＝1的全体素数；
（3） 求，，的素因数分解式；
（4） 判断方程≡25（mod 1013）是否有解。
10． 设素数＝4m＋1，d│m。证明： ＝1。
11． 设是奇素数，pa。证明：存在整数u和v，使得≡0（mod ）的充分必要条件是－a是模的二次剩余。其中＝1。
12． 设是奇素数，证明：
（1） 模的所有二次剩余的乘积对模的剩余是；
（2） 模的所有二次非剩余的乘积对模的剩余是；
（3） 模的所有二次剩余之和对模的剩余是1（当＝3时）或0（当＞3时）；
（4） 所有模的二次非剩余之和是多少？
13． 证明下列形式的素数均有无穷多个：
（1）8k－1，8k＋3，8k－3；
（2）3k＋1，6k＋1，12k＋1，12k＋7；
（3）十进制表示末尾为9的数。
14． 设的素因数为，证明：≡1（mod 12）。
15． 设是奇素数，且≡1（mod 4）。证明：
（1） 1, 2, …, (－1)/2中模的二次剩余与非剩