二次互反律的证明

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

二次互反律的叙述

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

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

现在考虑$\prod _{k=1}^{(p-1)/2}ak\equiv \prod _{k=1}^{(p-1)/2}{ϵ}_k\prod _{k=1}^{(p-1)/2}{r}_{k}modp$。因为每个$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}{ϵ}_k\prod _{k=1}^{(p-1)/2}kmodp$，因此$a^{\frac{p-1}{2}}\equiv \prod _{k=1}^{(p-1)/2}{ϵ}_{k}modp$。

现在考虑${ϵ}_k$的正负情况。$ak\equiv {ϵ}_k{r}_{k}modp$等价于$ak={ϵ}_k{r}_k+bp,b\in \mathbb{Z}$。若${ϵ}_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$也是偶数。同理可证若${ϵ}_k=-1$，$B_k=2b+1$，而$\lfloor \frac{2ak}{p}\rfloor$是奇数。据此，可以知道$\mathrm{sgn}(r_k)=\lfloor \frac{2ak}{p}\rfloor$，其中$\mathrm{sgn}(r_k)$是$r_k$的符号，也就是${ϵ}_k=1$还是${ϵ}_k=-1$。

所以$a^{\frac{p-1}{2}}\equiv (-1{)}^{\sum _{k=1}^{(p-1)/2}\lfloor 2ak/p\rfloor }modp$。又由欧拉准则知$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}modp$，所以$\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}}$。