二次剩余

定义

对于整数 \(a\) 和奇素数 \(p\)，若存在整数 \(x\) 使 \(x^2 \equiv a \pmod p\)，则称 \(a\) 是模 \(p\) 的二次剩余；否则称 \(a\) 是模 \(p\) 的二次非剩余。

勒让德符号

对奇素数 \(p\)，勒让德符号定义为

\[ \left(\frac{a}{p}\right) = \begin{cases} 0, & p \mid a, \\ 1, & a \text{ 是模 } p \text{ 的二次剩余}, \\ -1, & a \text{ 是模 } p \text{ 的二次非剩余}. \end{cases} \]

性质

1. 对奇素数 \(p\)，非零剩余类中恰有 \(\frac{p-1}{2}\) 个二次剩余，另有 \(\frac{p-1}{2}\) 个二次非剩余。
2. 二次剩余与二次非剩余的乘法逆元保持其类型。
3. 对不同的奇素数 \(p\)、\(q\)，二次互反律为

\[ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}. \]

欧拉判别法

对 \(p \nmid a\)，有

\[ a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \pmod p. \]

因此 \(a\) 是模 \(p\) 的二次剩余，当且仅当 \(a^{\frac{p-1}{2}} \equiv 1 \pmod p\)；若结果为 \(-1\)，则 \(a\) 是二次非剩余。