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

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

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

方剩余

?? 第五章 二次同余式与平方剩余 第五章 二次同余式与平方剩余 §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)是等价的。证明

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 1 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

必要性显然；反之，设(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)，从而欧拉定理可知反之，若

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 2 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

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个解，

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 3 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

即模p的平方剩余2p?1p?1，从而模p的平方非剩余的个数为；22p?12)都是模p的平方剩余，而且它们两两不同余，2p?1，则(j?i)(j?i)?0(modp)，2- 2 - 另一方面，12,22,?,((因为若i2?j2(modp)，1?i?j?于是p|j?i或p|j?i，这是不可能的)，故它们就是模p的全部平方剩余。第五章 二次同余式与平方剩余 例求模13的平方剩余与平方非剩余。解平方剩余：12，22，32，42，52，62，即1，4，9，3，12，10； 平方非剩余：2，5，6，7，8，11。定理3设p为奇质数，则模p的两个平方剩余或两个平方非剩余的积是模p的两个平方剩余；模p的一个平方剩余与平方非剩余的积是模p的平方

非剩余。证明通过欧拉判别条件易证。 - 3 - 第五章 二次同余式与平方剩余 §2 勒让得符号与二次反转定律 ?a?定义勒让得(Legendre)符号??p??(读作：a对p的勒让得符号)是一个对??于给定的奇质数p定义在一切整数a上的函数，它的值规定如下：?1，a

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 4 ~

================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============

是模p的平方剩余；?a????p?????1，a是模p的平方非剩余；???0，p|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??a??b??a1a2?at??????3、??，特别地，?p??p??p??p????????a24、当p?|a时，??p????1。??p?12?1???1???5、??1，?p??p???(?1)?????1，当p?1(mod4)；????1，当p?3(mod4)。1定理1(高斯引理)设p是奇质数，(a,p)?1，a,2a,?,(p?1)a各数对模2p的最小非负剩余(余数)中大于?a?p?的个数为?，则??(?1)?。??2?p? p1证明设a,2a,?,(p?1)a各数对模p的最小非负剩余中小于的为22a1,a2,?,a?，大于pp的为b1,b2,?,b?，不可能有等于的(否则p|a矛盾)，22 - 4 - 第五章 二次同余式与平方剩余 1则显然有????(p?1)，并且?as?bt?2s?1t?1又因

--------------------精选公文范文，管理类，工作总结类，工作计划类文档，感谢阅读下载---------------------

~ 5 ~

本文来源：https://www.bwwdw.com/article/ob2d.html