二次互反律的证明

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

二次互反律的叙述

对于两个奇素数$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 \equiv 0\mod p$。对于每个$k=1,2,...,{\frac {p-1}{2}}$，这样定义$\epsilon _{k}$和$r_{k}$：

$ak\equiv \epsilon _{k}r_{k}\mod p$，其中$0<r_{k}<{\frac {p}{2}}$，$\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 _{k}r_{k}\mod p$等价于$ak=\epsilon _{k}r_{k}+bp,b\in \mathbb {Z}$。若$\epsilon _{k}=1$，则有$ak=r_{k}+bp$。注意到$0<r_{k}<{\frac {p}{2}}$，将等式两边同时乘2得到$2ak=R_{k}+B_{k}p$，其中$R_{k}=2r_{k},0<R_{k}<p,B_{k}=2b$，可以发现$B_{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$是奇数。据此，可以知道$\operatorname {sgn}(r_{k})=\lfloor {\frac {2ak}{p}}\rfloor$，其中$\operatorname {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}}$。