第五章 二次同余式与平方剩余 - 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证明的全部平方剩余。,故它们就是模,这是不可能的或于是,,则,因为若两两不同余,的平方剩余,而且它们都是模另一方面,;的平方非剩余的个数为,从而模的个数为的平方剩余...