第5章二次同余方程



5.1二次同余方程的概念及二次剩余由第4章知，解一般模数的二次同余方程可归结为解素数模的二次同余方程: ax2+bx+c≡0 mod p(5.1.1)其中p a。
由p a得(p,a)=1，(p,4a)=1，将式(5.1.1)两边同乘以4a，得4a2x2+4abx+4ac≡0 mod p
(2ax+b)2≡b2－4ac mod p做可逆变换y=2ax+b(因为(p,2a)=1)，得到式(5.1.1)的等价同余方程: y2≡b2－4ac mod p所以，只需讨论形如x2≡d mod p的同余方程。当p|d时，方程只有一个解0 mod p，所以下面恒假设p d。
定义5.1.1设素数p>2,a∈Z,p a。如果同余方程x2≡a mod p(5.1.2)有解，则称a是模p的二次剩余，否则称为模p的二次非剩余。满足式(5.1.2)的x称为a的平方根。
例5.1.1由x2≡1 mod 3得x≡±1 mod 3，所以1是模3的二次剩余。
x2≡－1 mod 3无解，－1是模3的二次非剩余。
x2≡1 mod 5得x≡±1 mod 5，1是模5的二次剩余。
x2≡－1 mod 5得x≡±2 mod 5，－1是模5的二次剩余。
x2≡2 mod 5无解，2是模5的二次非剩余。
x2≡－2 mod 5无解，－2是模5的二次非剩余。
已知p，模p的二次剩余和二次非剩余元素的个数由以下定理给出。
定理5.1.1在模p的一个简化剩余系中，恰有p－12个二次剩余和p－12个二次非剩余。若a是二次剩余，则方程(5.1.2)有两个解。
证明取模p的绝对最小简化剩余系－p－12,－p－12+1,…,－1,1,…,p－12－1,p－12a是模p的二次剩余，当且仅当a与以下p-1个值中的一个模p同余: －p－122,－p－12+12,…,(－1)2,12,…,p－12－12,p－122但由于(－j)2≡j2 mod p，所以a是模p的二次剩余，当且仅当a与以下p－12个值中的一个模p同余: 12,…,p－12－12,p－122(5.1.3)网络空间安全数学基础第5章二次同余方程这p－12个值中任意两个都不同余。否则设i2≡j2 mod p，则得(i+j)i－j≡0 mod p，所以p|i+j或p|i－j。但1≤i,j≤p－12，2≤i+j≤p－1，|i－j|≤p－1，所以i=j，矛盾。所以式(5.1.3)给出了模p的全部二次剩余，其余的p－1－p－12=p－12个元素是二次非剩余。所以若a是二次剩余，a必为式(5.1.3)中的一项，而且仅为其中一项。
若x≡i mod p是式(5.1.2)的解，则x≡－i mod p也是式(5.1.2)的解，即式(5.1.2)有两个解。 证毕。
由以上证明过程可得如下推论。
推论设a是模p的二次剩余，则a与12,22,…,p－122中的一个且仅与一个模p同余。
例5.1.2求模19的二次剩余。
解由定理5.1.1的推论，求模19的二次剩余就是在模19的绝对最小简化剩余系－9,－8,…,－1,1,2,…,9中求a，它与12,22,…,92中的某一个模19同余，如表5.1.1所示。表5.1.1模19的二次剩余j123456 789a≡j2 mod 19149-36-2－875所以模19的二次剩余是1,－2,－3,4,5,6,7,－8,9，二次非剩余是－1,2,3,－4,－5,－6,－7,8,－9。
反过来看表5.1.1，可得每个二次剩余的两个解。例如，6是二次剩余，它的两个解是±5 mod 19。
定理5.1.2可直接判断a是不是模p的二次剩余，可无须在模p的绝对最小简化剩余系中逐一验证。
定理5.1.2设素数p>2，p a，则a是模p的二次剩余的充要条件是ap－12≡1 mod pa是模p的二次非剩余的充要条件是ap－12≡－1 mod p证明由于xp－1－1=x2p－12－ap－12+ap－12－1=x2－aq(x)+ap－12－1由定理4.4.5得x2－a≡0 mod p有两个解(即a是模p的二次剩余)的充要条件是x2－a|xp－x=xxp－1－1因x2－a≡0 mod p没有0解，即x2－a没有x因子，所以x2－a|xp－1－1等价于ap－12－1≡0 mod p即
ap－12≡1 mod p
又由于ap－12+1ap－12－1≡ap－1－1 mod p≡0 mod p其中第二个同余式由Euler定理得，所以p|ap－12+1或p|ap－12－1但这两个同余式不能同时成立，否则ap－12≡－1 mod p且ap－12≡1 mod p得－1≡1 mod p，2≡0 mod p，矛盾。
所以，a是模p的二次非剩余的充要条件是ap－12≡－1 mod p。 证毕。
从上述证明过程还可见，如果a是模p的二次剩余，则ap－12－1≡0 mod p，x2－a|xp－x因此x2－a≡0 mod p有两个解，这也是定理5.1.1的结论。
推论1－1是模p的二次剩余的充要条件是p≡1 mod 4。
证明取模4的最小非负完全剩余系0,1,2,3，当且仅当p在最小非负完全剩余系中取1，即p≡1 mod 4时，满足方程(－1)p－12≡1 mod p 证毕。
推论2设素数p>2，p a1,p a2，则
(1) 若a1、a2均为模p的二次剩余，则a1a2也是模p的二次剩余。
(2) 若a1、a2均为模p的二次非剩余，则a1a2是模p的二次剩余。
(3) 若a1是模p的二次剩余，a2是模p的二次非剩余，则a1a2是模p的二次非剩余。
证明因为(a1a2)p－12=ap－121ap－122，由定理5.1.2即得。 证毕。
例5.1.3判断3是否为模17的二次剩余，7是否为模29的二次剩余。
解因为32≡9 mod 17≡－8 mod 17,34≡－4 mod 17,38≡16 mod 17≡－1 mod 17所以3是模17的二次非剩余。
因为72≡－9 mod 29，73≡－5 mod 29，74≡－6 mod 29，
77=73·74≡1 mod 29，714≡1 mod 29所以7是模29的二次剩余。
5.2Legendre符号要判断a是否为模p的二次剩余，由定理5.1.1要逐一检验a是否与以下各值中的某一个模p同余:12,22,…,p－122或者由定理5.1.2计算ap－12 mod p的值。当p很大时，两个方法都不实用。本节介绍一种简单方法，即求a模p的Legendre符号。
定义5.2.1设素数p>2，定义Legendre符号如下: ap=1,a是模p的二次剩余
－1,a是模p的二次非剩余
0,p|a所以，要判断a是否为模p的二次剩余，只需计算ap即可。
定理5.2.1Legendre符号有以下性质。
(1) ap=p+ap，一般地ap=a+kpp，其中k∈Z。
(2) ap≡ap－12 mod p。
(3) abp=apbp，即Legendre符号是完全积性的。
(4) 当p a时，a2p=1。
(5) 1p=1,－1p=(－1)p－12。
证明极简单，略。
由定理5.2.1可见，当a增加时，ap以p为周期，若a>p，则总能求出q<p，(p,q)=1，使得ap=qp。
下面考虑如何求2p及一般形式的qp，为此需要引入Gauss引理。
引理5.2.1(Gauss引理)设素数p>2,p a，如果a·1,a·2,…,a·p－12(mod p)(5.2.1)中大于p2的元素个数为n，则ap=(－1)n证明在式(5.2.1)的p－12个数中，当ij时，aiaj mod p，否则由(a,p)=1得i≡j mod p。
将式(5.2.1)中大于p2的数记为r1,r2,…,rn，小于p2的数记为s1,s2,…,st。显然1≤p－ri<p2(1≤i≤n)且p－risj mod p(1≤j≤t)这是因为－p2<－sj<0
－p2+1<p－ri－sj<p2
p－ri－sj0 mod p所以p－r1,p－r2,…,p－rn,s1,s2,…,st就是1,2,…,p－12的一个排列。将式(5.2.1)中的p－12个数相乘，得ap－12·p－12!≡s1s2…st·r1r2…rn mod p
≡(－1)ns1s2…st(p－r1)(p－r2)…(p－rn) mod p
≡(－1)np－12! mod p又因为p－12!,p=1所以，ap－12≡(－1)n mod p证毕。
定理5.2.2设素数p>2。
(1) 2p=(－1)p2－18。
(2) 当(a,2p)=1时，ap=(－1)T其中，T=∑p－12j=1jap。
证明当1≤j≤p－12时，因为ja=pjap+tj其中0<tj<p。对该式两边求和，左边为a1+2+…+p－12=ap2－18右边为p∑p－12j=1jap+∑p－12j=1tj=pT+∑ti=1si+∑nj=1rj
=pT+∑ti=1si+∑nj=1(p－rj)－np+2∑nj=1rj由引理5.2.1的证明知s1,s2，…,st,p－r1,p－r2,…,p－rn是1,2，…,p－12的一个排列，∑ti=1si+∑nj=1(p－rj)=p2－18图5.2.1T的几何意义得(a－1)p2－18=(T－n)p+2∑nj=1rj
(a－1)p2－18≡T－np mod 2≡(T－n) mod 2≡(T+n) mod 2当a=2时，对于1≤j≤p－12，有ja≤p－1,jap=0所以T=∑p－12j=1jap=0所以n≡p2－18 mod 2而当(a,2p)=1时，a必为奇数，a－1≡0 mod 2，所以从上式可得T≡n mod 2，由引理5.2.1即得ap=(－1)T证毕。
T的几何意义如图5.2.1所示。
T表示图5.2.1中x轴、直线x=p2、直线y=apx所围成的△OAB内部的整数点的个数，这是因为以下两点: 
(1) 线段AB上x=p2，无整数点。线段OB上，因(a,p)=1,p a，无整数点。
(2) 当0<j<p2时，线段x=j上整数点个数为ajp，所以△OAB内部整数点个数为∑p－12j=0ajp=T如果a=q，其中q≠p且为素数，则有qp=(－1)T类似地有pq=(－1)S其中，S=∑q－12l=1lpp为图5.2.1中△OCB内部整数点个数。
而S+T是矩形OABC内部整数点的个数，因此S+T=p－12q－12所以有qppq=(－1)S+T=(－1)p－12q－12由此可得如下定理。
定理5.2.3(二次互反律)设素数p、q均大于2，p≠q，则qppq=(－1)p－12q－12或写成qp=(－1)p－12q－12pq二次互反律的意义: ap以p为周期，若a>p，则总能找到q<p,p,q=1，使得ap=qp。由二次互反律知，要求qp，只需求pq，它的周期q<p，即所求的Legendre符号的周期越来越小，最后变为求形如1p或2p的Legendre符号。
例5.2.1求137227。
解227为素数，137227=－90227=－12272·32·5227=(－1)2227322275227其中，2227=(－1)2272－18=－1，32227=1，5227=2275=25=－1所以137227=－1。这表明同余方程x2≡137 mod 227无解。
例5.2.2判断以下两个同余方程是否有解。若有解，求出其解数。
(1) x2≡－1 mod 365。
(2) x2≡2 mod 3599。
解
(1) 365不是素数，365=5·73，所以同余方程与以下同余方程组等价: x2≡－1 mod 5
x2≡－1 mod 73由于－15=1,－173=1，同余方程组有解，原方程的解数为4。
(2) 3599不是素数，3599=59·61，同余方程等价于以下同余方程组: x2≡2 mod 59
x2≡2 mod 61由于259=－1，所以同余方程组无解，原方程无解。
例5.2.3求分别以3为其二次剩余和二次非剩余的所有奇素数p。
解就是分别求满足3p=1和3p=－1的奇素数p。
因为3p=(－1)p－12p3由定理5.1.2的推论1，有(－1)p－12=1,p≡1 mod 4
－1,p≡－1 mod 4在求p3时，将p=3,5,7,11,13,17,19,…逐个代入，可知p=7,13,19,…(即p=6k+1，k∈N)时为1，p=5,11,17,…(即p=6k+5,k∈N)时为－1，所以p3=13=1,p≡1 mod 6
－13=－1,p≡－1 mod 6所以3p=1的充要条件是: p≡1 mod 4且p≡1 mod 6，即p≡1 mod 12；或p≡－1 mod 4且p≡－1 mod 6，即p≡－1 mod 12。
而3p=－1的充要条件是: p≡1 mod 4且p≡－1 mod 6；或p≡－1 mod 4且p≡1 mod 6。即: p≡5 mod 4且p≡5 mod 6；或p≡－5 mod 4且p≡－5 mod 6。所以p≡5 mod 12或p≡－5 mod 12。
例5.2.4求分别以11为其二次剩余和二次非剩余的所有奇素数p。
解11p=(－1)p－12p11
(－1)p－12=1,p≡1 mod 4
－1,p≡－1 mod 4对模11的绝对最小完全剩余系±1，±2,±3,±4,±5中的每个值进行计算，可得p11=1,p≡1,－2,3,4,5(mod 11)
－1,p≡－1,2,－3,－4,－5(mod 11)由同余方程组p≡a1 mod 4
p≡a2 mod 11得p≡－11a1+12a2 mod 44。
11p=1当且仅当a1=1,a2=1,－2,3,4,5；或a1=－1,a2=－1,2,－3,－4,－5。所以p≡±1,±5,±7,±9,±19(mod 44)。
同理，11p=－1当且仅当a1=1,a2=－1,2,－3,－4,－5；或a1=－1,a2=1,－2,3,4,5。所以p=±3,±13,±15,±17,±21(mod 44)。
例5.2.5证明满足p≡1 mod 4的素数有无穷多个。
证明用反证法。假设满足条件的素数有有限个，它们构成的集合记为A={p1,p2,…,pk}，构造P=1+(2p1p2…pk)2，满足P≡1 mod 4，P不是素数，否则P∈A，不可能。
设p是P的素因子，则－1p=－1+Pp=2(p1p2…pk)2p=1由定理5.1.2的推论1可知p≡1 mod 4，所以p∈A。由p|P，p|(2p1p2…pk)2可得p|(P－(2p1p2…pk)2)=1矛盾。证毕。
5.3Jacobi符号在求Legendre符号ap时，需要求出a的素因数分解，然后再用Legendre符号的性质和二次互反律来求解，但当a很大时计算复杂。为了避免这种复杂的计算，引入Jacobi符号。
定义5.3.1设P=p1p2…ps，其中pj(1≤j≤s)是素数，定义aP=ap1ap2…aps其中apj(1≤j≤s)是模pj的Legendre符号。称aP为Jacobi符号。
由定义5.3.1及Legendre符号的性质，容易推出Jacobi符号有以下性质。
定理5.3.1
(1) 1P=1。
(2) aP=0,(a,P)>1
±1,(a,P)=1。
(3) aP=a+PP。
(4) abP=aPbP。
(5) aP1P2=aP1aP2。
(6) 当a,P=1时，a2P=aP2=1。
为了进一步得到Jacobi符号的其他性质，需要以下引理。
引理5.3.1设aj≡1 mod m(1≤j≤s),a=a1a2…as，则a－1m≡a1－1m+a2－1m+…+as－1mmod m证明对s用归纳法。
s=2时，a－1=a1a2－1=(a1－1)+(a2－1)+(a1－1)(a2－1)由aj≡1 mod m，知a≡1 mod m，所以a－1m≡a1－1m+a2－1m+(a1－1)(a2－1)m mod m
≡a1－1m+a2－1mmod m其中，第3项中m2|(a1－1)(a2－1)。
设s=k时，结论成立。
当s=k+1时，a=(a1a2…ak)ak+1
a－1m≡a1a2…ak－1m+ak+1－1mmod m
≡a1－1m+a2－1m+…+ak－1m+ak+1－1mmod m证毕。
定理5.3.2－1P=(－1)P－12,2P=(－1)P2－18。
证明设P=p1p2…ps，则－1P=－1p1…－1ps=(－1)p1－12(－1)p2－12…(－1)ps－12=(－1)p1－12+p2－12+…+ps－12在引理5.3.1中，取m=2,aj=pj(1≤j≤s)，得