第5章 二次同余方程与平方剩余内容 1. 二次同余方程，平方剩余 2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点二次同余方程有解的判断与求解 5.1 一般二次同余方程（一） 二次同余方程2ax ＋bx ＋c ≡0（mod m ），（a 0（mod m ））（1）（二） 化简设m ＝k kp 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 ）， （pa ） （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）【例5.1.1】化简方程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））（四） 平方剩余【定义5.1.1】设m 是正整数，a 是整数，m a 。

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

【例】1是模4平方剩余，－1是模4平方非剩余。

【例】1、2、4是模7平方剩余，3、5、6是模7平方非剩余。

问题：（1）设正整数a是模p的平方剩余，若记方程（6）中的解为x≡a（mod m），那么此处的平方根a（modm）与通常的代数方程2x＝a的解a有何区别？（2）如何判断方程（6）有解？（3）如何求方程（6）的解？（五）例【例5.1.2】求以15为模的所有平方剩余和平方非剩余。

（解）直接计算12，22，...，142得模15的平方剩余（实际只需计算12，22， (72)1，4，9，10，6平方非剩余：2，3，5，7，8，11，12，13，14【例5.1.3】求满足方程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的图形称为椭圆曲线。

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

（p ＝时，方程恰好1个解）5. 2. 1 平方剩余的判断条件【定理5.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 能整除()()()()11121+---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 ）。

充分性：()21-p a ≡1（mod p ）⇒p a 。

故一次同余方程bx ≡a （mod p ）, (1≤b ≤p －1) （5）有唯一解，对既约剩余系⎭⎬⎫⎩⎨⎧----=21,,1,1,,21p p A ΛΛ （6） 设b ＝j 时方程（5）的解j x x =（A x j ∈）。

若a 不是模p 的二次剩余⇒jx j ≠⇒A 中各数可按j 、x j配对，两两分完。

（b 1≠b 2，则相应的解x 1≠x 2，且除了±1之外，每个数的逆不是它本身） ⇒()()p a p p m od )!1(21-≡-即 ()()p a p m od 121-≡-（威尔逊定理）与式（2）矛盾⇒必有某个0j ，使00j x j =⇒a 是模p 的二次剩余。

（ii ）显然（由（i ）的证明即知）其次，若0x 0（mod p ）是方程（1）的解，则－0x 也是其解，且必有0x －0x （mod p ）。

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

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

（解）由费马定理18a ≡1（mod 19），a ＝1, 2, …, 18方程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） 【2】2x ≡2（mod 19）无解，即a ＝2是模19的二次非剩余。

则9211922≡-≡－1（mod 19）◆ 针对充分性：【例】a ＝6，()21-p a ≡96≡1（mod 19），验证6是二次剩余。

解方程bx ≡6（mod 19）, (1≤b ≤18)所以6是二次剩余。

又选a ＝8，()21-p a ≡98≡－1（mod 19），验证：解方程 bx ≡8（mod 19）, 1≤b ≤181•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 ＝()()12211--p p a a5. 2. 2 平方剩余的个数【定理5.2.2】设p 是奇素数，则模p 的既约剩余系中平方剩余与平方非剩余的个数各为(p －1)／2，且(p －1)／2个平方剩余恰与序列12，22，…，221⎪⎭⎫ ⎝⎛-p 中的一个数同余。

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

但 1121---p p x x由定理4.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 。

故结论成立。

（定理4.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 的倍数）5.3 勒让德符号目的：快速判断整数a 是否为素数p 的平方剩余。

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

当的二次非剩余；是模当的二次剩余；是模当a p p a p a ,0,1,1 【推论】整数a 是素数p 的平方剩余的充要条件是⎪⎪⎭⎫ ⎝⎛p a ＝1。

（证）由定义5.3.1。

意义：判断平方剩余转化为计算勒让德符号的值。

【例5.3.1】计算勒让德符号17a ⎛⎫ ⎪⎝⎭的值。

其中a ＝0, 1, 2, …,16。

（解）直接计算： ⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛171617151713179178174172171＝1 ⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛1714171217111710177176175173＝－1 （注：本例仍是利用平方剩余而得到勒让德符号值） 问题：反过来，如何快速计算勒让德符号的值，以判断平方剩余。