数论概论读书笔记 20.模p平方剩余

2019-04-13 21:50发布

站内文章 / 模拟电子
11062 0 1308

模p平方剩余

img 观察上面这张表，可以发现上下的对称性，字符化描述为：
p2+b2−2pb=(p−b)2≡b2(mod p)" role="presentation">p2+b2−2pb=(p−b)2≡b2(mod p)
因此，若要列出模p" role="presentation">p的所有（非零）平方剩余，只需要计算出其中的一半：
12 (mod p),22 (mod p),...,(p−12)2 (mod p)" role="presentation">12 (mod p),22 (mod p),...,(p−12)2 (mod p)
我们的目的是发现模式，以便用来区分模p" role="presentation">p的平方剩余与非平方剩余。 最后将会导出整个数论中最漂亮的定理之一—二次互反律 一些定义：
  • 与一个平方数模p" role="presentation">p同余的非零数称为模p" role="presentation">p的二次剩余
  • 不与任何一个平方数模p" role="presentation">p同余的数称为模p" role="presentation">p的二次非剩余
  • 将二次剩余简记为QR" role="presentation">QR，二次非剩余简记为NR" role="presentation">NR
  • 与0模p" role="presentation">p同余的数既不是QR" role="presentation">QR，也不是NR" role="presentation">NR
定理 设p" role="presentation">p为一个奇素数，则恰有p−12" role="presentation">p−12个模p" role="presentation">p的二次剩余，且恰有p−12" role="presentation">p−12个模p" role="presentation">p的二次非剩余。 由前面的结论知道，只要证明12,22,...,(p−12)2 mod p" role="presentation">12,22,...,(p−12)2 mod p是两两不同的。 假设b1,b2" role="presentation">b1,b2是[1,p−12]" role="presentation">[1,p−12]之间的数 且满足b12≡b22 (mod p)" role="presentation">b12≡b22 (mod p) 我们要证明b1=b2" role="presentation">b1=b2 由于b12≡b22 (mod p)" role="presentation">b12≡b22 (mod p)，得到p | (b12−b22)=（b1−b2)(b1+b2)" role="presentation">