二次剩余

它把一个存在性问题(是否存在 $x$ 使其平方为 $a$)转化为一次模幂运算,正是这一点使勒让德符号既可计算又具有积性。

由于 $(\mathbb{Z}/p\mathbb{Z})^{*}$ 是阶为 $p-1$ 的循环群(素数模下的标准事实),固定一个原根 $g$,写 $a \equiv g^k \pmod p$,其中 $0 \le k \le p-2$。模 $p$ 的二次剩余恰好是 $g$ 的偶数次幂:若 $a=g^{2m}$,则 $x=g^m$ 满足 $x^2\equiv a$;反之每个平方 $x^2=(g^j)^2=g^{2j}$ 都是偶数次幂。因此 $a$ 是二次剩余当且仅当 $k$ 为偶数。

现在计算 $a^{(p-1)/2} \equiv g^{k(p-1)/2} \pmod p$。若 $k$ 为偶数,记 $k=2m$,由费马小定理得 $g^{k(p-1)/2}=g^{m(p-1)}=(g^{p-1})^m\equiv 1^m=1\pmod p$,与剩余情形吻合。

若 $k$ 为奇数,则 $g^{k(p-1)/2}$ 是 $g^{k(p-1)}=(g^{p-1})^k\equiv 1\pmod p$ 的平方根,故 $a^{(p-1)/2}\equiv \pm 1$。它不能等于 $1$:否则 $g$ 的阶必须整除 $k(p-1)/2$,但 $\operatorname{ord}(g)=p-1$ 且 $k$ 为奇数意味着除非 $(p-1)/2$ 本身已是倍数,否则 $k(p-1)/2$ 不是 $p-1$ 的倍数,这与 $g$ 是阶恰为 $p-1$ 的原根矛盾。所以恰好当 $k$ 为奇数即 $a$ 为非剩余时,$a^{(p-1)/2}\equiv -1\pmod p$。

综合两种情形:$a^{(p-1)/2}\equiv 1\pmod p$ 当且仅当 $a$ 是二次剩余,否则 $\equiv -1$,这正是 $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$ 的断言。

它说明 $p$ 是否为模 $q$ 的平方数,与 $q$ 是否为模 $p$ 的平方数,其实是“同一个”问题,差别仅在于一个只依赖 $p,q$ 模 $4$ 的符号——把一个看似困难的双变量问题变成一条规则。

我们借助高斯引理作为垫脚石:对奇素数 $p$ 及 $\gcd(a,p)=1$,考察 $a, 2a, \dots, \frac{p-1}{2}a$ 模 $p$ 的最小正剩余,设其中超过 $p/2$ 的个数为 $\mu$。高斯引理断言 $\left(\dfrac{a}{p}\right)=(-1)^{\mu}$;这可由将每个这样的“大”剩余 $r$ 与 $p-r\le p/2$ 配对、并以两种方式相乘这 $\frac{p-1}{2}$ 个数时追踪符号得到。

艾森斯坦的精细化把 $\mu$ 表示为格点计数:当 $a=q$ 为奇数时,通过比较 $\lfloor kq/p\rfloor$(小于 $kq$ 的 $p$ 的倍数个数)与 $kq \bmod p$ 距 $p/2$ 的远近,可证明 $\mu \equiv \sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor \pmod 2$。将同样的计数论证对称地应用,得到 $\left(\frac{q}{p}\right)=(-1)^{S(q,p)}$ 与 $\left(\frac{p}{q}\right)=(-1)^{S(p,q)}$,其中 $S(q,p)=\sum_{k=1}^{(p-1)/2}\left\lfloor \frac{kq}{p}\right\rfloor$,$S(p,q)=\sum_{k=1}^{(q-1)/2}\left\lfloor \frac{kp}{q}\right\rfloor$。

从几何上看,$S(q,p)+S(p,q)$ 统计满足 $1\le x\le \frac{p-1}{2}$、$1\le y\le \frac{q-1}{2}$ 且严格位于直线 $qx=py$ 下方的格点 $(x,y)$(共 $S(q,p)$ 个),加上严格位于其上方的格点(由 $p,q$ 的对称角色,共 $S(p,q)$ 个)。由于 $\gcd(p,q)=1$ 且 $x<p$,没有格点恰好落在该直线上,故这两个计数合起来恰好覆盖整个 $\frac{p-1}{2}\cdot\frac{q-1}{2}$ 个格点的矩形。

因此 $S(q,p)+S(p,q) = \frac{p-1}{2}\cdot\frac{q-1}{2}$,将两个勒让德符号公式相乘得到 $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{S(p,q)+S(q,p)}=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$,这正是 $\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$。