资源描述：
《次同余式和平方剩余》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章二次同余式和平方剩余一般二次同余式为进而有(a,p)=1P=2时可直接验证x=0，1是否是方程的解，对一般奇素数有(p,2)=1,同余式两边同乘4a有从而变成最简形式下面我们讨论这一类方程什么时侯有解，有多少解，如何求解等问题.§1欧拉判别条件定义：m>0,(a,m)=1,若对于整数a,有解，则称a是模m的平方乘余;否则，称a是模m的平方非乘余。对于有下面的定理。证：先证(3),设是方程的解，则-也满足方程，但不同余于-关于模p,否则有即因为(p,a)=1,所以有,不可能，所以方程至少有两解，又因方程的数不超过次数，恰有两解。定理：（欧拉判别定理）p>2,(a,p)=1,则有(1)a
2、是模p的平方乘余的充要条件是(2)a是模P的平方非乘余充要条件是(3)a是模p的平方乘余,则有两解(1)因为(a,p)=1,由欧拉定理知即有即或但上两式不能同时成立，否则有又若a是模P的平方乘余，则有两解，由定理知为p的倍数,有反之若则由定理知有解.（2）若a是模P的平方非乘余，则不是P的倍数，即不成立，只有反之也对。例：用欧拉判别定理判别是否有解。解：由欧拉判别定理所以无解。从上可知用欧拉判别定理判别当模比较大时，就比较麻烦，从理论上说a是否为平方乘余，只要在P的简化系中去找即可，且若a是平方数则一定为平方乘余，那么在P的简化系中有多少个是平方乘余呢？我们有定理：在模P的简化系中，平方剩
3、余和平方非剩余余各为个且个平方乘余分别与之一同余，而且仅与一数一同余。证明如下:证：由欧拉判别定理知平方剩余的个数是的解数。但其余式为0，由定理知有个解，即平方乘余的个数为从而平方非剩余的个数为p-1-=个。又中每一个数都是平方剩余， 所以有解，(i=1，2…),且两两不同余，因为若 则有这是不可能的，所以中两两不同余。注：上述定理给出了找平方剩余的比比较简单的办法。例1：求素数7的平方剩余和平方非剩余解：因为1，4是平方数，所以是平方剩余，又9关于7同余于2，所以2也是7的平方剩余，则在7的简化系中已经找到了3个平方剩余，则另外3个数3，5，6是7的平方非剩余。常见素数的平方剩余和平方
4、非剩余如下：素数平方剩余平方非剩余P=3，12P=51，42，3P=71，2，43，5，6P=111，4，9，5，32，6，7，8，10P=131，4，9，3，12，102，5，6，7，8，11欧拉判别定理从理论上这对判别一般的a是否有解已经是完善了，但缺点是计算量比较大。为了弥补计算量大的不足，我们要引进了勤让德符号，使得判别更简单。§2勒让德符号定义：p是一个给定的奇素数，对于整数a定义勒让德符号例：为了更方便地计算勒让德符号，我们给出其相关的性质，即有下面的定理。定理1：（1）（2）（3）（4）（5）证：（1）由定义可得.（2）若P
5、a，则P
6、b，由定义有又若（P，a）=1，则有由于
7、两边只能取1或-1，所以只能相等。（3）由定义若，则有则两边都为零相等若，则有由于两边只能取1或-1，所以只能相等。（4）显然。（5）由定义由于两边只能取1或-1，所以有定理2：设p是奇素数，则有证：因为把上述个式子相乘得因为从而证明了结论。定理3：（两次互反律）设p，q是两个不同的奇素数，则有证：（略）注：利用两次互反律可以使求勒让德符号变得更简单。例1：设p=4n+3是素质，试证当q=2p+1也是素数时，梅素数Mp不是素数。证：∵q=8n+7,∴q
8、24n+3-1，即q
9、Mp，∴Mp不是素数。例2：证明形如4m+1的素数有无穷多个。证：假设形如4m+1的素数只有有限个，设为p1…pk，
10、显然(2p1…pk)2+1的最小素因数p是奇数，且p与p1…pk不同设p为4m+3形的素数，但p整除(2p1…pk)2+1，表明(2p1…pk)2+1≡0（modp）即x2≡(-1)(modp)有解，即，但矛盾，∴p为4m+1形，这与4m+1的素数只有k个矛盾。例3：证明不定方程x2+23y=17无解。证：只要证x2≡17(mod23)无解即可，∵17≡1(mod4)∴∴x2≡17(mod23)无解，即原方程无解。例4：若3是素数p平方剩余，问p是什么形式的素数？解：∵由反转定律，注意到p>3，p只能为且∴只能下列情况或∴或§3雅可比符号对于勒让德符号可以判别是否有解，但对于判别是否有解，
11、理论上可化为然后进行综合判别，但这是不容易的，为此介绍一个更为实用的符号定义：给定正奇数m=对任意的整数a定义称为雅可比符号注：1、雅可比符号是勒让德符号的推广。2、雅可比符号为1时，不一定有解。例,但无解。3、雅可比符号为-1时，则一定无解。因为若=-1，则至少有一个i使得=-1,即无解，则无解.下面给出雅可比符号的类似于勒让德符号性质，定理1:(1)(2)(3)(4)定理2：设p是正奇数，则有定理3：（两次互反律）设
