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

《初等数论 第5章 二次同余式与平方剩余.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2021/9/161第五章二次同余式与平方剩余§5.1一般二次同余式2021/9/162一、一般二次同余式的转化二次同余式的一般形式为ax2bxc0(modm)。(1)对(1)的讨论可以转化为对素数幂为模的同余式的讨论。2021/9/163二、同余式(2)解的讨论由§4.3－TH2〔P82〕知(2)有解ax2bxc0(modp)有解bxc0(modp)有解2021/9/164代换即得2021/9/165(2)有解由§4.3－TH2〔P82〕知(2)有解2021/9/166三、同余

2、式解的讨论一般地，对同余式(2)的求解，最终可以转化为同余式2021/9/1672021/9/1682021/9/169四、平方剩余和平方非剩余若有解，则a称为模m的平方剩余；否则，称a为模m的平方非剩余。∴模3的平方剩余为1；平方非剩余为2(或-1).2021/9/1610∴模5的平方剩余为±1；平方非剩余为±2.2021/9/1611∴模7的平方剩余为1，2，-3；平方非剩余为-1，-2，3.∴模11的平方剩余为1，-2，3，4，5；平方非剩余为-1，2，-3，-4，-5.2021/9/16

3、12§5.2单质数的平方剩余与平方非剩余本节讨论形如的同余式的解。2021/9/1613定理１〔欧拉判别条件〕若(a,p)=1，则（1）a是模p的二次剩余的充要条件是（2）若a是模p的二次剩余，则方程(1)有两个解；（3）a是模p的二次非剩余的充要条件是2021/9/1614可以验证：∴模11的平方剩余为1，-2，3，4，5；平方非剩余为-1，2，-3，-4，-5.2021/9/1615模11的平方剩余为1，-2，3，4，5.2021/9/1616a是模p的二次剩余的充要条件是若a是模p的二次剩

4、余，2021/9/1617若a是模p的二次剩余，则方程(1)有两个解；根据§4.4-TH5[P86]知，方程(1)有两个解。定理5设np，则同余方程f(x)=xnan1xn1a1xa00(modp)有n个解的充要条件是存在整数多项式q(x)和r(x)，r(x)的次数

5、余与二次非剩余的个数都是且模p的每个二次剩余与且仅与数列中的一个数同余。模7的平方剩余为1，2，-3；平方非剩余为-1，-2，3.2021/9/1620定理2的证明：由定理1知，平方剩余的个数等于同余式的解数，所以据§4.4-TH5[P86]知，平方剩余的个数等于又模p的简化系中含有p-1个元素，从而平方非剩余的个数等于易证其两两对p不同余.得证.2021/9/1621§5.3勒让德符号利用欧拉判别条件虽然可以判定x2a(modp)的解的存在性，但对较大的质数模，实际运用很困难。通过引入勒让德

6、符号，本节给出了较方便的判别方法。2021/9/1622一、Legendre符号定义给定奇素数p，对于整数n，定义Legendre符号为如,1与4是模5的平方剩余，2与3是模5的平方非剩余，2021/9/1623二、基本性质2021/9/1624(1)的特例.2021/9/16252021/9/1626的取值只有0，±1，且p>2，故得证。2021/9/16272021/9/1628引理设(n,p)=1，对于整数k以rk表示nk对模p的最小非负剩余,a是模p的二次剩余的充要条件是2021/9/1

7、6292021/9/1630引理的证明：且对任意的i，j，1im，1jt，否则，将有整数k1与k2，使得nk1nk20(modp)，即pn(k1+k2)，由于(n,p)=1，于是pk1k2，这是不可能的。由式(*)推出下略2021/9/1631定理1下面的结论成立：注：定理1给出了判断平方剩余的另一方法。2021/9/16322021/9/1633证明：使用引理中的符号rk，ai，bi，m与t，2021/9/1634若n=2，2021/9/1635定理2(二次互反律)设p与q是

8、不同的两个奇素数，则2021/9/1636由定理1，有考察有序数对(u,v)所成的集合S={(u,v)；u=py，v=qx，1xp1，1yq1}显然S中有p1q1个元素。由于(p,q)=1，所以，对于任何(u,v)S，uv记S1={(u,v)；(u,v)S，u>v}，S2={(u,v)；(u,v)S，v>u}有S1S2=，S1S2=S。2021/9/1637记S1={(u,v)；(u,v)S，u>v}，S2={(u,v)；(u,v)S，v>u}有S1S2=，S1S