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

二次同余式与平方剩余 内容： 二次同余方程，平方剩余 模为奇素数的平方剩余 勒让德符号、雅可比符号 二次同余方程的求解 重点：二次同余方程有解的判断与求解 一般二次同余式 二次同余式 a＋bx＋c≡0 mod m， （a≠0 mod m） （1） 化简 设模数m可分解为m＝，则方程（1）等价于同余方程 问题归结为讨论同余方程 a＋bx＋c≡0 mod ， （p┝a） （2） 化为标准形式 方程（2）两边同乘以4a， 4＋4abx＋4ac≡0 mod ≡－4ac mod 变量代换， y＝2ax＋b≡－4ac mod （4） 当p为奇素数时，（4）与方程（2）是等价的。也就是说，两者同时有解或无解；有解时，对（4）的每个解，通过式（3）（这时是x的一次同余方程，，所以解数为1）给出（2）的一个解，由（4）的不同的解给出（2）的不同的解，且反过来也对，此外两者解数相同。 由以上讨论知，只要讨论形如 ≡a mod （5） 的同余方程。 【例】化简方程7x2＋5x－2≡0（mod 9）为标准形式。 （解）方程两边同乘以28，得 196x2＋140x－56≡0（mod 9） 即 (14x＋5) 2－25－56≡0（mod 9） 亦即 y2≡81（mod 9） 二次剩余 【定义1】设m是正整数，a是整数，m┞a。若同余方程 ≡a mod m （6） 有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的二次非剩余。【定义1】 问题： 正整数a模p的平方剩余与实数中的平方根有何区别？ 如何判断方程（6）有解？ 如何求方程（6）的解？ 例 【例1】1是模4平方剩余，－1是模4平方非剩余。【例1】 【例2】1、2、4是模7平方剩余，3、5、6是模7平方非剩余。【例2】 【例3】直接计算12，22，…，142得模15的平方剩余为（实际上只要计算（12，22，…，82） 1，4，9，10，6 平方非剩余为 2，3，5，7，8，11，12，13，14 【例4】求满足方程E：≡＋x＋1 mod 7的所有点。【例4】 （解）对 x＝0，1，2，3，4，5，6分别解出y： ＝0，≡1 mod 7，y≡1，6 mod 7 ＝1，≡3 mod 7，无解 ＝2，≡4 mod 7，y≡2，5 mod 7 ＝3，≡3 mod 7，无解 ＝4，≡6 mod 7，无解 ＝5，≡5 mod 7，无解 ＝6，≡6 mod 7，无解 说明：方程E：≡＋x＋1的图形称为椭圆曲线。 模为奇素数的平方剩余与平方非剩余 模为素数的二次方程 ≡a mod p, (a,p)＝1 （1） 因为＝，故方程（1）要么无解，要么有两个解。 平方剩余的判断条件 【定理1】（欧拉判别条件）设p是奇素数，(a,p)＝1，则 （i）a是模p的平方剩余的充要条件是 （2） （ii）a是模p的平方非剩余的充要条件是 （3） 并且当a是模p的平方剩余时，，同余方程（1）恰有两个解。 （证）首先证明对任一整数a，若p┞a，则式（2）或（3）有且仅有一个成立。由费马定理知 故知 （4） 即 p│＝ 但 ＝1或2 且素数p2。所以，p能整除，但p不能同时整除和（否则，p能整除它们的最大公因子1或2） 所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。 （i）必要性。若a是模p的二次剩余，则必有使得 ≡a（mod p）， 因而有 ≡（mod p）。 即 （mod p）。 由于p┞a，所以p┞，因此由欧拉定理知 ≡1（mod p）。 由以上两式就推出式（2）成立。 充分性。设式（2）成立，这时必有p┞a。故一次同余方程 ≡a（mod p）, (1≤b≤p－1) （5） 有唯一解，对简化剩余系 －(p－1)/2，…，－1，1，…，(p－1)/2 （6） 由式（6）给出的模p的既约剩余系中的每个j，当b＝j时，必有唯一的属于简化剩余系（6），使得式（5）成立。若a不是模p的二次剩余，则必有。这样，既约剩余系（6）中的p－1个数就可按j、xj作为一对，两两分完。 （b1≠b2，则相应的解x1≠x2，且除了±1之外，每个数的逆不是它本身） 因此有 由威尔逊定理知 但这与式（2）矛盾。所以必有某一，使，由此及式（5）知，a是模p的二次剩余。