《平方剩余》ppt课件

《《平方剩余》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章平方剩余第七章平方剩余7.1平方剩余（熟练）7.2勒让德符号（掌握）7.3雅可比符号（掌握）7.1平方剩余定义7.1.1设p是奇素数，即大于2的素数，如果二次同余式x2a(modp)，(a，p)=1(1)有解，则a称为模p的平方剩余，否则a成为模p的平方非剩余．之所以规定p是大于2的素数，是因为p=2时解二次同余式(1)非常容易．在有些书籍中，平方剩余和平方非剩余又分别称为二次剩余和二次非剩余．平方剩余例7.1.1求出p=5，7时的平方剩余和平方非剩余．解p=5时，因为121(mod5

2、)，224(mod5)，324(mod5)，421(mod5)，所以1，4是模5的平方剩余，而2，3是模5的平方非剩余．p=7时，因为121(mod7)，224(mod7)，322(mod7)，422(mod7)，524(mod7)，621(mod7)，所以1，2，4是模7的平方剩余，而3，5，6是模7的平方非剩余．平方剩余定理7.1.1设p是奇素数．在模p的简化剩余系中，有个平方剩余，个平方非剩余．证明　取模p的最小绝对简化剩余系则模p的全部平方剩余为由于(a)2a2(m

3、odp)平方剩余于是模p的全部平方剩余为现在证明这个平方剩余两两不同，用反证法．假设i2j2(modp)，ij，1i，j，则(i+j)(ij)0(modp)，p(i+j)(ij)，因为p是素数，于是p(i+j)或p(ij)，当ij，1i，j时这显然是不可能的，故证得．平方剩余所以在模p的简化剩余系中，有个平方剩余，同时有个平方非剩余．平方剩余以后我们求模p的平方剩余时，就可以只计算下列数了：12，22，…，．平方剩余例7.1.2求出p=11，17时的平方剩余和平方非剩

4、余．解p=11时：121(mod11)，224(mod11)，329(mod11)，425(mod11)，523(mod11)，所以1，3，4，5，9是模11的平方剩余，而2，6，7，8，10是模11的平方非剩余．p=17时：121(mod17)，224(mod17)，329(mod17)，4216(mod17)，528(mod17)，622(mod17)，7215(mod17)，8213(mod17)，所以1，2，4，8，9，13，15，16是模17的平方剩余，而3，

5、5，6，7，10，11，12，14是模17的平方非剩余．平方剩余定理7.1.2（欧拉判别法）设p是奇素数，(a，p)=1．a是模p平方剩余的充分必要条件是a是模p平方非剩余的充分必要条件是平方剩余证明　定理第1部分证明：必要条件证明：因为a是模p的平方剩余，则存在b,使b2a(modp)充分条件证明：由于,由定理6.4.4，同余式平方剩余有个解，可以验证所有的平方剩余正好就是它的个解．于是当时，a是模p平方剩余．平方剩余定理第2部分证明：对于任意aGF(p)*，有ap11(modp)，即

6、ap1–10(modp)，由于p是素数，则即平方剩余由定理的第1部分，a是模p平方剩余的充分必要条件是那么a是模p平方非剩余的充分必要条件就是定理证毕．平方剩余例7.1.31）判断3是不是模17的平方剩余？解　因为329(mod17)，34814(mod17)，所以3是模17的平方非剩余．平方剩余2）7是不是模29的平方剩余？解　因为72=499(mod29)，74(9)2816(mod29)，78(6)2367(mod29)，=714=7874727(

7、6)(9)1(mod29)，所以7是模29的平方剩余．7.2勒让德符号定义7.2.1设p是奇素数，a是整数．勒让德（Legendre）符号定义如下：由欧拉判别法我们立即得到下面的定理．定理7.2.1勒让德符号具有下列性质：勒让德符号2）如果ab(modp)，则3）4）如果(a，p)=1，则5）勒让德符号性质5证明：因为于是勒让德符号由于p是奇素数，p2，而勒让德符号只能取值0，1，所以上式中k只可能等于0，所以我们有定理该结论可以作为勒让德符号的第6项性质．定理7.2.2（二次互反

8、律）如果p，q都是奇素数，(p，q)=1，则二次互反律勒让德符号性质7：证明：分别把p1(mod8)，p3(mod8)，代入式中便得．二次互反律例7.2.1判别286是否是模563的平方剩余．解563是奇素数，又286=21113，于是而，（因为5633(mod8)．）（因为5634(mod13)．）二次互反律（因为5632(mod11)．）则故286是模563的平方非剩余．二次互反律例7.2.2判断x2=137(mod227)是否有解．解227是奇素数，又137902