二次同余式和平方剩余课件.ppt

第五章 二次同余式和平方剩余;;证：先证(3),设 是方程的解，则- 也满足方程，但 不同余于- 关于模p,否则有 即 因为(p,a)=1,所以有 ,不可能，所以方程至少有两解，又因 方程的数不超过次数，恰有两解。;(1)因为(a,p)=1,由欧拉定理知 即有 即 或 但上两式不能同时成立，否则有 又 若a 是模P的平方乘余，则 有两解，由定理知 为p的倍数,有 反之若 则由定理知 有解.; （2）若a 是模P的平方非乘余，则 不是P的倍数，即 不成立，只有 反之也对。;例：用欧拉判别定理判别 是否有解。 解：由欧拉判别定理 所以无解。 从上可知用欧拉判别定理判别当模比较大时，就比较麻烦，从理论上说a是否为平方乘余，只要在P的简化系中去找即可，且若a是平方数则一定为平方乘余，那么在P的简化系中有多少个是平方乘余呢？我们有;定理：在模P的简化系中，平方剩余和平方非剩余余各为 个 且 个平方乘余分别与 之一同余，而且仅与一数一同余。 证明如下:;证：由欧拉判别定理知平方剩余的个数是 的解数。但 其余式为0，由定理知 有 个解，即平方乘余的个数为 从而平方非剩余的个数为p-1- = 个。;又 中每一个数都是平方剩余，所以 有解，(i=1，2… ),且两两不同余，因为若则有 这是不可能的，所以 中两两不同余。;注：上述定理给出了找平方剩余的比比较简单的办法。 例1：求素数7的平方剩余和平方非剩余 解：因为1，4是平方数，所以是平方剩余，又9关于7同余于2，所以2也是7的平方剩余，则在7的简化系中已经找到了3个平方剩余，则另外3个数3，5，6是7的平方非剩余。 ;; 欧拉判别定理从理论上这对判别一般的a是否有解已经是完善了，但缺点是计算量比较大。为了弥补计算量大的不足，我们要引进了勤让德符号，使得判别更简单。; §2 勒让德符号 定义：p是一个给定的奇素数，对于整数a定义勒让德符号 例： 为了更方便地计算勒让德符号，我们给出其相关的性质，即有下面的定理。;定理1：（1） （2） （3） （4） （5） ;证：（1）由定义可得. （2）若P|a，则P|b，由定义有 又若（P，a）=1，则有 由于两边只能取1或-1，所以只能相等。 （3）由定义若 ，则有 则两边都为零相等 若 ， 则有 由于两边只能取1或-1，所以只能相等。;（4）显然。 （5）由定义 由于两边只能取1或-1，所以有 ;证：因为 把上述 个式子相乘得 因为