二次互反律的证明

这个条目给出了二次互反律的证明。

二次互反律的叙述
对于两个奇素数p,q，\left( \frac{p}{q} \right) \cdot \left( \frac{q}{p} \right) = (-1)^{\frac{ (p-1)(q-1) }{4} }。其中，\left( \frac{p}{q} \right)是勒让德符号。

证明一
设p是一个奇素数并且a\not\equiv0\mod p。对于每个k=1,2,...,\frac{p-1}{2}，这样定义\epsilon_k和r_k：

ak\equiv \epsilon_kr_k\mod p，其中0，\epsilon_k=\pm 1。通过分别考虑\epsilon_k=1和\epsilon_k=-1的情况，易证每个r_k都两两不等。

现在考虑\prod_{k=1}^{(p-1)/2}ak\equiv \prod_{k=1}^{(p-1)/2}\epsilon_k\prod_{k=1}^{(p-1)/2}r_k\mod p。因为每个r_k都两两不等，所以\{r_1,r_2,...,r_{\frac{p-1}{2}}\}就是\{1,2,...,\frac{p-1}{2}\}的一个重排列。所以我们得到a^{\frac{p-1}{2}}\prod_{k=1}^{(p-1)/2}k\equiv \prod_{k=1}^{(p-1)/2}\epsilon_k\prod_{k=1}^{(p-1)/2}k\mod p，因此a^{\frac{p-1}{2}}\equiv\prod_{k=1}^{(p-1)/2}\epsilon_k\mod p 。

现在考虑\epsilon_k 的正负情况。ak\equiv \epsilon_kr_k\mod p等价于ak=\epsilon_kr_k+bp,b\in\mathbb{Z} 。若\epsilon_k=1，则有ak=r_k+bp 。注意到0，将等式两边同时乘2得到2ak=R_k+B_kp ，其中R_k=2r_k,0B_k 是偶数，而\lfloor \frac{2ak}{p}\rfloor=\lfloor \frac{R_k}{p}+B_k\rfloor=B_k 也是偶数。同理可证若\epsilon_k=-1，B_k=2b+1 ，而\lfloor \frac{2ak}{p}\rfloor 是奇数。据此，可以知道\sgn(r_k)=\lfloor \frac{2ak}{p}\rfloor，其中\sgn(r_k)是r_k的符号，也就是\epsilon_k=1还是\epsilon_k=-1。

所以a^{\frac{p-1}{2}}\equiv(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor 2ak/p\rfloor}\mod p 。又由欧拉准则知\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\mod p ，所以\left(\frac{a}{p}\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor 2ak/p\rfloor}。

如果a 是奇数，同时考虑勒让德符号的性质\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right) ，可知\left(\frac{a}{p}\right)\left(\frac{2}{p}\right)=\left(\frac{2a+2p}{p}\right)=\left(\frac{4\left(\frac{a+p}{2}\right)}{p}\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor \frac{2\left(\frac{a+p}{2}\right)k}{p}\rfloor}=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor \frac{ak}{p}\rfloor}(-1)^{\sum_{k=1}^{(p-1)/2}k}=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor \frac{ak}{p}\rfloor}(-1)^{\frac{p^2-1}{8}}，其中最后一步利用了等差数列的求和公式。

但是，当a=1时，由上式可得\left(\frac{2}{p}\right)=\left(\frac{1}{p}\right)\left(\frac{2}{p}\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor \frac{k}{p}\rfloor}(-1)^{\frac{p^2-1}{8}}=(-1)^{\frac{p^2-1}{8}}，所以\left(\frac{a}{p}\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor \frac{ak}{p}\rfloor}。

现在令p和q为奇素数，可得\left(\frac{q}{p}\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor \frac{qk}{p}\rfloor}以及\left(\frac{p}{q}\right)=(-1)^{\sum_{l=1}^{(q-1)/2}\lfloor \frac{pl}{q}\rfloor}，

所以\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor \frac{qk}{p}\rfloor+{\sum_{l=1}^{(q-1)/2}\lfloor \frac{pl}{q}\rfloor}}。

现在考虑右边这幅图：设A=\sum_{l=1}^{(q-1)/2}\lfloor \frac{pl}{q}\rfloor,B=\sum_{k=1}^{(p-1)/2}\lfloor \frac{qk}{p}\rfloor，则A代表了三角形A中的格点个数，B代表了三角形B中的格点个数。它们加在一起等于整个p\times q长方形的格点个数的四分之一。需要注意的是由于p,q互素，所以对角线上不可能有格点。

由于整个长方形的格点个数是(p-1)(q-1)，所以A+B=\frac{(p-1)(q-1)}{4}，即得\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^\frac{(p-1)(q-1)}{4}。

参考文献