二次剩余 基本概念 二次剩余是数论中研究平方数在模运算下性质的核心概念。设 \( m > 1 \) 为正整数（模数），若存在整数 \( x \) 使得同余方程 \( x^2 \equiv a \pmod{m} \) 有解，则称整数 \( a \) 是模 \( m \) 的二次剩余；否则称 \( a \) 是模 \( m \) 的二次非剩余。例如，模 7 时： \( 1^2 \equiv 1 \), \( 2^2 \equiv 4 \), \( 3^2 \equiv 2 \)，因此 1、2、4 是模 7 的二次剩余； 而 3、5、6 无法表示为平方，故为二次非剩余。 勒让德符号 当模数 \( p \) 为奇素数时，定义勒让德符号 \( \left( \frac{a}{p} \right) \) 为： \[ \left( \frac{a}{p} \right) = \begin{cases} 0 & \text{若 } p \mid a \\ 1 & \text{若 } a \text{ 是模 } p \text{ 的二次剩余} \\ -1 & \text{若 } a \text{ 是模 } p \text{ 的二次非剩余} \end{cases} \] 其核心性质包括： 周期性 ：\( \left( \frac{a+p}{p} \right) = \left( \frac{a}{p} \right) \) 完全积性 ：\( \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) \) 欧拉判别准则 ：\( \left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod{p} \) 二次互反律 该定律是二次剩余理论的巅峰成果，由高斯首次证明。对于不同的奇素数 \( p \neq q \)，有： \[ \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}} \] 其价值在于将计算 \( \left( \frac{p}{q} \right) \) 转化为计算 \( \left( \frac{q}{p} \right) \)，极大简化了判定过程。例如： \[ \left( \frac{3}{5} \right) = (-1)^{1 \times 2} \left( \frac{5}{3} \right) = \left( \frac{2}{3} \right) = -1 \] 说明 3 是模 5 的二次非剩余。 雅可比符号的推广 当模数 \( m \) 为合数时，通过其素因数分解 \( m = p_ 1^{k_ 1} p_ 2^{k_ 2} \cdots \) 定义雅可比符号： \[ \left( \frac{a}{m} \right) = \prod_ {i} \left( \frac{a}{p_ i} \right)^{k_ i} \] 虽然雅可比符号为 1 时不能保证 \( a \) 是模 \( m \) 的二次剩余，但其为 -1 时必定不是。该符号保留勒让德符号的积性，且二次互反律对奇素数对应的雅可比符号依然成立。 算法与应用 二次剩余判定算法（如 Tonelli–Shanks 算法）可高效解 \( x^2 \equiv a \pmod{p} \)。应用场景包括： 素数检测（如 Solovay–Strassen 算法） 密码学（Rabin 加密系统基于二次剩余问题的困难性） 组合设计（构造 Hadamard 矩阵）