二次互反律的證明

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

二次互反律的敘述

對於兩個奇素數${\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）.