数论算法讲义 4章(二次同余方程与平方剩余)

1、第 4 章 二次同余方程与平方剩余（一） 内容：l 二次同余方程，平方剩余l 模为奇素数的平方剩余l 勒让德符号、雅可比符号l 二次同余方程的求解（二） 重点：二次同余方程有解的判断与求解4.1 一般二次同余方程(一) 二次同余方程abxc0（mod m）， （a0（mod m） （1）(二) 化简设模数m可分解为m，则方程（1）等价于同余方程问题归结为讨论同余方程abxc0（mod ）， （pa） （2）(三) 化为标准形式方程（2）两边同乘以4a，44abx4ac0（mod ）4ac（mod ）变量代换，y2axb （3）有4ac（mod ） （4）当p为奇素数时，（4）与方程（2）是等价

2、的。也就是说，两者同时有解或无解；有解时，对（4）的每个解，通过式（3）（这时是x的一次同余方程，所以解数为1）给出（2）的一个解，由（4）的不同的解给出（2）的不同的解，且反过来也对，此外两者解数相同。由以上讨论知，只要讨论形如a（mod ） （5）的同余方程。【例】化简方程7x25x20（mod 9）为标准形式。（解）方程两边同乘以4×728，得196x2140x560（mod 9）即 (14x5) 225560（mod 9）亦即 (14x5) 281（mod 9）令 y14x5即得 y20（mod 9）（解之得y0, ±3，从而原方程的解为x(y5) (y5)2(y5

3、)2y102y17, 1, 54, 1, 2（mod 9）(四) 二次剩余【定义4.1.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）1是模4平方剩余，1是模4平方非剩余。【例2】（例2）1、2、4是模7平方剩余，3、5、6是模7平方非剩余。【例3】直接计算

4、12，22，142得模15的平方剩余为（实际上只要计算（12，22，82）1，4，9，10，6平方非剩余为2，3，5，7，8，11，12，13，14【例4】（例4）求满足方程E：x1（mod 7）的所有点。（解）对 x0，1，2，3，4，5，6分别解出y：0，1（mod 7），y1，6（mod 7）1，3（mod 7），无解2，4（mod 7），y2，5（mod 7）3，3（mod 7），无解4，6（mod 7），无解5，5（mod 7），无解6，6（mod 7），无解说明：方程E：x1的图形称为椭圆曲线。4.2 模为奇素数的平方剩余与平方非剩余模为素数的二次方程a（mod p）, (a, p

5、)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）恰有两个解。（证）首先证明对任一整数a，若pa，则式（2）或（3）有且仅有一个成立。由费马定理知1（mod p）故知0（mod p） （4）即 p1但1或2且素数p>2。所以，p能整除，但p不能同时整除和（否则，p能整除它们的最大公因子1或2）所以，由式（4）立即推出式（2）或

6、式（3）有且仅有一式成立。（i）必要性。若a是模p的二次剩余，则必有使得a（mod p），因而有 （mod p）。即 （mod p）。由于pa，所以p，因此由欧拉定理知1（mod p）。由以上两式就推出式（2）成立。充分性。设式（2）成立，这时必有pa。故一次同余方程a（mod p）, (1bp1) （5）有唯一解，对既约剩余系(p1)/2，1，1，(p1)/2 （6）由式（6）给出的模p的既约剩余系中的每个j，当bj时，必有唯一的属于既约剩余系（6），使得式（5）成立。若a不是模p的二次剩余，则必有。这样，既约剩余系（6）中的p1个数就可按j、xj作为一对，两两分完。（b1b2，则相应的解x

7、1x2，且除了±1之外，每个数的逆不是它本身）因此有由威尔逊定理知但这与式（2）矛盾。所以必有某一，使，由此及式（5）知，a是模p的二次剩余。（ii）由已经证明的这两部分结论，立即推出第（ii）条成立。其次，若0（mod p）是方程（1）的解，则也是其解，且必有（mod p）。故当(a, p)1时，方程（1）要么无解，要么同时有两个解。（说明：本定理只是一个理论结果，当p>>1时，它并不是一个实用的判断方法）小结：对于任何整数a，方程（1）的解数可能为T(x2a；p)0, 1, 2【例1】设p19，验证定理4.2.1的证明过程。（解）由费马定理知，对任何a1, 2, ,

8、18，都有1（mod 19）。而当p19为素数时，方程1（mod 19）只有两个解，即x±1（mod 19）。从而必有±1（mod 19）针对必要性：例如a17是模19的二次剩余，即存在6使得因为6217（mod 19）。那么必有1（mod 19）针对充分性：已知1（mod 19），验证6是二次剩余。解方程6（mod 19）, (1b18)当b1, 2, 3, 4, 5, , 17, 18（mod 9）时，方程有唯一解x6, 3, 3, 11, 5, , 16, 13（mod 9）即当b5时，x5。所以6是二次剩余。【例2】（例1）判断137是否为模227的平方剩余。（解）

9、首先，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的既约剩余系中平方剩余与平方非剩余的个数各为(p1)2，且(p1)2个平方剩余恰与序列12，22，中的一个数同余。（证）由定理4.2.1，模p的平方剩余的个数就等

10、于方程1（mod p）的解数。但11由定理3.4.5知，方程的解数为，即平方剩余的个数是，且平方非剩余的个数是(p1)。其次，可以证明当1k1，1k2，且k1k2时，有 mod p。故结论成立。4.3 勒让德符号目的：快速判断整数a是否为素数p的平方剩余。(一) 勒让德符号【定义4.3.1】设p是素数，定义勒让德（Legendre）符号为：L(a, p)【推论】整数a是素数p的平方剩余的充要条件是1。（证）由定义4.3.1。因此，判断平方剩余转化为计算勒让德符号值。【例1】直接计算，得11（注：本例仍是利用平方剩余而得到勒让德符号值）问题：反过来，如何快速计算勒让德符号的值，以判断平方剩余。(

11、二) （勒让德符号的）性质【性质1】（欧拉判别法则）设p是奇素数，则对任意整数a，有（mod p）（证）由定理4.2.1即知。【性质2】1（证）显然（因为方程x21（mod p）始终有解x±1（mod p），或者由性质1立得）。【性质3】。（证）由性质1即得。【例2】1，1【推论】（证）p1（mod 4） p4k11p3（mod 4） p4k31另一种描述：设素数p>2，则1是模p的二次剩余的充分必要条件是p1（mod 4）。【性质4】（证）因x2ap（mod p） x2a（mod p）【推论】若ab（mod p），则【性质5】（证）因【推论1】【推论2】当pa时，1这样，确定

12、a是否是模p的平方剩余就变为如何计算Legendre符号的值。上述性质可以用来计算，并由算术基本定理，设a 的分解式为±， （t0, 1）则（t0, 1）故只要能计算出，就可以计算出任意的，其中是小于p的素数。已经解决的计算：剩余的问题：，的计算。解决这些问题的基础是下面的二次互反律（Gauss定理）。【性质6】【例3】1，1，故2是模17的平方剩余，但不是模19的平方剩余。【推论】p为奇素数，则（证）因为当p8k1时，k(8k2)偶数m8k3时，(2k1)(4k1)奇数【例4】由于3171（mod 8），593（mod 8），故1，1，即2是模31的平方剩余，但不是模59的平方剩余

13、。【性质7】（二次互反律，高斯定理）pq且均为奇素数，则另一表示形式：说明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） 若pq3（mod 4），则方程q（mod p）有解方程p（mod q）无解（证）（

14、i）设p1（mod 4），即p4k1，则（ii）此时，p4s3，q4t3，则【例5】判断3是否是模17的平方剩余。（解）1所以，3是模17的平方非剩余。（不但如此，17也是3的平方非剩余，即2是3的平方非剩余）【例6】判断同余方程137（mod 227）是否有解。（解）已知137与227均为奇数，所以1所以，方程无解。另法：1【例7】判断同余方程1（mod 365）是否有解，若有解，求解数。（解）由于3655·73，所以1（mod 365） 1所以方程有解，且解数为4。【例8】判断同余方程2（mod 3599）是否有解，若有解，求解数。（解）由于359959·61，所以2（

15、mod 3599） 因为593（mod 8），即1，故方程2（mod 59）无解，从而原方程无解。【例9】证明形如4k1的素数有无穷多。（证）反证法：不然，形如4k1的素数为有限个，设为，令4b1即a 也形如4k1且a（i1,2, k）。所以a 为合数，设其素因数p 为奇数，则1所以1为模p平方剩余。由性质3的推论，p1（mod 4），即p也是形如4k1的素数。但显然p（i1,2, k），矛盾（否则，p，且由p知p1）。4.4 二次互反律的证明(一) 证明(二) 应用【例1】求所有奇素数p，它以3为其平方剩余。（解）即求所有奇素数p，使得1。易知p3。由二次互反律因为以及（排除偶数）知1 或

16、即p1（mod 12）或p1（mod 12）故3是模p二次剩余 p±1（mod 12）【例2】设p为奇素数，d是整数。若1，则p一定不能表示为x2dy2的形式。（证）用反证法。设p有表达式x2dy2，则由p是素数可知(x, p)(y, p)1。这是因为若(x, p)1，则必有px px2pdy2但是，由1知(d, p)1，所以py2，进而py。所以p2x2，p2y2 p2x2dy2p这显然不可能。（即(x, p)(y, p)1成立）那么，由(x, p)(y, p)1可知，±1，±1，从而有1与题设矛盾。【性质8】同余方程的解数是。【问题】求所有奇素数p，它以5或2

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

18、mod m）也无解），但当J(a, m)1时，方程a（mod m）则不一定有解。（4） 当k1时，J(a, m) L(a, m)，即此时勒让德符号的值与雅可比符号的值相等。（5） 因此，求勒让德符号的值转化为计算雅可比符号。【例1】由定义4.5.1(1)(1)1但可以验证2是模9的平方非剩余。又如当奇素数p3（mod 4）时，由勒让德符号的性质知，1是模P的非平方剩余，即方程1（mod p）无解，从而方程1（mod ）也无解。即1是模的平方非剩余。但若取m，则总有(1)(1)1问题：如何快速计算雅可比符号的值，以帮助加速勒让德符号的求值过程，从而加速判断平方剩余。(二) （雅可比符号的）性质【

19、性质1】若(a, m)1，则J(a, m)±1；若(a, m)1，则J(a, m)0。（证）因(a, m)1时，至少有某个a，即0，从而0。【例2】a15，m39，则J(a, m)00【性质2】1（证）J(1, m)1【性质3】（证）因为1故 m1（mod 4），即（mod 2）所以J(1, m) 【推论】（证）m1 mod 4 m4k113 mod 4 m4k31【例3】1，1【性质4】（证）首先，由m和maa（mod m）知maa（mod ）其次，由雅可比符号和勒让德符号性质知【推论】若ab（mod m），则（证）显然【性质5】（证）因···

20、3;【推论1】【推论2】当(m, a)1时，1【性质6】（证）因为1而对任何奇数q，都有1（mod 8）（i1,2, k），故故1（mod 64），即（mod 8）（mod 2）所以J(2, m) 【推论】m为奇数，则（证）因为当m8k1时，k(8k2)偶数m8k3时，(2k1)(4k1)奇数【例4】1，1。【性质7】（二次互反律，高斯定理）设m、n都是奇数，则或 【性质8】、n为整数，则（证）设，则左边 J(n, ) J(n, )· J(n, )右边这样，计算勒让德符号的值就转化为了计算雅可比符号的值。而后者的求值要比前者快了许多。【例5】用雅可比符号计算：(i) L(51, 71

21、) (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）是否有解。（解）1053·5·7为合数，直接计算雅可比符号1所以，原方程无解。（因为原方程等价于方程组，而方程组有解的充分必要条件是勒让德符号1。但现在1，说明、三者中至少有一个为1，即方程组中至少有一个方程无解，从而原方程无解）。【例8】求同余方程38（mod 385）的解

22、数。（解）3857·5·11为合数，直接计算雅可比符号11并不能肯定原方程是否有解。所以，还须判断方程组中的每个方程是否有解。故再计算勒让德符号1，因此方程38（mod 5）无解，最终说明原方程无解。4.6 模p平方根（1） 目的：解同余方程a（mod p），p为素数且pa （1）（2） 方法：逐步迭代设p12ts。(一) 理论基础理论基础：a是模p的平方剩余的充要条件是Z1（mod p）若t>1则±1（mod p）若1（mod p）且t>2，继续开方；否则，构造1（mod p）又可以继续开方。其中N为模p的平方非剩余（即1（mod p）。目标：构造，

23、使得a（mod p）从而方程（1）的解为x±（mod p）(二) 算法将偶数p1表为p1s，t1，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）若t1，则x（mod p）满足方程a（mod p）（此时p12s，a（mod p）否则，t2，寻找，使得y满足方程1（mod p）即y是模p的次单位根。（a）若1（mod p）令0，（mod p），则即为所求。（b）若1（mod p）令1，b（mod

24、p），则即为所求。（因(-1)(-1)1（mod p）（4）若t2，则x（mod p）满足方程a（mod p）（此时p1s，a（mod p）否则，t3，寻找，使得y满足方程1（mod p）即y是模p的次单位根。（a）若1（mod p）令0， （mod p），则即为所求。（b）若1（mod p）令1，（mod p），则即为所求。依次类推（k1）设找到整数满足1（mod p）即y是模p的次单位根：1（mod p）（k2）若tk，则x（mod p）满足方程a（mod p）否则，tk1，寻找整数，使得y满足方程1（mod p）即y是模p的次单位根。（a）若1（mod p）令0，（mod p），则即为所

25、求。（b）若1（mod p）令1，（mod p），则即为所求。特别，对kt1，有（mod p）满足方程a（mod p），p为素数且pa(三) 例【例1】（例1）用上述方法解同余方程186（mod 401）（解）a186，p401。判断：p401为素数，且（用雅可比符号计算）1·11或（用勒让德符合计算）1 ·(1) ·(1)1故原方程有解。计算p14011400·25，其中t4，s25。（1）由上边计算，1，即N3是模401的平方非剩余。令b268（mod 401）。（2）计算103（mod 401）235（mod 401）（3）因为1（mod 401）

26、故令1，103·268336（mod 401）。（此时，x318613，x2b 18613335）（4）因为1（mod 401）故令0，336（mod 401）。（此时，x1 x2b2 18613335）（5）因为235·1（mod 401）故令1，336·304（mod 401）。（此时，x0 x1b4 186133353140186133175）则304（mod 401）满足原方程。（此时，304292416186（mod 401）【例2】（例2）设p是形为4k3的素数，若方程a（mod p）有非零解，则其解为x±（mod p）（解）因为p4k3，故

27、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】（例3）设pq均为形如4k3的素数，且1，求解同余方程：a（mod pq）（解）首先a（mod pq）而两个方程的解分别为x±（mod p）和x±（mod q）利用中国剩余定理解联立方程得原方程的解为x±（mod p）uq±（mod q）vp （mod pq）其中，uq1 （mod p），vp1 （mod q）【例3】

28、解同余方程3（mod 253）。（解）25311·23，1123均为形如4k3的素数，且1，解方程 3（mod 11），得x±±±5（mod 11）解方程3（mod 23），得x±±±7（mod 23）利用中国剩余定理解联立方程M11·23253，11，计算1（mod 11），21（mod 23） x±5·23·1±7·11·21（mod 253）±115±99±16，±39，（mod 253）4.7 合数的情形方程

29、a（mod m），（a, m）1 （1）a（mod ），（a, p）1 ，1 （3）(一) P为奇素数【定理4.7.1】（定理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）的解数为T1(二) P2a（mod ），（a, 2）1 ，1 （4）（当1时，方程a1（mod 2）有一个解x1（mod 2）【定理4.7.2】（定理2）设1，则同余方程（4）有解的必要条件是（i） 当2时，

30、a1（mod 4）；（ii） 当3时，a1（mod 8）。若上述条件成立，则（4）有解。且当2时，解数是2；当3时，解数是4。（证）必要性：若（4）有解，则存在整数z，使得a（mod ）由（a, 2）1知（z, 2）1，记z12t，则上式可表为a14t(t1) （mod ） （5）（注：14t4）所以当2时，a1（mod 4）。而当3时，由（5）知a14t(t1) （mod 8）又由2t(t1)知，a1（mod 8）。充分性：（i）当2时，a1（mod 4），方程a1（mod ）显然有两个解 x1，3（mod ）（ii）当3时，a1（mod 8）。此时，若3，易验证方程a1（mod ） （6）

31、的解为 x±1，±5（mod ），即±(1)，0, ±1, ±2或±()，0, ±1, ±2 （7）其中，x31, 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）的解可表为±()，2，0, ±1, ±2±()，0,

32、 ±1, ±2或±()，0, ±1, ±2其中，且1（mod 2）。（因为a1（mod 8），故整数，从而为偶数）依次类推，对于4，设同余方程a（mod ） （9）的解为±()，0, ±1, ±2 （10）或±()，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）的解可表为±()，2，0, ±1, ±2即±()，0, ±1, ±2或±()，0, ±1, ±2其中，且1（mod 2）。（因为由式（12）可知整数，从而为偶数）【例1】（例1）解方程57（mod 64）。（解）64，即6。因571（mod 8），故方程有4个解。3时，解的值为x±(1)，0, ±1, ±2 （13）（解的表示方式：x1，3，5，7（mod 8），或 x±1，±5±7，±