初等数论第五章二次同余式与平方剩余

第五章 二次同余式与平方剩余 - 1 - 第五章 二次同余式与平方剩余 §1 二次同余式与平方剩余 。下面讨论它的解的情况，是二次同余式的一般形式)1()(mod0)(mod02mamcbxax 同余式。的为奇质数，，如因此，下面主要研究形。或，所以我们下面总假定仅有一个解时，来求解，当为奇质数，同余式可以化为由以上讨论可知，二次有解。有解，即，所以，因为有一解必要性显然；反之，设证明是等价的。和同余式可以证明：，得令，再配方得乘，用若为奇质数，只需讨论二次同余式极易求解，因此，我们时，同余式当。为质数，归结为解又可以为质数，有解，而解，有解的充要条件为，则令)7(1),()(mod1),(|)(mod0)6(|)6()(mod)4()(mod21)2,()5()5()4()5()(mod04,2)(mod04)2()4(4|)4()(mod0)()3(2)3()(mod0)()2()(mod0)(,,2,1)(mod0)1(2200222222222121pappaxapappxapppaxpybaxapyypAyacbAbaxypbacbaxaapppcbxaxxfpppcbxaxxfppcbxaxxfkipcbxaxpppmikik 。二次非剩余的平方非剩余叫做模，若无解，则二次剩余的平方剩余叫做模有解，则为奇质数若同余式)()(,1),(),(mod2papappapax定义式恰有两解。的平方剩余，则是模若。件为的平方非剩余的充要条是模；为的平方剩余的充要条件是模，则若欧拉判别条件)7()(mod1)(mod11),()(2121papapapapapapp定理1 第五章 二次同余式与平方剩余 - 2 - 。要条件为的平方非剩余的充分必是模因此，，要条件为的平方非剩余的充分必是模可知而由有且仅有一个成立，与从而，为奇质数，所以，因为于是，，则由欧拉定理可知，若有解，并且有两个解。可知同余式故由第四章第三节定理，所得的余式除，即，则反之，若。，从而由欧拉定理可知，于是设为有解，，的平方剩余，则同余式是模设)(mod1)(mod1)1()(mod1)(mod1)(mod11)(mod0)1)(1()(mod11),()2()(mod5)(mod0)()(mod)()(])[()1()(mod1)(mod1)(mod1),()(mod)1(21212121212112222121212112122papapapapapapppaapapapaxpxrxxaxpxqaxxaxxxxxxpapapapapaxpappppppppppppppp证明的全部平方剩余。，故它们就是模，这是不可能的或于是，，则，因为若两两不同余，的平方剩余，而且它们都是模另一方面，；的平方非剩余的个数为，从而模的个数为的平方剩余...