二次剩余

二次剩余回答"哪些数模 $p$ 是平方数"，是研究高次同余方程与后续数论的基础。

定义

设 $p$ 为奇素数，$p\nmid a$。若存在整数 $x$ 使 $x^2 \equiv a \pmod p$，则称 $a$ 是模 $p$ 的二次剩余；否则称 $a$ 是模 $p$ 的二次非剩余。

性质

• 模 $p$ 的二次剩余恰有 $\dfrac{p-1}{2}$ 个，即 $1^2, 2^2, \dots, \left(\dfrac{p-1}{2}\right)^2$ 模 $p$ 所得的各不相同的剩余类；二次非剩余同样有 $\dfrac{p-1}{2}$ 个
• 对 $a\not\equiv 0 \pmod p$，方程 $x^2 \equiv a \pmod p$ 要么无解，要么恰有两个解 $\pm x$（这是高次同余方程 $x^k\equiv a$ 在 $k=2$ 时的特殊情形）
• 欧拉判别准则：$a^{\frac{p-1}{2}} \equiv \begin{cases}1, & a \text{ 是二次剩余}\\ -1, & a \text{ 是二次非剩余}\end{cases} \pmod p$

勒让德符号

勒让德符号 $\left(\dfrac{a}{p}\right) = \begin{cases}1, & a \text{ 是二次剩余}\\ -1, & a \text{ 是二次非剩余}\\ 0, & p \mid a\end{cases}$。欧拉判别准则可写为 $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p$。

示例

• 模 $7$：$1^2\equiv 1$，$2^2\equiv 4$，$3^2\equiv 2$，故二次剩余为 $\{1,2,4\}$，二次非剩余为 $\{3,5,6\}$
• 用欧拉判别准则复核：$2^3 = 8 \equiv 1 \pmod 7$，故 $2$ 是二次剩余；$3^3 = 27 \equiv -1 \pmod 7$，故 $3$ 是二次非剩余