二次剩余与二次互反律 — Arendelle Royal Library

二次剩余与 Legendre 符号

定义

设 \(p\) 为奇素数，\(a\) 为整数且 \(p \nmid a\)。

若 \(x^2 \equiv a \pmod{p}\) 有解，则称 \(a\) 是模 \(p\) 的二次剩余（quadratic residue）。
若无解，则称 \(a\) 是模 \(p\) 的二次非剩余。

Legendre 符号定义为

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

Jacobi 符号：Legendre 符号的推广

当分母从奇素数推广到任意正奇数时，可定义 Jacobi 符号

\(\left(\frac{a}{n}\right)\)

它由奇数 \(n\) 的素因子分解逐项定义，本质上是 Legendre 符号的乘法延拓。需要注意：当 \(n\) 为合数时，\(\left(\frac{a}{n}\right)=1\) 只是不排斥 \(a\) 成为平方剩余，并不能保证 \(a\) 真的是模 \(n\) 的平方剩余。

因此，Legendre 符号是对模奇素数的精确判别，而 Jacobi 符号则更适合作为一个计算工具和互反律工具。详见雅可比符号与勒让德符号。

Legendre 符号的基本性质

性质 1：周期性

若 \(a \equiv b \pmod{p}\)，则 \(\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)\)。

性质 2：欧拉判别法

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

由于 Legendre 符号只取 \(\{-1, 0, 1\}\)，上述同余实际上是等式。

证明：

若 \(x^2 \equiv a \pmod{p}\) 有解，则 \(a^{(p-1)/2} \equiv x^{p-1} \equiv 1 \pmod{p}\)。
若无解，设 \(a \equiv g^s \pmod{p}\)（\(g\) 为原根），则 \(\mathrm{ord}_p(a) \nmid (p-1)/2\)（否则 \(a \equiv (g^{s/2})^2\)），故 \(a^{(p-1)/2} \equiv -1 \pmod{p}\)。

性质 3：完全乘性

\(\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\)

由欧拉判别法：\((ab)^{(p-1)/2} = a^{(p-1)/2} \cdot b^{(p-1)/2}\)。两边都在 \(\{-1, 0, 1\}\) 中取值且模 \(p\) 同余，而 \(p\) 为奇素数时 \(-1 \not\equiv 1\)，故等式成立。

从群论角度看，Legendre 符号是 \((\mathbb{Z}/p\mathbb{Z})^\times \to \{\pm 1\}\) 的群同态。

推论

在 \(\{1, 2, \ldots, p-1\}\) 中，二次剩余和非二次剩余各占 \((p-1)/2\) 个。

\((-1/p)\) 和 \((2/p)\)

\((-1/p)\)

\(\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} 1 & p \equiv 1 \pmod{4} \\ -1 & p \equiv 3 \pmod{4} \end{cases}\)

\((2/p)\)

\(\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} = \begin{cases} 1 & p \equiv \pm 1 \pmod{8} \\ -1 & p \equiv \pm 3 \pmod{8} \end{cases}\)

高斯引理

定理：设 \(p\) 为奇素数，\(p \nmid a\)。考虑数列 \(a, 2a, \ldots, \frac{p-1}{2}a\)，将每个数模 \(p\) 约化到 \((-p/2, p/2)\) 的最小绝对值剩余。设其中负数的个数为 \(\mu\)，则 \(\left(\frac{a}{p}\right) = (-1)^{\mu}\)

证明：对每个 \(j \in \{1, \ldots, (p-1)/2\}\)，设 \(ja \equiv \varepsilon_j b_j \pmod{p}\)，其中 \(b_j \in \{1, \ldots, (p-1)/2\}\)。

关键观察：\(b_1, \ldots, b_{(p-1)/2}\) 互不相同（若 \(b_i = b_j\) 则 \(i \equiv \pm j \pmod{p}\)，但 \(1 \leq i, j \leq (p-1)/2\) 时不可能）。因此

\(a^{(p-1)/2} \cdot \left(\frac{p-1}{2}\right)! = \prod_{j=1}^{(p-1)/2} (ja) = (-1)^{\mu} \cdot \left(\frac{p-1}{2}\right)! \pmod{p}\)

消去 \(((p-1)/2)!\) 后结合欧拉判别法即得。

二次互反律

定理（Gauss 的”黄金定律”）：设 \(p, q\) 为不同的奇素数，则 \(\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\)

计算例子

计算 \(\left(\frac{137}{227}\right)\)：

\(\left(\frac{137}{227}\right) = \left(\frac{-90}{227}\right) = \left(\frac{-1}{227}\right)\left(\frac{9}{227}\right)\left(\frac{10}{227}\right)\)

\(227 \equiv 3 \pmod{4}\)，故 \((-1/227) = -1\)。
\((9/227) = (3/227)^2 = 1\)。
\((10/227) = (2/227)(5/227)\)。\(227 \equiv 3 \pmod{8}\)，故 \((2/227) = -1\)。
由互反律：\((5/227) = (227/5) = (2/5) = -1\)（因 \(2^2 = 4 \equiv -1 \pmod{5}\)）。

故 \((10/227) = (-1)(-1) = 1\)，最终 \((137/227) = -1\)。

用二次互反律计算 Legendre 符号的复杂度约为 \(O((\log p)(\log q))\)。

分布推论

原型定理：给定非平方整数 \(A\)，存在正整数 \(M\) 和若干整数 \(r_1, \ldots, r_k\)（均与 \(M\) 互素），使得 \(A\) 是模 \(p\) 的二次剩余当且仅当 \(p \equiv r_i \pmod{M}\)（对某个 \(i\)）。

例：\(A = -3\) 时，\(\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)\)。利用互反律可得 \(-3\) 是模 \(p\) 的二次剩余当且仅当 \(p \equiv 1 \pmod{3}\)。

例：\(A = 6\) 时，需讨论 \(p \pmod{8}\) 和 \(p \pmod{3}\)，\(M = 24\)，6 是模 \(p\) 的二次剩余当且仅当 \(p \equiv 1, 5, 19, 23 \pmod{24}\)。

无穷多非二次剩余

定理：对任意非平方整数 \(A\)，存在无穷多素数 \(p\) 使得 \(A\) 不是模 \(p\) 的二次剩余。

利用 CRT 构造整数 \(b\)，使 \(b\) 是某些 \(p_i\) 的二次剩余但不是另一个 \(p_s\) 的二次剩余，然后取 \(b\) 的素因子并利用互反律计算。

Eisenstein 证明

Eisenstein 引理

设 \(f\) 是周期为 1 的奇函数，则

\(\prod_{k=1}^{(p-1)/2} f\!\left(\frac{ka}{p}\right) = \left(\frac{a}{p}\right) \prod_{k=1}^{(p-1)/2} f\!\left(\frac{k}{p}\right)\)

证明与高斯引理相同——重新排列最小绝对值剩余，奇函数给出 \((-1)^{\mu} = (a/p)\)。

完成证明

取 \(f(x) = 2\sin(2\pi x)\)，利用 \(\sin\) 的倍角公式和 \(n\) 次单位根的因式分解，分别写出 \((p/q)\) 和 \((q/p)\) 的乘积表达式并比较。交换 \(p, q\) 的角色时，奇函数性质恰好给出互反律中的符号 \((-1)^{\frac{p-1}{2}\frac{q-1}{2}}\)。

高斯和证明

高斯和的定义

设 \(\zeta_p = e^{2\pi i/p}\)，定义

\(G_a = \sum_{k=0}^{p-1} \left(\frac{k}{p}\right) \zeta_p^{ak}\)

记 \(G = G_1\)。

基本性质

\(G_0 = 0\)（Legendre 符号的值 \(\pm 1\) 各占一半）。
\(G_a = (a/p) \cdot G\)（变量代换 \(k \to ab\)）。
\(G^2 = (-1/p) \cdot p\)（核心公式）。

证明二次互反律

在分圆整数环 \(\mathbb{Z}[\zeta_p]\) 中：

方法一：\(G^q = (G^2)^{(q-1)/2} \cdot G = ((-1/p) \cdot p)^{(q-1)/2} \cdot G\)。

方法二：由 Freshman’s dream（\((a+b)^q \equiv a^q + b^q \pmod{q}\)），

\(G^q \equiv \sum_{k} \left(\frac{k}{p}\right)^q \zeta_p^{kq} = \sum_k \left(\frac{k}{p}\right) \zeta_p^{kq} = G_q = \left(\frac{q}{p}\right) G \pmod{q}\)

联立得 \(((-1/p) \cdot p)^{(q-1)/2} \cdot G \equiv (q/p) \cdot G \pmod{q}\)，除以 \(G\) 并用欧拉判别法整理即得互反律。

深层含义

\(G^2 = (-1/p) \cdot p\) 给出了二次域 \(\mathbb{Q}(\sqrt{p^*})\) 到分圆域 \(\mathbb{Q}(\zeta_p)\) 的嵌入（\(p^* = (-1)^{(p-1)/2} p\)）。这是类域论（class field theory）的最初萌芽，也是 Langlands 纲领的特例——用 Galois 对应的语言说，二次域是分圆域的子域，而 Gauss 和 \(G\) 本质上是嵌入的显式构造。关于 Gauss 和的更详细讨论，参见 Jacobi和与Gauss和与二次剩余。