二次互反律的證明

這個條目給出了二次互反律的證明。

二次互反律的敘述

對於兩個奇素數$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}}$。