第 4 章 二次同余方程与平方剩余 内容 1. 二次同余方程，平方剩余 2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点二次同余方程有解的判断与求解 4.1 一般二次同余方程(一) 二次同余方程2ax ＋bx ＋c ≡0（mod m ），（a0（mod m ）） （1）(二) 化简 设m ＝k k p p p αααΛ2121，则方程（1）等价于同余方程 ⎪⎪⎩⎪⎪⎨⎧≡++≡++≡++）（）（）（k k p c bx ax p c bx ax p c bx ax αααmod 0mod 0mod 02221221ΛΛ 问题归结为讨论同余方程 2ax ＋bx ＋c ≡0（mod αp ）， （p a ） （2）(三) 化为标准形式p ≠2，方程（2）两边同乘以4a ，422x a ＋4abx ＋4ac ≡0（mod αp ）()22b ax +≡2b －4ac （mod αp ）变量代换，y ＝2ax ＋b （3）有2y ≡2b －4ac （mod αp ） （4）当p 为奇素数时，方程（4）与（2）等价。

即● 两者同时有解或无解；有解时，对（4）的每个解()p y y mod 0≡，通过式（3）（x 的一次同余方程，且（p , 2a ）＝1，所以解数为1）给出（2）的一个解()p x x mod 0≡，由（4）的不同的解给出（2）的不同的解；反之亦然。

● 两者解数相同。

结论：只须讨论以下同余方程2x ≡a （mod αp ） （5）【例】化简方程7x 2＋5x －2≡0（mod 9）为标准形式。

（解）方程两边同乘以4a ＝4×7＝28，得196x 2＋140x －56≡0（mod 9）配方 (14x ＋5) 2－25－56≡0（mod 9）移项 (14x ＋5) 2≡81（mod 9）变量代换 y ＝14x ＋5 得 y 2≡0（mod 9）（解之得y ＝0, ±3，从而原方程的解为x ≡114-(y －5)≡15- (y －5)≡2(y －5)≡2y －10≡2y －1≡－7, －1, 5≡－4, －1, 2（mod 9））(四) 二次剩余【定义4.1.1】设m是正整数，a是整数，m a。

若同余方程2x≡a（mod m）（6）有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的平方非剩余（或二次非剩余）。

问题：（1）设正整数a是模p的平方剩余，若记方程（6）中的解为x≡a（mod m），那么此处的平方根a（modm）与通常的代数方程2x＝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：2y≡3x＋x＋1（mod 7）的所有点。

（解）对x＝0，1，2，3，4，5，6分别解出y：x＝0，2y≡1（mod 7），y≡1，6（mod 7）x＝1，2y≡3（mod 7），无解x ＝2，2y ≡4（mod 7），y ≡2，5（mod 7） x ＝3，2y ≡3（mod 7），无解 x ＝4，2y ≡6（mod 7），无解 x ＝5，2y ≡5（mod 7），无解 x ＝6，2y ≡6（mod 7），无解 所以，满足方程的点为（0, 1），（0, 6），（2, 2），（2, 5）。

说明：方程E ：2y ≡3x ＋x ＋1的图形称为椭圆曲线。

4.2 模为奇素数的平方剩余与平方非剩余 模为素数的二次方程2x ≡a （mod p ）, (a, p)＝1 （1）因为()2x -＝2x ，故方程（1）要么无解，要么有两个解。

(一) 平方剩余的判断条件【定理4.2.1】（欧拉判别条件）设p 是奇素数，(a, p)＝1，则（i ）a 是模p 的平方剩余的充要条件是()21-p a ≡1（mod p ） （2）（ii ）a 是模p 的平方非剩余的充要条件是()21-p a ≡－1（mod p ） （3）并且当a 是模p 的平方剩余时，同余方程（1）恰有两个解。

（证）先证p a 时，式（2）或（3）有且仅有一个成立。

由费马定理 1-p a ≡1（mod p ）()()221-p a －1≡0（mod p ）()()()()112121+---p p a a ≡0（mod p ） （4） 即 11--p a p ＝()()()()112121+---p p a a 但 ()()()1,12121+---p p a a ＝1或2且素数p>2。

所以，p 能整除()()()()112121+---p p a a ，但p 不能同时整除()121--p a 和()121+-p a （否则，p 能整除它们的最大公因子1或2）所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。

（i ）必要性。

若a 是模p 的二次剩余，则必有0x 使得20x ≡a （mod p ）， 因而有 ()()21p 20-x ≡()21-p a （mod p ）。

即 ()2110--≡p p a x （mod p ）。

由于p a ，所以p 0x ，因此由欧拉定理知10-p x ≡1（mod p ）。

即（2）式成立。

充分性。

已知()21-p a≡1（mod p ），这时必有p a 。

故一次同余方程 bx ≡a （mod p ）, (1≤b ≤p －1) （5） 有唯一解，对既约剩余系－(p －1)/2，…，－1，1，…，(p －1)/2 （6） 由式（6）给出的模p 的既约剩余系中的每个j ，当b ＝j 时，必有唯一的j x x =属于既约剩余系（6），使得式（5）成立。

若a 不是模p 的二次剩余，则必有j x j ≠。

这样，既约剩余系（6）中的p －1个数就可按j 、x j 作为一对，两两分完。

（b 1≠b 2，则相应的解x 1≠x 2，且除了±1之外，每个数的逆不是它本身）因此有()().mod )!1(21p a p p -≡-由威尔逊定理知()().mod 121p a p -≡-与式（2）矛盾。

所以必有某一0j ，使00j x j =，由此及式（5）知，a 是模p 的二次剩余。

（ii ）由已经证明的这两部分结论，立即推出第（ii ）条成立。

其次，若0x 0（mod p ）是方程（1）的解，则－0x 也是其解，且必有0x －0x （mod p ）。

故当(a , p )＝1时，方程（1）要么无解，要么同时有两个解。

（说明：本定理只是一个理论结果，当p >>1时，它并不是一个实用的判断方法）小结：对于任何整数a ，方程（1）的解数可能为T (x 2－a ；p )＝0, 1, 2 【例1】设p ＝19，验证定理4.2.1的证明过程。

（解）由费马定理知，对任何a ＝1, 2, …, 18，都有18a ≡1（mod 19）。

方程2x ≡1（mod 19）只有两个解，即x ≡±1（mod 19）。

从而必有9a ≡±1（mod 19）（视()2918a a ≡≡1（mod 19），即9a x ≡）针对必要性：例如a ＝17是模19的二次剩余，即存在0x ≡6使得26≡17（mod 19）。

那么必有 ()21-p a ≡917≡186≡1（mod 19）针对充分性：例如a ＝6，()21-p a ≡96≡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，()21-p a ≡98≡－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≡81•2• (18)(1•8)( 2•4)( 3•9)( 5•13)( 6•14)( 7•12)( 10•16)( 11•18)( 15•17)≡98≡－1（mod 19）【例2】判断137是否为模227的平方剩余。

（解）首先，227是素数。

其次，计算()1227137-≡－1（mod 227）所以，137是模227的平方非剩余。

【推论】设p 是奇素数，(a 1, p )＝1，(a 2, p )＝1，则 （i ）若a 1，a 2都是模p 的平方剩余，则a 1a 2是模p 的平方剩余；（ii ）若a 1，a 2都是模p 的平方非剩余，则a 1a 2是模p 的平方剩余；（iii ）若a 1是模p 的平方剩余，a 2是模p 的平方非剩余，则a 1a 2是模p 的平方非剩余。

（证）因()()2121-p a a ＝()()212211--p p a a(二) 平方剩余的个数【定理4.2.2】设p 是奇素数，则模p 的既约剩余系中平方剩余与平方非剩余的个数各为(p －1)／2，且(p －1)／2个平方剩余恰与序列12，22，…，221⎪⎭⎫ ⎝⎛-p 中的一个数同余。

（证）由定理4.2.1，模p 的平方剩余个数等于方程 21-p x≡1（mod p ）的解数。

但 1121---p p x x由定理3.4.5知，方程的解数为21-p ，即平方剩余的个数是21-p ，且平方非剩余的个数是(p －1)－21-p ＝21-p 。

其次，可以证明当1≤k 1≤21-p ，1≤k 2≤21-p ，且k 1≠k 2时，有21k 22k mod p 。

故结论成立。

（定理3.4.5：设p 为素数，n 为正整数，n ≤p 。

则同余方程()x f ＝0111a x a x a x n n n ++++--Λ≡0 mod p 有n 个解⇔x x p -被()x f 除所得余式的所有系数都是p 的倍数）4.3 勒让德符号目的：快速判断整数a 是否为素数p 的平方剩余。

(一) 勒让德符号【定义4.3.1】设p 是素数，定义勒让德（Legendre ）符号为：L(a, p)＝⎪⎪⎭⎫ ⎝⎛p a ＝⎪⎩⎪⎨⎧-。