平方剩余ppt课件.ppt
38页
电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余第七章平方剩余 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余第七章第七章 平方剩余平方剩余7.1 平方剩余〔熟练〕 平方剩余〔熟练〕7.2 勒让德符号〔掌握〕 勒让德符号〔掌握〕7.3 雅可比符号〔掌握〕 雅可比符号〔掌握〕 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余7.1 平方剩余平方剩余定定义7.1.1 设p是奇素数，即大于是奇素数，即大于2的素数，的素数，假假设二次同余式二次同余式x2 a (mod p)，，(a，，p) = 1 (1) 有解，那么有解，那么a称称为模模p的平方剩余，否那么的平方剩余，否那么a成成为模模p的平方非剩余．的平方非剩余． 之所以之所以规定定p是大于是大于2的素数，是由于的素数，是由于p = 2时解二次同余式解二次同余式(1)非常容易．在有些非常容易．在有些书籍籍中，平方剩余和平方非剩余又分中，平方剩余和平方非剩余又分别称称为二二次剩余和二次非剩余．次剩余和二次非剩余． 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余例例7.1.1 求出 求出p = 5，，7时的平方剩余和平方非剩余．的平方剩余和平方非剩余．解 解 p = 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 第七章 平方剩余平方剩余平方剩余定理定理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)(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的平方剩余的平方剩余时，就可以只，就可以只计算以下算以下数了：数了：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 (mod 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) = 1．．a是模是模p平方剩余的充分必要条件是平方剩余的充分必要条件是a是模是模p平方非剩余的充分必要条件是平方非剩余的充分必要条件是 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余证明 定理第明 定理第1部分部分证明：明：必要条件必要条件证明：明：由于由于a是模是模p的平方剩余，那么存在的平方剩余，那么存在b, 使使 b2 a (mod p)充分条件充分条件证明：由于明：由于,由定理由定理6.4.4，同余式，同余式 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余有 个解，可以验证一切的平方剩余正好就是它的 个解．于是当时，a是模p平方剩余． 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余定理第定理第2部分部分证明：明：对于恣意于恣意aGF(p)*，有，有ap1 1 (mod p)，，即即 ap1 –1 0 (mod p)，，由于由于p是素数，那么是素数，那么即即 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余由定理的第由定理的第1部分，部分，a是模是模p平方剩余的充分必要条件平方剩余的充分必要条件是是那么那么a是模是模p平方非剩余的充分必要条件就是平方非剩余的充分必要条件就是定理定理证毕．． 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余例例7.1.3 1〕判〕判别3是不是模是不是模17的平方剩余？的平方剩余？解 由于解 由于32 9 (mod 17)，，34 81 4 (mod 17)，，所以所以3是模是模17的平方非剩余．的平方非剩余． 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余平方剩余平方剩余2〕〕7是不是模是不是模29的平方剩余？的平方剩余？解 由于解 由于72 = 49 9 (mod 29)，，74 (9)2 81 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勒勒让德符号德符号 具有以下性具有以下性质：： 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余勒勒让德符号德符号2〕假〕假设a b (mod p)，那么，那么3〕〕4〕假〕假设(a，，p) = 1，那么，那么5〕〕 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余勒勒让德符号德符号性性质5证明：明：由于由于 于是于是 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余勒让德符号勒让德符号 由于p是奇素数，p2，而勒让德符号只能取值0，1，所以上式中k只能够等于0，所以我们有 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC 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 判 判别286能否是模能否是模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)能否有解．能否有解．解 解 227是奇素数，又是奇素数，又 90 2325 (mod227)，那么，那么而而 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余二次互反律二次互反律故故原同余式无解．原同余式无解． 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余7.3 雅可比符号雅可比符号定定义7.3.1 设m是大于是大于1的奇数，的奇数，m = p1p2…pr是是m的素数分解，的素数分解，a是整数．雅可比符号定是整数．雅可比符号定义如下：如下：其中其中 是勒是勒让德符号．德符号．当当m是一个奇素数是一个奇素数时，雅可比符号和勒，雅可比符号和勒让德符号德符号是一致的．雅可比符号有着和勒是一致的．雅可比符号有着和勒让德符号德符号类似的似的以下性以下性质：： 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余雅可比符号雅可比符号1〕〕2〕假〕假设a b (mod m)，那么，那么3〕假〕假设(a，，m) = 1，那么，那么4〕〕5〕〕6〕〕7〕〕 ． 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余证明 性明 性质6证明：明：如今只需如今只需证明明而而故得故得证．． ，故性质6证得． 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余性性质7证明：明：如今只需如今只需证明明而而故性故性质7证得．得． 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余雅可比符号雅可比符号定理定理7.3.1 假 假设m，，n都是大于都是大于1的奇数，那么的奇数，那么证明 假明 假设(m，，n)1，得到，得到定理成立．如今假定理成立．如今假设(m，，n)=1．．设n = q1q2…qs是是n的素数分解，那么的素数分解，那么． 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院UESTC Press 第七章 平方剩余 电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院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) 。
