数学天书中的证明：二次互反律

NaCly_Fish · 2022-10-20 23:01:27 · 个人记录

正文之前，先说明一下 Legendre 符号 \left( \dfrac ap\right)：对于 a \not \equiv 0 \pmod p，若 a 为模 p 的二次剩余，定义其值为 1，否则为 -1。对此有一个欧拉判别准则：

利用费马小定理就很容易证明，这里就直接跳过了。

然后就是我们这次的主题，二次互反律：

其中 p,q 为不相同的奇素数。

作为数论中基础且非常重要的定理，它也有很多种证明方式（据说有 196 种）。可惜这个定理在 OI 中应用太少，所以普及度并不高。

最近又去看了看那本《Proofs from THE BOOK》，看到了一个很初等也很神秘的证明，就来复述一下。

为了证明二次互反律，我们先证明一个高斯引理（许多证明也都用到了这个引理）。若 a\not \equiv 0 \pmod p，对于 i=1,2,\cdots,\frac{p-1}{2} 取绝对值最小的 r_i 使得 ia \equiv r_i \pmod p，则

其中 s 为小于零的 r_i 个数。

设 u_i 表示第 i 个（如何排序不重要）小于零的剩余，同理设 v_i。我们首先要证明对于任意 i,j，-u_i \neq v_j：先假设存在一组情况相等，令 u_i\equiv ka \pmod p，v_j \equiv la \pmod p，则 (k+l)a \equiv 0 \pmod p，而 k+l<p，这样就矛盾了。

有了刚才的证明，就可以得到所有 -u_i 和 v_j 组成的集合，就是 \{ 1,2,\cdots,\frac{p-1}{2}\}（因为各 ia \bmod p 是互异的）。所以：

从另一个角度，即 r_i \equiv ia \pmod p：

两边消掉阶乘之后，根据欧拉判别准则，就证明了高斯引理。

铺垫了前面这么多，终于 要 来 了！最后的证明很简单，我们来数格点就可以。

比如对于 \left( \dfrac qp\right)，在高斯定理中的 s 实际上就是满足如下条件的整数对 x,y 的个数：

第一个条件很容易理解，是取 q 的倍数时限定的范围；第二个条件是相对于第一个设定的，它保证每个 x 至多只有一个对应的 y；最后一个条件限定 qx-py 是小于零、且绝对值最小的与 qx 在模 p 下同余的整数。

求整数解个数，就与数格点联系起来了。相应地考虑 \left( \dfrac pq \right)，限制条件为：

下图展现了 p=17，q=11 的情况： （图片为自制，可能看起来有一点误差，不过实际验证的话，格点是在所求范围内的）

图中蓝色的点有 5 个，即 \left( \dfrac qp\right)=(-1)^5；同理可得 \left( \dfrac pq\right) = (-1)^3。

由于这三条斜线段上必然没有整点（对于中间那条，可以根据 p,q 均为素数来求 py=qx 的整数解来证明；对于边上的两条，py-qx 是整数，而 \frac p2 和 \frac q2 均不是），根据高斯引理计数的整点，都在斜线段之间。

那么记上半区域的整点数（蓝色节点）为 s，另一部分为 t。可以发现：二次互反律成立，当且仅当 R、S 两个区域的整点数相等。考虑总的整点数，而 R、S 中整点数相等的话，s+t 就与 \frac{p-1}{2}\frac{q-1}{2} 有相同的奇偶性；那么反过来也是一样的。

现在只需要对 R、S 中的整点建立双射，把 R 中的点 (x,y) 映射到 (\frac{p+1}{2}-x,\frac{q+1}{2}-y)，可以验证这是成立的，不会把点映射到斜线段内的区域。

所以：

证毕！