二次同余式和平方剩余

1、第五章 二次同余式和平方剩余,一般二次同余式为 进而有 (a,p)=1 P=2时可直接验证x=0，1是否是方程的解， 对一般奇素数有(p,2)=1,同余式两边同乘4a有 从而变成最简形式 下面我们讨论这一类方程什么时侯有解，有多少解，如何求解等问题.,1 欧拉判别条件 定义：m0,(a,m)=1,若对于整数a, 有解，则称a是模m的平方乘余; 否则，称a 是模m的平方非乘余。 对于 有下面的定理。,证：先证(3),设 是方程的解，则- 也满足方程，但 不同余于- 关于模p,否则有 即 因为(p,a)=1,所以有 ,不可能，所以方程至少有两解，又因 方程的数不超过次数，恰有两解。,定理：（欧拉判

2、别定理）p2,(a,p)=1,则有 (1)a是模p的平方乘余的充要条件是 (2)a 是模P的平方非乘余充要条件是 (3)a是模p的平方乘余,则 有两解,(1)因为(a,p)=1,由欧拉定理知 即有 即 或 但上两式不能同时成立，否则有 又 若a 是模P的平方乘余，则 有两解，由定理知 为p的倍数,有 反之若 则由定理知 有解.,（2）若a 是模P的平方非乘余，则 不是P的倍数，即 不成立，只有 反之也对。,例：用欧拉判别定理判别 是否有解。 解：由欧拉判别定理 所以无解。 从上可知用欧拉判别定理判别当模比较大时，就比较麻烦，从理论上说a是否为平方乘余，只要在P的简化系中去找即可，且若a是平方数

3、则一定为平方乘余，那么在P的简化系中有多少个是平方乘余呢？我们有,定理：在模P的简化系中，平方剩余和平方非剩余余各为 个 且 个平方乘余分别与 之一同余，而且仅与一数一同余。 证明如下:,证：由欧拉判别定理知平方剩余的个数是 的解数。但 其余式为0，由定理知 有 个解，即平方乘余的个数为 从而平方非剩余的个数为p-1- = 个。,又 中每一个数都是平方剩余，所以 有解，(i=1，2 ),且两两不同余，因为若则有 这是不可能的，所以 中两两不同余。,注：上述定理给出了找平方剩余的比比较简单的办法。 例1：求素数7的平方剩余和平方非剩余 解：因为1，4是平方数，所以是平方剩余，又9关于7同余于2，

4、所以2也是7的平方剩余，则在7的简化系中已经找到了3个平方剩余，则另外3个数3，5，6是7的平方非剩余。,常见素数的平方剩余和平方非剩余如下： 素数 平方剩余 平方非剩余 P=3， 1 2 P=5 1，4 2， 3 P=7 1，2，4 3，5，6 P=11 1，4，9，5，3 2，6，7，8，10 P=13 1，4，9，3，12，10 2，5，6，7，8，11,欧拉判别定理从理论上这对判别一般的a是否有解已经是完善了，但缺点是计算量比较大。为了弥补计算量大的不足，我们要引进了勤让德符号，使得判别更简单。,2 勒让德符号 定义：p是一个给定的奇素数，对于整数a定义勒让德符号 例： 为了更方便地计

5、算勒让德符号，我们给出其相关的性质，即有下面的定理。,定理1：（1） （2） （3） （4） （5）,证：（1）由定义可得. （2）若P|a，则P|b，由定义有 又若（P，a）=1，则有 由于两边只能取1或-1，所以只能相等。 （3）由定义若 ，则有 则两边都为零相等 若 ， 则有 由于两边只能取1或-1，所以只能相等。,（4）显然。 （5）由定义 由于两边只能取1或-1，所以有,定理2：设p是奇素数，则有,证：因为 把上述 个式子相乘得 因为 从而证明了结论。,定理3：（两次互反律）设p，q是两个不同的奇素数，则有 证：（略） 注：利用两次互反律可以使求勒让德符号变得更简单。,例1：设p=4

6、n+3是素质，试证当q=2p+1也是素数时，梅素数Mp不是素数。 证： q=8n+7, q|24n+3-1，即q |Mp， Mp不是素数。,例2：证明形如4m+1的素数有无穷多个。 证：假设形如4m+1的素数只有有限个，设为p1pk，显然(2p1pk)2+1的最小素因数p是奇数，且p与p1pk不同 设p为4m+3形的素数，但p整除(2p1pk)2+1， 表明(2p1pk)2+10（mod p） 即x2(-1)(mod p)有解，即 ， 但 矛盾， p为4m+1形，这与4m+1的素数只有k个矛盾。,例3：证明不定方程x2+23y=17无解。 证：只要证x217(mod 23)无解即可， 171(

7、mod 4) x217(mod 23)无解，即原方程无解。,例4：若3是素数p平方剩余，问p是什么形式的素数？ 解： 由反转定律 ， 注意到p3，p只能为 且 只能下列情况 或 或,3 雅可比符号 对于勒让德符号 可以判别 是否有解，但对于 判别是否有解，理论上可化为 然后进行综合判别，但这是不容易的，为此介绍一个更为实用的符号 定义：给定正奇数m= 对任意的整数a定义 称 为雅可比符号,注：1、雅可比符号是勒让德符号 的推广。 2、雅可比符号为1时， 不一定有解。例 ,但 无解。 3、雅可比符号为-1时，则 一定无解。 因为若 =-1，则至少有一个i使得 =-1,即 无解，则 无解.,下面给

8、出雅可比符号的类似于勒让德符号性质，定理1 : (1) (2) (3) (4),定理2：设p是正奇数，则有 定理3：（两次互反律）设p，q是两个不同的正奇数，则有,关于雅可比符号这一些性质在此就不一一证明了，关键是要用雅可比符号的性质为计算勒让德符号 提供方便，即我们可以在计算勒让德符号时把其当成是雅可比符号，这样就不要求是奇素数的条件了。 来判别下面的方程是否有解。,例1： 判别 是否有解？ 解：因为563=7*80+3,又 所以原方程无解。 注：在计算勒让德符号 时，可以不要管143是否为素数而直接用二次互反律，为计算提供了方便。,例2：若 则p 不能写成 的形式 证：若p= ,则有若P|

9、x, 则有 p|y 于是可设 于是有 ，不可能。 所以有(p,x)=1,则有 矛盾，所以假设错误， p 不能写成 的形式。,例3：证明：形如8k+7的素数有无穷多个。 证：假设形如8k+7的素数只有有限多个，设为 共k个，记 设q是N的素因数，则有 则q=8k+1或8k+7.若N的所有素因数都是8k+1的形式，则N也是8k+1的形式，但任何数的平方用8模同余1 ，有 有矛盾， 说明N至少有一个8k+7的素因数q,显然q不同于 (i=1,2,.k),这与8k+7的素因数只有k个矛盾，所以假设错误，即形如8k+7的素数有无穷多个。,4 合数模两次同余方程 下面讨论 有解的条件和解数 设 ， 为奇素

10、数。 首先上述方程等价于方程组 （*）,定理1：设P是奇素数，（a，p）=1，则有 （1）若 =-1，则 无解。 （2）若 =1，则 有两解。,证（1）显然 （2）若 有解，则 有解，所以有 =1。 反之，若 =1，则 恰有两解，记为 ，由于（p，a）=1,所以 又因p为奇素数，所以有(p，2）=1则 ，所以有 由上一章的定理知 有解，并由此可得到得 的两解。,定理2：若(a,2)=1，则 （1） =1时， 有一解 （2） =2时， 有解的充要条件是a=4k+1，且若有解，则有两解。 （3） 时，则 有解的充要条件是a=8k+1，且若有解，则有四解。,证：若 有解，则x为奇数，设x=1+2t代入得 当 =2时，则有 当 时，则 当 =1时，显然 是方程的解 反之若上述条件成立，则有 当 =1时， 有解 当 =2时， 有解,当 时， （1）当 =3， 时， 有解 （2）当 3时，考虑 的x可以写成 的形式，代入 有 即 ， 即 是满足 的解。,同理 的解为 同样的方法有 对一切 3时有 的解为 对模 来说是四个解为,例：解方程 解：因为57=7*8+1，且 =6，所以由定理知有四解。将 代入 有 所以 代入 有 有 所以 代入 得 即 所以有 是 的解，