《平方剩余ppt课件》由会员分享，可在线阅读，更多相关《平方剩余ppt课件（38页珍藏版）》请在金锄头文库上搜索。
1、电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余第七章平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余第七章第七章 平方剩余平方剩余7.1平方剩余熟练平方剩余熟练7.2勒让德符号掌握勒让德符号掌握7.3雅可比符号掌握雅可比符号掌握电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余7.1 平方剩余平方剩余定定义7.1.1设p是奇素数，即大于是奇素数，即大于2的素数，的素数，假假设二次同余式二次同余式x2 a (mod
2、p)，(a，p) = 1 (1) 有解，那么有解，那么a称称为模模p的平方剩余，否那么的平方剩余，否那么a成成为模模p的平方非剩余的平方非剩余 之所以之所以规定定p是大于是大于2的素数，是由于的素数，是由于p = 2时解二次同余式解二次同余式(1)非常容易在有些非常容易在有些书籍籍中，平方剩余和平方非剩余又分中，平方剩余和平方非剩余又分别称称为二二次剩余和二次非剩余次剩余和二次非剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余例例7.1.1求出求出p = 5，7时的平方剩余和平方非剩余的平方剩余和平方非剩余解解p =
3、 5时，由于，由于12 1 (mod 5)，22 4 (mod 5)，32 4 (mod 5)，42 1 (mod 5)，所以所以1，4是模是模5的平方剩余，而的平方剩余，而2，3是模是模5的平方非剩余的平方非剩余p = 7时，由于，由于12 1 (mod 7)，22 4 (mod 7)，32 2 (mod 7)，42 2 (mod 7)，52 4 (mod 7)，62 1 (mod 7)，所以所以1，2，4是模是模7的平方剩余，而的平方剩余，而3，5，6是模是模7的平方非的平方非剩余剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余
4、平方剩余平方剩余定理定理7.1.1设p是奇素数在模是奇素数在模p的的简化剩余系中，有化剩余系中，有 个平方剩余，个平方剩余， 个平方非剩余个平方非剩余证明取模明取模p p的最小的最小绝对简化剩余系化剩余系那么模那么模p的全部平方剩余的全部平方剩余为由于由于(a)2 a2 (mod p)电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余于是模于是模p的全部平方剩余的全部平方剩余为如今如今证明明这个个 平方剩余两两不同，用反平方剩余两两不同，用反证法法假假设i2 j2 (mod p)，ij，1i，j ，那么那么(i + j)(
5、i j) 0 (mod p)，p(i + j)(ij)，由于由于p是素数，于是是素数，于是p p(i + j)(i + j)或或p p(i(ij)j)，当当ij，1i，j 时这显然是不能然是不能够的，故的，故证得得电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余所以在模所以在模p的的简化剩余系中，有化剩余系中，有 个平方剩余，个平方剩余，同同时有有 个平方非剩余个平方非剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余 以后我以后我们求模求模p的
6、平方剩余的平方剩余时，就可以只，就可以只计算以下算以下数了：数了：12，22， 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余例例7.1.2求出求出p = 11，17时的平方剩余和平方非剩余的平方剩余和平方非剩余解解p = 11时：12 1 (mod 11)，22 4 (mod 11)，32 9 (mod 11)，42 5 (mod 11)，52 3 (mod 11)，所以所以1，3，4，5，9是模是模11的平方剩余，而的平方剩余，而2，6，7，8，10是模是模11的平方非剩余的平方非剩余p = 17时：12 1 (m
7、od 17)，22 4 (mod 17)，32 9 (mod 17)，42 16 (mod 17)，52 8 (mod 17)，62 2 (mod 17)，72 15 (mod 17)，82 13 (mod 17)，所以所以1，2，4，8，9，13，15，16是模是模17的平方剩余，而的平方剩余，而3，5，6，7，10，11，12，14是模是模17的平方非剩余的平方非剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余定理定理7.1.2欧拉判欧拉判别法法设p是奇素数，是奇素数，(a，p) = 1a是模是模p平方剩余的充分
8、必要条件是平方剩余的充分必要条件是a是模是模p平方非剩余的充分必要条件是平方非剩余的充分必要条件是电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余证明定理第明定理第1部分部分证明：明：必要条件必要条件证明：明：由于由于a是模是模p的平方剩余，那么存在的平方剩余，那么存在b, 使使 b2 a (mod p)充分条件充分条件证明：由于明：由于,由定理由定理6.4.4，同余式，同余式电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余有 个解，可以验证一切的
9、平方剩余正好就是它的 个解于是当时，a是模p平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余定理第定理第2部分部分证明：明：对于恣意于恣意aGF(p)*，有，有ap1 1 (mod p)，即即 ap1 1 0 (mod p)，由于由于p是素数，那么是素数，那么即即电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余由定理的第由定理的第1部分，部分，a是模是模p平方剩余的充分必要条件平方剩余的充分必要条件是是那么那么a是模是模p平方非剩余的充分必
10、要条件就是平方非剩余的充分必要条件就是定理定理证毕电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余例例7.1.31判判别3是不是模是不是模17的平方剩余？的平方剩余？解由于解由于32 9 (mod 17)，34 81 4 (mod 17)，所以所以3是模是模17的平方非剩余的平方非剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余27是不是模是不是模29的平方剩余？的平方剩余？解由于解由于72 = 49 9 (mod 29)，74 (9)2 81
11、 6 (mod 29)，78 (6)2 36 7 (mod 29)， = 714 =787472 7(6)( 9) 1 (mod 29)，所以所以7是模是模29的平方剩余的平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余7.2 勒勒让德符号德符号定定义7.2.1设p是奇素数，是奇素数，a是整数勒是整数勒让德德Legendre符号定符号定义如下：如下：由欧拉判由欧拉判别法我法我们立刻得到下面的定理立刻得到下面的定理定理定理7.2.1勒勒让德符号德符号 具有以下性具有以下性质： 电子科技大学电子科技大学 计算机科学与工程学院计算机科
12、学与工程学院UESTC Press 第七章 平方剩余勒勒让德符号德符号2假假设a b (mod p)，那么，那么34假假设(a，p) = 1，那么，那么5 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余勒勒让德符号德符号性性质5证明：明：由于由于 于是于是电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余勒让德符号勒让德符号 由于p是奇素数，p2，而勒让德符号只能取值0，1，所以上式中k只能够等于0，所以我们有电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UE
13、STC Press 第七章 平方剩余定理定理该结论可以作可以作为勒勒让德符号的第德符号的第6项性性质定理定理7.2.2二次互反律假二次互反律假设p，q都是奇素数，都是奇素数，(p，q) = 1，那么，那么电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律勒勒让德符号性德符号性质7：证明：分明：分别把把p 1 (mod 8)，p 3 (mod 8)，代入代入 式中便得式中便得电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律例例7.2.1判判别2
14、86能否是模能否是模563的平方剩余的平方剩余解解563是奇素数，又是奇素数，又286 = 21113，于是，于是而而 ，由于，由于563 3 (mod8)由于由于563 4 (mod13)电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律由于由于563 2 (mod11)那么那么故故286是模是模563的平方非剩余的平方非剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律例例7.2.2判判别x2 = (mod 227)能否有解能否有解解解
15、227是奇素数，又是奇素数，又 90 2325 (mod227)，那么，那么而而电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律故故原同余式无解原同余式无解电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余7.3 雅可比符号雅可比符号定定义7.3.1设m是大于是大于1的奇数，的奇数，m = p1p2pr是是m的素数分解，的素数分解，a是整数雅可比符号定是整数雅可比符号定义如下：如下：其中其中 是勒是勒让德符号德符号当当m是一个奇素数是一个奇素数时，雅可比符号和勒
16、，雅可比符号和勒让德符号德符号是一致的雅可比符号有着和勒是一致的雅可比符号有着和勒让德符号德符号类似的似的以下性以下性质： 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余雅可比符号雅可比符号12假假设a b (mod m)，那么，那么3假假设(a，m) = 1，那么，那么4567 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余证明性明性质6证明：明：如今只需如今只需证明明而而故得故得证 ，故性质6证得电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC
17、 Press 第七章 平方剩余性性质7证明：明：如今只需如今只需证明明而而故性故性质7证得得电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余雅可比符号雅可比符号定理定理7.3.1假假设m，n都是大于都是大于1的奇数，那么的奇数，那么证明假明假设(m，n)1，得到，得到定理成立如今假定理成立如今假设(m，n)=1设n = q1q2qs是是n的素数分解，那么的素数分解，那么电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学
18、院UESTC Press 第七章 平方剩余雅可比符号雅可比符号我我们有有故故电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余例例1判判别339能否模能否模1979的平方剩余的平方剩余解解1979是奇素数，所以是奇素数，所以该例是求勒例是求勒让德符号德符号 而此而此时勒勒让德符号与雅可比符号是一致的，所以我德符号与雅可比符号是一致的，所以我们求求339对1979的雅可比符号：的雅可比符号：由于由于1979 = 284 mod (339) 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余339 = 55 mod (71)由于由于71 =16 mod (55) 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余雅可比符号雅可比符号 所以339对1979的勒让德符号也等于1，故339是模1979的平方非剩余需求留意:电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余作业作业12610(1)11(1)14(1)18(1)19(1)
