二次互反律的证明

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

## 二次互反律的敘述

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

## 參考文獻