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

《数论算法》 第四章 二次同余方程与平方剩余

第 4 章 二次同余方程与平方剩余

内容 1. 二次同余方程，平方剩余 2. 模为奇素数的平方剩余 3. 勒让德符号、雅可比符号 4. 二次同余方程的求解 二次同余方程有解的判断与求解 要点 4.1 一般二次同余方程

(一) 二次同余方程

，（aax2＋bx＋c≡0（mod m）

(二) 化简

设m＝p11p22?pkk，则方程（1）等价于同余方程

???0（mod m）） （1）

?ax2?bx?c?0（mod?2?ax?bx?c?0（mod?????ax2?bx?c?0（mod?问题归结为讨论同余方程

?1p1）?2p2） ?kpk）， （pa） （2） ax2＋bx＋c≡0（mod p?）

(三) 化为标准形式

p≠2，方程（2）两边同乘以4a，

4a2x2＋4abx＋4ac≡0（mod p?）

?2ax?b?2≡b2－4ac（mod

变量代换，

1/49

p?）

《数论算法》 第四章 二次同余方程与平方剩余

y＝2ax＋b （3）

有

y2≡b2－4ac（mod p?） （4）

当p为奇素数时，方程（4）与（2）等价。即 ? 两者同时有解或无解；有解时，对（4）的每个解

通过式（3）（x的一次同余方程，且（p, y?y0?modp?，

2a）＝1，所以解数为1）给出（2）的一个解x?x0?modp?，由（4）的不同的解给出（2）的不同的解；反之亦然。 ? 两者解数相同。

结论：只须讨论以下同余方程

x2≡a（mod p?） （5）

【例】化简方程7x2＋5x－2≡0（mod 9）为标准形式。 （解）方程两边同乘以4a＝4×7＝28，得

196x2＋140x－56≡0（mod 9）

配方 (14x＋5) 2－25－56≡0（mod 9） 移项 (14x＋5) 2≡81（mod 9） 变量代换 y＝14x＋5 得 y2≡0（mod 9）

（解之得y＝0, ±3，从而原方程的解为

x≡14?1(y－5)≡5?1 (y－5) ≡2(y－5)≡2y－10≡2y－1

≡－7, －1, 5≡－4, －1, 2（mod 9）） (四) 二次剩余

2/49

《数论算法》 第四章 二次同余方程与平方剩余

【定义4.1.1】设m是正整数，a是整数，ma。若同余方程

x2≡a（mod m） （6）

有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的平方非剩余（或二次非剩余）。

问题：

（1） 设正整数a是模p的平方剩余，若记方程（6）中的

解为x≡a（mod m），那么此处的平方根a（mod

m）与通常的代数方程x2＝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：y2≡x3＋x＋1（mod 7）的所有点。

（解）对 x＝0，1，2，3，4，5，6分别解出y： ，y≡1，6（mod 7） x＝0，y2≡1（mod 7），无解 x＝1，y2≡3（mod 7）

，y≡2，5（mod 7） x＝2，y2≡4（mod 7），无解 x＝3，y2≡3（mod 7）

3/49

《数论算法》 第四章 二次同余方程与平方剩余

，无解 x＝4，y2≡6（mod 7），无解 x＝5，y2≡5（mod 7），无解 x＝6，y2≡6（mod 7）

所以，满足方程的点为（0, 1），（0, 6），（2, 2），（2, 5）。

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

4.2 模为奇素数的平方剩余与平方非剩余

模为素数的二次方程

x2≡a（mod p）, (a, p)＝1 （1）

因为??x?＝x2，故方程（1）要么无解，要么有两个解。

2(一) 平方剩余的判断条件

【定理4.2.1】（欧拉判别条件）设p是奇素数，(a, p)＝1，则

（i）a是模p的平方剩余的充要条件是

a?p?1?2 ≡1（mod p） （2）

（ii）a是模p的平方非剩余的充要条件是

a?p?1?2 ≡－1（mod p） （3）

并且当a是模p的平方剩余时，同余方程（1）恰有两个解。

（证）先证pa时，式（2）或（3）有且仅有一个成立。 由费马定理 ap?1≡1（mod p）

?a??a?p?1?2?－1≡0（mod p）

?1??a???1?≡0（mod p） （4）

p?1?22p?124/49

《数论算法》 第四章 二次同余方程与平方剩余

即 pap?1?1＝a?p?1?2?1a?p?1?2?1

????但 ap?12?1,ap?12?1＝1或2

????且素数p>2。所以，p能整除ap?12?1ap?12?1，但p不能同时整除a?p?1?2?1和a?p?1?2?1（否则，p能整除它们的最大公因子1或2）

??????????所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。

（i）必要性。若a是模p的二次剩余，则必有x0使得

2x0≡a（mod p），

因而有

??2?p?1?2≡a?p?1?2（mod p）。 x0p?1??即 x0?ap?12（mod p）。

由于pa，所以p

x0，因此由欧拉定理知

x0p?1≡1（mod p）。

即（2）式成立。

充分性。已知a?p?1?2 ≡1（mod p），这时必有pa。故一次同余方程

bx≡a（mod p）, (1?b?p－1) （5）

有唯一解，对既约剩余系

－(p－1)/2，…，－1，1，…，(p－1)/2 （6）

由式（6）给出的模p的既约剩余系中的每个j，当b＝j时，必有唯一的x?xj属于既约剩余系（6），使得式（5）成立。若a不是模p的二次剩余，则必有j?xj。这样，既约剩余系（6）中的p－1个数就可按j、xj作为一对，两两分完。 （b1≠b2，则相应的解x1≠x2，且除了±1之外，每个数的逆不是它本身）

5/49

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数论算法》教案 4章(二次同余方程与平方剩余)在线全文阅读。