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

本资料来源搜集与网络和投稿如有侵权牵扯利益关系请告知上传人联系删除。初等数论第五章二次同余式与平方剩余第五章二次同余式与平方剩余第五章二次同余式与平方剩余§1二次同余式与平方剩余二次同余式的一般形式是ax2。bx。c。0（modm）a。。0（modm）（1）下面讨论它的解的情况。。k。1。2令m。p1p2。pk则（1）有解的充要条件为ax2。bx。c。0（modpi。i）i。12。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。ba。b2。4ac得y2。a。0（modp）可以证明：同余式（4）和（5）是等价的。证明必要性显然；反之设（5）有一解y。y0因为（p2a）。1所以2ax。b。y0（modp）有解即（4）有解。由以上讨论可知二次同余式可以化为x2。a（modp）p为奇质数（6）（5）来求解当p|a时（6）仅有一个解x。0（modp）所以我们下面总假定p。|a或（pa）。1。因此下面主要研究形如x2。a（modp）（pa）。1p为奇质数同余式。（7）的定义若同余式x2。a（modp）（ap）。1p为奇质数有解则a叫做模p的平方剩余（二次剩余）若无解则a叫做模p的平方非剩余（二次非剩余）。定理1（欧拉判别条件）若（ap）。1则a是模p的平方剩余的充要条件为ap。12。1（modp）；a是模p的平方非剩余的充要条件为a-1-p。12。。1（modp）。若a是模p的平方剩余则（7）式恰有两解。第五章二次同余式与平方剩余证明（1）设a是模p的平方剩余则同余式x2。a（modp）（ap）。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）由欧拉定理可知若（ap）。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。12p。1p。12个平方剩余分别与1222。中的一数且仅与一数同余。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-另一方面1222。（（因为若i2。j2（modp）1。i。j。于是p|j。i或p|j。i这是不可能的）故它们就是模p的全部平方剩余。第五章二次同余式与平方剩余例求模13的平方剩余与平方非剩余。解平方剩余：122232425262即14931210；平方非剩余：2567811。定理3设p为奇质数则模p的两个平方剩余或两个平方非剩余的积是模p的两个平方剩余；模p的一个平方剩余与平方非剩余的积是模p的平方非剩余。证明通过欧拉判别条件易证。-3-第五章二次同余式与平方剩余§2勒让得符号与二次反转定律。a。定义勒让得（legendre）符号。。p。。（读作：a对p的勒让得符号）是一个对。。于给定的奇质数p定义在一切整数a上的函数它的值规定如下：。1a是模p的平方剩余；。a。。。。p。。。。。1a是模p的平方非剩余；。。。0p|a。。简单性质。。a。。b。。p。d。。d。。。。。1、当a。b（modp）时。。；或。p。。p。。p。。。。。p。。。。。。。。。。。。a。2、。。p。。。a。。p。12（modp）（欧拉判别条件）。。a1。。a2。。。。。p。。。。。。。。p。。at。。。。。。。p。。。。。。ab。