初等数论 第五章 二次同余式与平方剩余
第五章二次同余式与平方剩余
第五章二次同余式与平方剩余
§1二次同余式与平方剩余
二次同余式的一般形式是ax2。bx。c。0（modm），a。。0（modm）（1）下面讨论它的解的情况。。k。1。2令m。p1p2。pk，则（1）有解的充要条件为ax2。bx。c。0（modpi。i），
i。1，2，。，k有解，而解f（x）。ax2。bx。c。0（modp。），p为质数（2）又可以归结为解f（x）。ax2。bx。c。0（modp），p为质数（3）。当p。2时，同余式（3）极易求解，因此，我们只需讨论二次同余式f（x）。ax2。bx。c。0（modp），p为奇质数（4）若p。|a，用4a乘（4）再配方得（2ax。b）2。4ac。b2。0（modp），令y。2ax。b，a。b2。4ac，得y2。a。0（modp）可以证明：同余式（4）和（5）是等价的。证明必要性显然；反之，设（5）有一解y。y0，因为（p，2a）。1，所以2ax。b。y0（modp）有解，即（4）有解。由以上讨论可知，二次同余式可以化为x2。a（modp），p为奇质数（6）（5）来求解，当p|a时，（6）仅有一个解x。0（modp），所以我们下面总假定p。|a或（p，a）。1。因此，下面主要研究形如x2。a（modp），（p，a）。1，p为奇质数同余式。（7）的
定义若同余式x2。a（modp），（a，p）。1，p为奇质数有解，则a叫做模p的平方剩余（二次剩余），若无解，则a叫做模p的平方非剩余（二次非剩余）。定理1（欧拉判别条件）若（a，p）。1，则a是模p的平方剩余的充要条件为ap。12。1（modp）；a是模p的平方非剩余的充要条件为a-1-
p。12。。1（modp）。
若a是模p的平方剩余，则（7）式恰有两解。第五章二次同余式与平方剩余
证明（1）设a是模p的平方剩余，则同余式x2。a（modp），（a，p）。1有解，设为。，于是。。a（modp），从而由欧拉定理可知反之，若ap。122ap。12。。p。1。1（modp）。2p。12。1（modp），则x。x。x（xpp。1。1）。x[（x）。ap。12]。x（x2。a）q（x）（modp），即x2。a除xp。x所得的余式r（x）。0（modp），故由第四章第三节定理5可知同余式x2。a（modp）有解，并且有两个解。（2）由欧拉定理可知，若（a，p）。1，则ap。1。1（modp），于是从而a（ap。12p。12。1）（ap。12。1）。0（modp），因为p为奇质数，所以1。。。1（modp），p。12。1（modp）与a。。1（modp）有且仅有一个成立，p。12而由（1）可知a是模p的平方非剩余的充分必要条件为a因此，a是模p的平方非剩余的充分必要条件为ap。12。。1（modp），。。1（modp）。定理2模p的简化剩余系中平方剩余与平方非剩余的个数各为而且p。1，2p。1p。12个平方剩余分别与12，22，。，中的一数，且仅与一数同余。22证明由定理1可知，模p的平方剩余的个数等于同余式xp。12。1（modp）的解数，因为x的个数为p。12。1能整除xp。x，所以它有p。1个解，即模p的平方剩余2p。1p。1，从而模p的平方非剩余的个数为；22p。12）都是模p的平方剩余，而且它们两两不同余，2p。1，则（j。i）（j。i）。0（modp），2-2-
(未完，全文共6344字，当前显示1431字)
(请认真阅读下面的提示信息)
