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

模p平方剩余

观察上面这张表，可以发现上下的对称性，字符化描述为：

因此，若要列出模p$p$的所有（非零）平方剩余，只需要计算出其中的一半：

我们的目的是发现模式，以便用来区分模p$p$的平方剩余与非平方剩余。

最后将会导出整个数论中最漂亮的定理之一—二次互反律

一些定义：

• 与一个平方数模p$p$同余的非零数称为模p$p$的二次剩余
• 不与任何一个平方数模p$p$同余的数称为模p$p$的二次非剩余
• 将二次剩余简记为QR$QR$，二次非剩余简记为NR$NR$
• 与0模p$p$同余的数既不是QR$QR$，也不是NR$NR$

定理 设p$p$为一个奇素数，则恰有p−12$\frac{p-1}{2}$个模p$p$的二次剩余，且恰有p−12$\frac{p-1}{2}$个模p$p$的二次非剩余。

由前面的结论知道，只要证明12,22,...,(p−12)2 mod p$1^2,2^2,...,(\frac{p-1}{2}{)}^{2}modp$是两两不同的。

假设b1,b2$b_1,b_2$是[1,p−12]$[1,\frac{p-1}{2}]$之间的数

且满足b21≡b22 (mod p)$b_1^2\equiv b_2^2(modp)$

我们要证明b1=b2$b_1=b_2$

由于b21≡b22 (mod p)$b_1^2\equiv b_2^2(modp)$，得到p | (b21−b22)=（b1−b2)(b1+b2)$p|(b_1^2-b_2^2)=（b_1-b_2)(b_1+b_2)$

然而b1+b2$b1+b2$显然不能被p$p$整除

所以b1−b2=0$b_1-b_2=0$

证毕。

QR与NR有什么关系呢？

一个不很难想到的结论是QR∗QR=QR$QR\ast QR=QR$

因为平方数乘平方数仍为平方数。所以两个二次剩余乘积模p$p$仍为二次剩余。

那么其他的组合呢？

经过一些小的表观察，可以得到：

在验证后面两个关系之前，我们先来看下原根与二次剩余的关系。

设g$g$是模p$p$的一个原根，辣么g$g$的幂：

可以给出p$p$的所有非零剩余。即[1,p−1]$[1,p-1]$。其中一半是二次剩余，一半是二次非剩余。

如何确定哪些是QR$QR$，哪些是NR$NR$呢？

显然g$g$的每个偶次幂是一个QR$QR$，即g2k$g^{2k}$。

注意到在(4)中恰有一半是偶次幂，所以g$g$的偶次幂给出了所有的二次剩余。而剩下的奇次幂必定是二次非剩余。

同时，也可以用指标来描述，二次剩余是指标I(a)$I(a)$为偶数的那些数a$a$

二次非剩余是指标I(a)$I(a)$为奇数的那些数a$a$

定理 二次剩余乘法法则—版本1

设p$p$为素数，则

• 两个模p$p$的二次剩余的积是二次剩余
• 二次剩余与二次非剩余的积是二次非剩余
• 两个二次非剩余的积是二次剩余

即

证明 对与p$p$互素的任意两个数a,b$a,b$，由指标的乘积法则知I(ab)≡I(a)+I(b)mod p−1$I(ab)\equiv I(a)+I(b)modp-1$

从而有I(ab)≡I(a)+I(b)mod 2$I(ab)\equiv I(a)+I(b)mod2$

后面的证明就很自然了。可以讨论(5)$(5)$中的三种情况。

对于(5)$(5)$式，你肯定会想到+1,−1$+1,-1$这种

许多年前，勒让德也想到了，而且还搞了点东西

a$a$模p$p$的勒让德符号是

定理 二次剩余乘法法则—版本2（使用勒让德符号）

设p$p$为素数，则

勒让德符号使计算可以更直观，比如

而

所以