Gauss 和与二次互反律

设 $p, q$ 为互异奇素数，Legendre 符号 $\left(\frac{\cdot}{p}\right)$ 如常定义。二次互反律断言：

\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.

下面用 Gauss 和给出一个证明。

准备工作

令 $\zeta_p = e^{2\pi i/p}$ 是一个 $p$ 次本原单位根。

Lemma 1.

\sum_{k=0}^{p-1} \zeta_p^{ak} = \begin{cases} p, & p \mid a, \\ 0, & p \nmid a. \end{cases}

Proof. $p \mid a$ 时各项均为 $1$ ，和为 $p$ 。 $p \nmid a$ 时 $\zeta_p^a \neq 1$ 是 $p$ 次单位根，几何级数求和即得。 $\square$

Definition. 对 $a \in \mathbb{Z}$ ，定义 Gauss 和

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

记 $g := g_1$ 。

Proposition. Gauss 和满足以下性质：

$g_a = \left(\frac{a}{p}\right) g$ 对任意 $a \in \mathbb{Z}$ 成立。
记 $p^* = (-1)^{\frac{p-1}{2}}p$ ，则 $g^2 = p^*$ 。

Proof. (1) $p \mid a$ 时， $\zeta_p^{ak}=1$ ， $\sum_k \left(\frac{k}{p}\right)=0$ ，等式成立。 $p \nmid a$ 时，

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

令 $b$ 为 $a$ 模 $p$ 的乘法逆元。换元 $k \mapsto bk$ 即得 $g_a = \left(\frac{a}{p}\right) g$ 。

(2) 用两种方式计算 $\sum_{a=0}^{p-1} g_a g_{-a}$ 。

一方面，由 (1) 知 $p \nmid a$ 时 $g_a g_{-a} = \left(\frac{a}{p}\right)\left(\frac{-a}{p}\right) g^2 = \left(\frac{-1}{p}\right) g^2$ 。对 $a$ 求和，

\sum_{a=0}^{p-1} g_a g_{-a} = \left(\frac{-1}{p}\right)(p-1) g^2.

另一方面，展开 $g_a g_{-a}$ ：

g_a g_{-a} = \sum_{k=0}^{p-1} \sum_{\ell=0}^{p-1} \left(\frac{k}{p}\right)\left(\frac{\ell}{p}\right) \zeta_p^{a(k-\ell)}.

对 $a$ 求和，交换求和次序：

\sum_{a=0}^{p-1} g_a g_{-a} = \sum_{k=0}^{p-1} \sum_{\ell=0}^{p-1} \left(\frac{k}{p}\right)\left(\frac{\ell}{p}\right) \sum_{a=0}^{p-1} \zeta_p^{a(k-\ell)}.

由 Lemma 1，内层和仅当 $k=\ell$ 时非零（值为 $p$ ）。故

\sum_{a=0}^{p-1} g_a g_{-a} = p \sum_{k=0}^{p-1} \left(\frac{k}{p}\right)^2 = p(p-1).

比较两种算法：

\left(\frac{-1}{p}\right)(p-1) g^2 = p(p-1).

约去 $p-1$ ，并注意 $\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$ （Euler 判别法），得 $g^2 = p^*$ 。 $\square$

Gauss 的证明

在分圆整数环

\mathbb{Z}[\zeta_p] := \left\{ a_0 + a_1 \zeta_p + \cdots + a_{p-2} \zeta_p^{p-2} \;\middle|\; a_i \in \mathbb{Z} \right\}

中考虑同余。注意对任意 $x, y \in \mathbb{Z}[\zeta_p]$ ，有 $(x+y)^q \equiv x^q + y^q \pmod{q}$ ，这是因为二项式系数 $\binom{q}{j}\ (0 < j < q)$ 均被 $q$ 整除。

一方面，利用 Proposition (2)：

g^q = (g^2)^{\frac{q-1}{2}} g = (p^*)^{\frac{q-1}{2}} g \equiv \left(\frac{p^*}{q}\right) g \pmod{q},

其中最后一步使用了 Euler 判别法（在 $\mathbb{Z}[\zeta_p]$ 中模 $q$ ）。

另一方面，由上述 “freshman’s dream” 性质：

g^q = \left( \sum_{k=0}^{p-1} \left(\frac{k}{p}\right) \zeta_p^k \right)^q \equiv \sum_{k=0}^{p-1} \left(\frac{k}{p}\right)^q \zeta_p^{qk} \pmod{q}.

注意 $\left(\frac{k}{p}\right) = \pm 1$ ， $q$ 为奇数，故 $\left(\frac{k}{p}\right)^q = \left(\frac{k}{p}\right)$ 。于是

g^q \equiv \sum_{k=0}^{p-1} \left(\frac{k}{p}\right) \zeta_p^{qk} = g_q \pmod{q}.

由 Proposition (1)， $g_q = \left(\frac{q}{p}\right) g$ 。结合两式：

\left(\frac{p^*}{q}\right) g \equiv \left(\frac{q}{p}\right) g \pmod{q}.

两边同乘 $g$ ，利用 $g^2 = p^*$ ：

\left(\frac{p^*}{q}\right) p^* \equiv \left(\frac{q}{p}\right) p^* \pmod{q}.

注意上式中的同余实则是在 $\mathbb{Z}$ 中进行的——这里用到了 $\mathbb{Q} \cap \mathbb{Z}[\zeta_p] = \mathbb{Z}$ 。在等式两边约去 $p^*$ （注意 $p^* = \pm p$ 与 $q$ 互素），得到

\left(\frac{p^*}{q}\right) \equiv \left(\frac{q}{p}\right) \pmod{q}.

两边都是 $\pm 1$ ，而 $q > 2$ ，故模 $q$ 同余推出相等：

\left(\frac{p^*}{q}\right) = \left(\frac{q}{p}\right).

将 $p^* = (-1)^{\frac{p-1}{2}}p$ 代入左边：

\left(\frac{(-1)^{\frac{p-1}{2}}p}{q}\right) = \left(\frac{-1}{q}\right)^{\frac{p-1}{2}} \left(\frac{p}{q}\right) = (-1)^{\frac{q-1}{2} \cdot \frac{p-1}{2}} \left(\frac{p}{q}\right) = \left(\frac{q}{p}\right).

移项即得二次互反律。 $\square$

注记. 证明中用到的事实 $\mathbb{Q} \cap \mathbb{Z}[\zeta_p] = \mathbb{Z}$ 需要验证。其直观含义是：一个分圆整数若同时是有理数，则必为普通整数。可以由 $\mathbb{Z}[\zeta_p]$ 的整性（integrality）和 $\mathbb{Z}$ 的整闭性推出。