二次互反律的证明

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

二次互反律的叙述

对于两个奇素数${\displaystyle p,q}$ ，${\displaystyle \left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}}$ 。^[1]其中，${\displaystyle \left({\frac {p}{q}}\right)}$ 是勒让德符号。

证明一

设${\displaystyle p}$ 是一个奇素数并且${\displaystyle a\not \equiv 0\mod p}$ 。对于每个${\displaystyle k=1,2,...,{\frac {p-1}{2}}}$ ，这样定义${\displaystyle \epsilon _{k}}$ 和${\displaystyle r_{k}}$ ：

${\displaystyle ak\equiv \epsilon _{k}r_{k}\mod p}$ ，其中${\displaystyle 0<r_{k}<{\frac {p}{2}}}$ ，${\displaystyle \epsilon _{k}=\pm 1}$ 。通过分别考虑${\displaystyle \epsilon _{k}=1}$ 和${\displaystyle \epsilon _{k}=-1}$ 的情况，易证每个${\displaystyle r_{k}}$ 都两两不等。

现在考虑${\displaystyle \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}$ 。因为每个${\displaystyle r_{k}}$ 都两两不等，所以${\displaystyle \{r_{1},r_{2},...,r_{\frac {p-1}{2}}\}}$ 就是${\displaystyle \{1,2,...,{\frac {p-1}{2}}\}}$ 的一个重排列。所以我们得到${\displaystyle 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}$ ，因此${\displaystyle a^{\frac {p-1}{2}}\equiv \prod _{k=1}^{(p-1)/2}\epsilon _{k}\mod p}$ 。

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

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

如果${\displaystyle a}$ 是奇数，同时考虑勒让德符号的性质${\displaystyle \left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)=\left({\frac {ab}{p}}\right)}$ ，可知${\displaystyle \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}}}$ ，其中最后一步利用了等差数列的求和公式。

但是，当${\displaystyle a=1}$ 时，由上式可得${\displaystyle \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}}}$ ，所以${\displaystyle \left({\frac {a}{p}}\right)=(-1)^{\sum _{k=1}^{(p-1)/2}\lfloor {\frac {ak}{p}}\rfloor }}$ 。

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

所以${\displaystyle \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 }}}$ 。

 

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

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

参考文献

1. 高斯二次互反律. [2019-12-08]. （原始内容于2019-12-08）.