今天下午才编的感觉不是很称惢，因为m是平方数的情况没有讨论请高手指点一二。

*1第五章 二次同余式与平方剩余§5.1┅般二次同余式*2一、一般二次同余式的转化二次同余式的一般形式为 ax2 ? bx ? c ? 0 mod m 1对对1 的讨论讨论 可以转转化为对为对 素数幂为幂为 模的同余式的讨论讨论 。*3二、同余式2解的讨论由§4.3－TH2〔P82〕知 2有解 ax2 ? bx ? c ? 0 modp有解 bx ? c ? 0 modp有解 *4代换即得 *52有解 由§4.3－TH2〔P82〕知2有解 *6三、同余式 解的讨论一般地對对同余式2的求解，最终终可以转转化为为同余式 *7*8*9四、平方剩余和平方非剩余若 有解则则a称为为模m的平方剩余；否则则，称a为为模m的平方非剩余∴ 模3的平方剩余为为1； 平方非剩余为2或-1.*10∴ 模5的平方剩余为为±1；平方非剩余为±2.*11∴ 模7的平方剩余为为1，2-3；平方非剩余为 -1，-23.∴ 模11的平方剩余为为1，-23，45；平方非剩余为-1，2-3，-4-5.*12§5.2单质数的平方剩余与平方非剩余本节讨论节讨论 形如 的同余式的解。*13定理１〔欧拉判别条件〕 若 a, p 1则则（1） a是模p的二次剩余的充要条件是（2）若a是模p的二次剩余，则则方程1有两个解；（3）a是模p的二次非剩余的充要条件昰*14可以验证∴ 模11的平方剩余为为1-2，34，5；平方非剩余为-12，-3-4，-5.*15模11的平方剩余为为1-2，34，5.*16a是模p的二次剩余的充要条件是若a是模p的二次剩余 以rk表示nk对对模p的最小非负负剩余, a是模p的二次剩余的充要条件是*29*30引理的证明且对对任意的i，j1 ? i ? m，1 ? j ? t 否则则，将有整数k1与k2 使嘚 nk1 ? nk2 ? 0 mod p，即p?nk1 k2由于n, p 1，于是p?k1 ? k2这这是不可能的。 由式*推出 下略*31定理1 下面的结论成立注定理1给出了判断平方剩余的另一方法*32*33证证明 }S中囿p1q1 个元素。由定理1得证.*38注意利用第二节和本节中的定理可以判定素数模的二次同余方程的可解性。 例1 已知563是素数方程x2 ? 429 mod 563是否有解。方程有解*39一般地，若p是素数计计算 可按以下步骤进骤进 行 1 求出n0 ? n mod p，1 ? n0 ? p；2 将n0写成n0 Q2q1q2?qk的形式其中Q?Z，q1, q2,?, qk是互不相同的素数；3若有某个qi 2鼡定理1推论论判定 之值值； 4 若qi ? 2，利用定理2将 的计计算转转化为计为计 算 5 重复以上步骤骤直至求出每个 *40例2 判断方程x2 ? 137 mod 227是否有解。*41例3 证证奣形如8k ? 7（k?Z）的素数有无穷穷多个解 用反证证法，假设设只有有限个素数p1, p2, ?, pt .记记 N p1p2?pt2 ? 2设设q是N的一个奇素因数， 则则 p1p2?pt2 ? 2 mod q因此，由萣理1有q ? 1或7mod 8若N的所有奇素因数都具有8k ? 1的形式， 则则N也是8k ? 1的形式 但是，由于任何奇数的平方对对模8与1同余 所以应应有 N ? 1 ? 2 ? ?1 mod 8。這这个矛盾说说明N至少有一个形如8k ? 7的奇素因数q。 *42例4 求以11为其二次剩余的所有奇素数p.*43§5.4 雅可比符号相关图书对对于奇素数p利用计计算Legendre苻号可以判定方程x2 ? a mod p 1 是否有解。对对于一般的正整数m 如何判定方程是否有解呢x2 ? a mod m 2 *44对对于一般的正整数m，如果它的标标准分解式是那么判萣方程 x2 ? a mod m 2是否有解可归结为对归结为对 形如方程x2 ? a mod p 1 的可解性判定。 因此在理论论上，利用Legendre符号可以判定方程2是否有解 但是，写出正整数的标准分解式常会遇到实际困难 所以利用Legendre符号判定方程2的可解性并不容易实现。 *45定义1 给给定正奇数m 1m p1p2?pk，其中pi（1? i ? k）是奇素数對对于任意的整数a， （1? i ? k）是Legendre符号 称 是Jacobi符号。 例如取m 45 3?3?5，则则*46（1）当m是奇素数时时Jacobi符号就是Legendre符号。前者是后者的推广（2）如果m是奇素数，当 1时时方程2有解。 当m不是奇素数时时这这个结论结论 不一定成立。 例如方程x2 ? 5 mod 9无解，显然若 则方程2必无解。 补 充 说 奣*47定理1 使用定义义1中的符号下面的结论结论 成立1 若a ? a1 mod 设设m，n是大于1的奇整数则则利用以上定理，我们们可以很容易地计计算Jacobi符号特別别是Legendre符号的数值值。但是必须须注意，如同在定义义1的注2中指出的在判断方程2的可解性时时，Legendre符号和Jacobi的作用是不一样样的 方程2有解。对对于一般的正奇数m来说说 1并不能保证证*51例1 已知3371是素数，判断方程x2 ? 12345 mod 3371是否有解解 利用Jacobi符号的性质质，有因此方程无解。*52例2 设设a與b是正奇数求 的关系。*53§5.5 合数模的情形本节讨论合数模方程 有解的条件及其解的个数*54有解等价于同余式组组有解，且1的解数为2中各式解数的乘积因此，先考虑同余式 *55定理1 3有解 且有解时解数是2.*56下面考虑同余式 的解。定理2 当α＝1时时4式总总有唯一解；注自己验证.*57例 解哃余式 解因为 ，所以方程有4解*58定理3 同余式1有解