《数论算法》教案 4章(二次同余方程与平方剩余)说课讲解

1、Good is good, but better carries it.精益求精，善益求善。数论算法教案 4章(二次同余方程与平方剩余)-二次同余方程与平方剩余内容二次同余方程，平方剩余模为奇素数的平方剩余勒让德符号、雅可比符号二次同余方程的求解要点二次同余方程有解的判断与求解一般二次同余方程二次同余方程bxc0（modm），（a0（modm）（1）化简设m，则方程（1）等价于同余方程问题归结为讨论同余方程bxc0（mod），（pa）（2）化为标准形式p2，方程（2）两边同乘以4a，44abx4ac0（mod）4ac（mod）变量代换，y2axb（3）有4ac（mod）（4）当p为奇素数时，方

2、程（4）与（2）等价。即两者同时有解或无解；有解时，对（4）的每个解，通过式（3）（x的一次同余方程，且（p,2a）1，所以解数为1）给出（2）的一个解，由（4）的不同的解给出（2）的不同的解；反之亦然。两者解数相同。结论：只须讨论以下同余方程a（mod）（5）【例】化简方程7x25x20（mod9）为标准形式。（解）方程两边同乘以4a4728，得196x2140 x560（mod9）配方(14x5)225560（mod9）移项(14x5)281（mod9）变量代换y14x5得y20（mod9）（解之得y0,3，从而原方程的解为x(y5)(y5)2(y5)2y102y17,1,54,1,2（m

3、od9）二次剩余【定义4.1.1】设m是正整数，a是整数，ma。若同余方程a（modm）（6）有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的平方非剩余（或二次非剩余）。问题：设正整数a是模p的平方剩余，若记方程（6）中的解为x（modm），那么此处的平方根（modm）与通常的代数方程a的解有何区别？如何判断方程（6）有解？如何求方程（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，

4、3，5，7，8，11，12，13，14【例4】求满足方程E：x1（mod7）的所有点。（解）对x0，1，2，3，4，5，6分别解出y：0，1（mod7），y1，6（mod7）1，3（mod7），无解2，4（mod7），y2，5（mod7）3，3（mod7），无解4，6（mod7），无解5，5（mod7），无解6，6（mod7），无解所以，满足方程的点为（0,1），（0,6），（2,2），（2,5）。说明：方程E：x1的图形称为椭圆曲线。模为奇素数的平方剩余与平方非剩余模为素数的二次方程a（modp）,(a,p)1（1）因为，故方程（1）要么无解，要么有两个解。平方剩余的判断条件【定理4.2.1

5、】（欧拉判别条件）设p是奇素数，(a,p)1，则（i）a是模p的平方剩余的充要条件是1（modp）（2）（ii）a是模p的平方非剩余的充要条件是1（modp）（3）并且当a是模p的平方剩余时，同余方程（1）恰有两个解。（证）先证pa时，式（2）或（3）有且仅有一个成立。由费马定理1（modp）10（modp）0（modp）（4）即但1或2且素数p2。所以，p能整除，但p不能同时整除和（否则，p能整除它们的最大公因子1或2）所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。（i）必要性。若a是模p的二次剩余，则必有使得a（modp），因而有（modp）。即（modp）。由于pa，所以p

6、，因此由欧拉定理知1（modp）。即（2）式成立。充分性。已知1（modp），这时必有pa。故一次同余方程a（modp）,(1bp1)（5）有唯一解，对既约剩余系(p1)/2，1，1，(p1)/2（6）由式（6）给出的模p的既约剩余系中的每个j，当bj时，必有唯一的属于既约剩余系（6），使得式（5）成立。若a不是模p的二次剩余，则必有。这样，既约剩余系（6）中的p1个数就可按j、xj作为一对，两两分完。（b1b2，则相应的解x1x2，且除了1之外，每个数的逆不是它本身）因此有由威尔逊定理知与式（2）矛盾。所以必有某一，使，由此及式（5）知，a是模p的二次剩余。（ii）由已经证明的这两部分结论，

7、立即推出第（ii）条成立。其次，若0（modp）是方程（1）的解，则也是其解，且必有（modp）。故当(a,p)1时，方程（1）要么无解，要么同时有两个解。（说明：本定理只是一个理论结果，当p1时，它并不是一个实用的判断方法）小结：对于任何整数a，方程（1）的解数可能为T(x2a；p)0,1,2【例1】设p19，验证定理4.2.1的证明过程。（解）由费马定理知，对任何a1,2,18，都有1（mod19）。方程1（mod19）只有两个解，即x1（mod19）。从而必有1（mod19）（视1（mod19），即）针对必要性：例如a17是模19的二次剩余，即存在6使得17（mod19）。那么必有1（m

8、od19）针对充分性：例如a6，1（mod19），验证6是二次剩余。解方程6（mod19）,(1b18)当b1,2,3,4,5,17,18（mod19）时，方程有唯一解x6,3,2,11,5,16,13（mod19）其中556（mod19）即当b5时，x5。所以6是二次剩余。又选a8，1（mod19），验证：解方程8（mod19）,(1b18)得188，248，398，428，5138，6148，7128，818，938，10168，11188，1278，1358，1468，15178，16108，17158，181181218(18)(24)(39)(513)(614)(712)(1016)

9、(1118)(1517)1（mod19）【例2】判断137是否为模227的平方剩余。（解）首先，227是素数。其次，计算1（mod227）所以，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个平方剩余恰与序列

10、12，22，中的一个数同余。（证）由定理4.2.1，模p的平方剩余个数等于方程1（modp）的解数。但由定理3.4.5知，方程的解数为，即平方剩余的个数是，且平方非剩余的个数是(p1)。其次，可以证明当1k1，1k2，且k1k2时，有modp。故结论成立。（定理3.4.5：设p为素数，n为正整数，np。则同余方程0modp有n个解被除所得余式的所有系数都是p的倍数）勒让德符号目的：快速判断整数a是否为素数p的平方剩余。勒让德符号【定义4.3.1】设p是素数，定义勒让德（Legendre）符号为：L(a,p)【推论】整数a是素数p的平方剩余的充要条件是1。（证）由定义4.3.1。因此，判断平方剩

11、余转化为计算勒让德符号的值。【例1】直接计算，得11（注：本例仍是利用平方剩余而得到勒让德符号值）问题：反过来，如何快速计算勒让德符号的值，以判断平方剩余。（勒让德符号的）性质【性质1】（欧拉判别法则）设p是奇素数，则对任意整数a，有（modp）（证）由定理4.2.1即知。【性质2】1（证）显然（因为方程x21（modp）始终有解x1（modp），或者由性质1立得）。【性质3】。（证）由性质1即得。【例2】1，1【推论】（证）p1（mod4）p4k11p3（mod4）p4k31另一种描述：设素数p2，则1是模p的二次剩余的充分必要条件是p1（mod4）。【性质4】（证）因x2ap（modp）x

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

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

14、od4），则方程q（modp）有解方程p（modq）无解（证）（i）设p1（mod4），即p4k1，则（ii）此时，p4s3，q4t3，则【例5】判断3是否是模17的平方剩余。（解）1所以，3是模17的平方非剩余。（不但如此，17也是3的平方非剩余，即2是3的平方非剩余）【例6】判断同余方程137（mod227）是否有解。（解）已知137与227均为奇素数，所以1所以，方程无解。另法：1【例7】判断同余方程1（mod365）是否有解，若有解，求解数。（解）由于365573，所以1（mod365）1所以方程有解，且解数为4。【例8】判断同余方程2（mod3599）是否有解，若有解，求解数。（解）

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

16、mod12）或p1（mod12）故3是模p二次剩余p1（mod12）【例2】设p为奇素数，d是整数。若1，则p一定不能表示为的形式。（证）用反证法。设p有表达式，则由p是素数可知(x,p)(y,p)1。这是因为若(x,p)1，则必有但由1知(d,p)1，所以py2，进而py。那么p2x2，p2y2p2x2dy2p矛盾。（即(x,p)(y,p)1成立）由(x,p)(y,p)1知，1，1，从而1与题设矛盾。【性质8】同余方程的解数是。【问题】求所有奇素数p，它以5或2为其平方剩余。雅可比符号问题：在计算勒让德符号时，若a为奇数，但非素数，如何快速计算。目的：为了快速计算勒让德符号。雅可比符号【定义

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

18、例1】由定义4.5.1(1)(1)1但可以验证2是模9的平方非剩余。又如当奇素数p3（mod4）时，由勒让德符号的性质知，1是模P的非平方剩余，即方程1（modp）无解，从而方程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】a15，m39，则J(a,m)00【性质2】1（证）J(1,m)1【性质3】（证）因为1故m1（mod4）

19、，即m1（mod4）（mod2）所以J(1,m)【推论】（证）m1mod4m4k113mod4m4k31【例3】1，1【性质4】（证）首先，由m和maa（modm）知maa（mod）其次，由雅可比符号和勒让德符号性质知【推论】若ab（modm），则（证）显然【性质5】（证）因【推论1】【推论2】当(m,a)1时，1【性质6】（证）因为11（mod64）而对任何奇数q，都有1（mod8）（i1,2,k），故（mod8）（mod2）所以J(2,m)【推论】m为奇数，则（证）因为当m8k1时k(8k2)偶数当m8k3时(2k1)(4k1)奇数【例4】1，1。【性质7】（二次互反律，高斯定理）设m、n

20、都是奇数，则或【性质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（mod563）是否有解。（解）563为素数，计算勒让德符号1所以，原方程无解。【例7】判断同余方程88（mod105）是否有解。（解）105357为合数，直接计算雅可比符号1所以，原方程无解。（因为原方程等价于方程组，而方程

21、组有解的充分必要条件是勒让德符号1。但1，说明、三者中至少有一个为1，即方程组中至少有一个方程无解，从而原方程无解）。再次说明雅可比符号可以用来否定方程有解，但不能肯定方程有解。【例8】求同余方程38（mod385）的解数。（解）3857511为合数，直接计算雅可比符号11并不能肯定原方程是否有解。所以，还须判断方程组中的每个方程是否有解。故再计算勒让德符号1，因此方程38（mod5）无解，最终说明原方程解数为零。模p平方根目的：解同余方程a（modp），p为素数且pa（1）方法：逐步迭代设p1s。理论基础理论基础：a是模p的平方剩余的充要条件（欧拉定理）Z1（modp）若t1则（偶数）1（m

22、odp）若1（modp）且t2，继续开方；否则，构造N，使1（modp）又可以继续开方。其中N为模p的平方非剩余（即）。目标：构造，使得：a（modp）从而得方程（1）的解：x（modp）算法将偶数p1表为p1s，t1，s为奇数。（1）选模p的平方非剩余N，即1，令b（modp），则有1（modp）1（modp）即b是模p的次单位根，但非模p的次单位根。（2）计算：（modp）则y满足方程：1（modp）（因1（modp）即y是模p的次单位根。（3）若t1，则x（modp）满足方程a（modp）（此时p12s，a（modp）。即方程已经解出）否则，t2，寻找，使得y满足方程1（modp）即y是

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

24、y是模p的次单位根。（a）若1（modp）令0，（modp），则即为所求。（b）若1（modp）令1，（modp），则即为所求。最后，kt1：（modp）满足方程：a（modp），p为素数且pa例【例1】用上述方法解同余方程186（mod401）（解）a186，p401。判断：p401为素数，且（用雅可比符号计算）111或（用勒让德符号计算）1(1)(1)1故原方程有解。准备：p1401140025，其中t4，s25。（1）由上边计算，1，即N3是模401的平方非剩余。令b268（mod401）。（2）计算103（mod401）235（mod401）（3）因为1（mod401）故令1，1032

25、68336（mod401）。（此时，）（4）因为1（mod401）故令0，336（mod401）。（此时，）（5）因为2351（mod401）故令1，336304（mod401）。（此时，）则304（mod401）满足原方程。（验证，92416186（mod401）【例2】设p是形为4k3的素数，若方程a（modp）有非零解，则其解为x（modp）（解）因为p4k3，故q为奇数，而方程a（modp）有解，则a是模p的二次剩余，从而有1（modp）即1（modp）已知原方程有非零解，即（a,p）1，故有a（modp）即a（modp）x（modp）【例3】设pq均为形如4k3的素数，且1，求解同余

26、方程：a（modpq）（解）首先a（modpq）而两个方程的解分别为（modp）和（modq）利用中国剩余定理解联立方程得原方程的解为（modp）uq（modq）vp（modpq）其中，1（modp），vp1（modq）【例3】解同余方程3（mod253）。（解）2531123，1123，二者均为形如4k3的素数，且1，解方程3（mod11），得5（mod11）解方程3（mod23），得7（mod23）利用中国剩余定理解联立方程M1123253，11，计算1（mod11），21（mod23）523171121（mod253）1159916，39，（mod253）合数的情形方程a（modm），（

27、a,m）1（1）a（mod），（a,p）1，1（3）P为奇素数【定理4.7.1】设p是奇素数，则（3）有解1。且有解时，（3）的解数为2。（证）必要性a（mod）有解a（modp）有解1充分性：设1，则存在整数x（modp）使得a（modp）令f(x)a，则2x，（2，p）1，故方程（3）的解数为2。【推论】同余方程（3）的解数为T1P2a（mod），（a,2）1，1（4）（当1时，方程a1（mod2）有一个解x1（mod2）【定理4.7.2】设1，则同余方程（4）有解的必要条件是当2时，a1（mod4）；当3时，a1（mod8）。若上述条件成立，则（4）有解。且当2时，解数是2；当3时，解数

28、是4。（证）必要性：若（4）有解，则存在整数z，使得a（mod）由（a,2）1知（z,2）1，记z12t，则上式可表为a14t(t1)（mod）（5）（注：14t4）所以当2时，a1（mod4）。而当3时，由（5）知a14t(t1)（mod8）又由2t(t1)知，a1（mod8）。充分性：（i）当2时，a1（mod4），方程a1（mod）显然有两个解x1，3（mod）（ii）当3时，a1（mod8）。此时，若3，易验证方程a1（mod）（6）的解为x1，5（mod），即(1)，0,1,2或()，0,1,2（7）其中，x31,5。若4，方程为a（mod）（8）令a（mod）（由第三章结论，希望从

29、方程（6）的解的值（7）中去找方程（8）的解，即确定）即2()a（mod）亦即a（mod）a（mod）所以（mod2）（mod2）（注意1（mod2）或2，0,1,2代入（7），方程（8）的解可表为（()，0,1,2（7）()，2，0,1,2()，0,1,2或()，0,1,2其中，且1（mod2）。（因为a1（mod8），故整数，从而为偶数）依次类推，对于4，设同余方程a（mod）（9）的解为()，0,1,2（10）或()（mod），0,1且1（mod2）。为了从方程（9）的上述解的值（10）中找出方程a（mod）（11）的解，令a（mod）即2()a（mod）亦即a（mod）a（mod）（1

30、2）所以（mod2）（mod2）或2，0,1,2代入（10）式，方程（11）的解可表为（()，0,1,2（10）()，2，0,1,2即()，0,1,2或()，0,1,2其中，且1（mod2）。（因为由式（12）可知整数，从而为偶数）【例1】解方程57（mod64）。（解）64，即6。因571（mod8），故方程有4个解。3时，解的值为x(1)，0,1,2（13）（解的表示：x1，3，5，7（mod8），或x1，57，3（mod8）或x(14t)(34t)（mod8），t0,1还可表为：x1，37，5（mod8）或x(12t)(52t)（mod8），t0,1此时方程为571（mod8）（1）4时

31、，在式（13）的所有值中找方程57（mod）（14）的解。为此，令57（mod）则21(4)57（mod）即157（mod）157（mod）11（mod2）1（mod2）或212，0,1,2代入（13）式得方程（14）的解为（x(1)，0,1,2（13）x(11)(5)，0,1,2或x(5)（mod），0,1或x5，133，5（mod）（5）5时，令57（mod），则25()57（mod）557（mod）50（mod2）0（mod2）或022，0,1,2故方程57（mod）的解为x(50)(5)，0,1,2或x(5)（mod），0,1或x5，215，11（mod）（5）6时，令57（mod），

32、则25()57（mod）557（mod）51（mod2）1（mod2）或12，0,1,2故方程57（mod）的解为(51)(21)，0,1,2或(21)（mod），0,1或21，5311，21（mod）（21）解同余方程总结方法一般方程方程f(x)0（modm）化为等价方程组其中解素数幂方程f(x)0（mod），p为素数deg(f)2，1，p2或奇素数的解法deg(f)2，2，p2或奇素数的解法deg(f)2，若已知1时的解，求2时的解问题（1）m的分解（2）deg(f)2，1时的解法习题4求满足下列方程的所有整点：（1）E：（mod7）；（2）E：（mod7）；（3）E：（mod17）；（4

33、）E：（mod17）。利用欧拉判别条件判断：（1）8是否是模53的二次剩余；（2）8是否是模67的二次剩余。求下列同余方程的解数：（1）2（mod67）；（2）2（mod67）；（3）2（mod37）；（4）2（mod37）；（5）1（mod221）；（6）1（mod427）；计算下列勒让德符号：（1）；（2）；（3）；（4）；（5）；（6）；（7）；（8）；（9）；（10）；（11）；（12）。判断下列同余方程是否有解，若有解，请求其解数：（1）7（mod227）；（2）249（mod257）（3）79（mod433）；（4）365（mod389）（5）11（mod511）；（6）2495（mod5249）；（7）116（mod91）；（8）514（mod6193）。解下列同余方程：（1）60（mod56）；（2）40（mod32）按要求完成下列问题：求以3为其二次剩余的全体素数；求以3为其二次剩余的全体素数；求以3为其二次非剩余的全体素数；求以3为二次剩余、以3为二次非剩余的全体素数；求以3为二次剩余、以3为二次非剩余的全体素数；求以3为二次非剩余、以2为二次剩余的全体素数（即以3为正的最小二次非剩余的全体素