《平方剩余》ppt课件.ppt

第七章 平方剩余,第七章 平方剩余,7.1 平方剩余（熟练） 7.2 勒让德符号（掌握） 7.3 雅可比符号（掌握）,7.1 平方剩余,定义7.1.1 设p是奇素数，即大于2的素数，如果二次同余式 x2  a (mod p)，(a，p) = 1 (1) 有解，则a称为模p的平方剩余，否则a成为模p的平方非剩余． 之所以规定p是大于2的素数，是因为p = 2时解二次同余式(1)非常容易．在有些书籍中，平方剩余和平方非剩余又分别称为二次剩余和二次非剩余．,平方剩余,例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的平方非剩余．,平方剩余,定理7.1.1 设p是奇素数．在模p的简化剩余系中，有 个平方剩余， 个平方非剩余． 证明 取模p的最小绝对简化剩余系 则模p的全部平方剩余为 由于 (a)2  a2 (mod p),平方剩余,于是模p的全部平方剩余为 现在证明这个 平方剩余两两不同，用反证法． 假设 i2  j2 (mod p)，ij，1i，j ， 则 (i + j)(i j)  0 (mod p)， 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时的平方剩余和平方非剩余． 解 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的平方非剩余．,平方剩余,定理7.1.2 （欧拉判别法）设p是奇素数，(a，p) = 1． a是模p平方剩余的充分必要条件是 a是模p平方非剩余的充分必要条件是,平方剩余,证明 定理第1部分证明： 必要条件证明： 因为a是模p的平方剩余，则存在b, 使 b2  a (mod p) 充分条件证明：由于, 由定理6.4.4，同余式,平方剩余,有 个解，可以验证所有的平方剩余正好就是它的 个解．于是当 时，a是模p平方剩余．,平方剩余,定理第2部分证明： 对于任意aGF(p)*，有ap1  1 (mod p)， 即 ap1 –1  0 (mod p)， 由于p是素数，则 即,平方剩余,由定理的第1部分，a是模p平方剩余的充分必要条件是 那么a是模p平方非剩余的充分必要条件就是 定理证毕．,平方剩余,例7.1.3 1）判断3是不是模17的平方剩余？ 解 因为 32  9 (mod 17)， 34  81  4 (mod 17)， 所以3是模17的平方非剩余．,平方剩余,2）7是不是模29的平方剩余？ 解 因为 72 = 49  9 (mod 29)， 74  (9)2  81  6 (mod 29)， 78  (6)2  36  7 (mod 29)， = 714 =787472  7(6)( 9)  1 (mod 29)， 所以7是模29的平方剩余．,7.2 勒让德符号,定义7.2.1 设p是奇素数，a是整数．勒让德（Legendre）符号定义如下： 由欧拉判别法我们立即得到下面的定理． 定理7.2.1勒让德符号 具有下列性质：,勒让德符号,2）如果a  b (mod p)，则 3） 4）如果(a，p) = 1，则 5）,勒让德符号,性质5证明： 因为 于是,勒让德符号,由于p是奇素数，p2，而勒让德符号只能取值0，1，所以上式中k只可能等于0，所以我们有,定理 该结论可以作为勒让德符号的第6项性质．,定理7.2.2 （二次互反律）如果p，q都是奇素数，(p，q) = 1，则,二次互反律,勒让德符号性质7： 证明：分别把 p  1 (mod 8)， p  3 (mod 8)， 代入 式中便得．,二次互反律,例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 (mod 227)是否有解． 解 227是奇素数，又137  90  2325 (mod227)，则 而,二次互反律,故 原同余式无解．,7.3 雅可比符号,定义7.3.1 设m是大于1的奇数，m = p1p2…pr是m的素数分解，a是整数．雅可比符号定义如下： 其中 是勒让德符号． 当m是一个奇素数时，雅可比符号和勒让德符号是一致的．雅可比符号有着和勒让德符号相似的下列性质：,雅可比符号,1） 2）如果a  b (mod m)，则 3）如果(a，m) = 1，则 4） 5） 6） 7）,．,,,证明 性质6证明： 现在只需证明 而 故得证．,,,， 故性质6证得．,性质7证明： 现在只需证明 而 故性质7证得．,,,雅可比符号,定理7.3.1 如果m，n都是大于1的奇数，则 证明 如果(m，n)1，得到 定理成立．现在假设(m，n)=1．设n = q1q2…qs是n的素数分解，则,,．,,,,雅可比符号,我们有 故,,例1 判断339是否模1979的平方剩余． 解 1979是奇素数，所以该例是求勒让德符号 而此时勒让德符号与雅可比符号是一致的，所以我们求339对1979的雅可比符号： 因为1979 = 284 mod (339)．,,,,,,,,,,339 = 55 mod (71)． 因为71 =16 mod (55)．,,雅可比符号,所以339对1979的勒让德符号也等于1，故339是模1979的平方非剩余． 需要注意:,作业,1 2 6 10(1) 11(1) 14(1) 18(1) 19(1),。