查看“︁二次互反律的证明”︁的源代码

{{Multiple issues|
{{Expert|subject=数学|time=2019-12-07T08:58:44+00:00}}
{{refimprove|time=2019-12-08}}}}
这个条目给出了[[二次互反律]]的证明。

== 二次互反律的叙述 ==
对于两个奇[[素数]]<math>p,q</math>，<math>\left( \frac{p}{q} \right) \cdot \left( \frac{q}{p} \right) = (-1)^{\frac{ (p-1)(q-1) }{4} }</math>。<ref>{{Cite web|title=高斯二次互反律|url=http://www.math.ntu.edu.tw/~msa/act/mathcamp/95page/lecture/K.doc|accessdate=2019-12-08|author=|date=|format=|publisher=|language=|archive-date=2019-12-08|archive-url=https://web.archive.org/web/20191208044908/http://www.math.ntu.edu.tw/~msa/act/mathcamp/95page/lecture/K.doc|dead-url=no}}</ref>其中，<math>\left( \frac{p}{q} \right)</math>是[[勒让德符号]]。

== 证明一 ==
设<math>p</math>是一个奇素数并且<math>a\not\equiv0\mod p</math>。对于每个<math>k=1,2,...,\frac{p-1}{2}</math>，这样定义<math>\epsilon_k</math>和<math>r_k</math>：

<math>ak\equiv \epsilon_kr_k\mod p</math>，其中<math>0<r_k<\frac{p}{2}</math>，<math>\epsilon_k=\pm 1</math>。通过分别考虑<math>\epsilon_k=1</math>和<math>\epsilon_k=-1</math>的情况，易证每个<math>r_k</math>都两两不等。

现在考虑<math>\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</math>。因为每个<math>r_k</math>都两两不等，所以<math>\{r_1,r_2,...,r_{\frac{p-1}{2}}\}</math>就是<math>\{1,2,...,\frac{p-1}{2}\}</math>的一个重排列。所以我们得到<math>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</math>，因此<math>a^{\frac{p-1}{2}}\equiv\prod_{k=1}^{(p-1)/2}\epsilon_k\mod p </math>。

现在考虑<math>\epsilon_k </math>的正负情况。<math>ak\equiv \epsilon_kr_k\mod p</math>等价于<math>ak=\epsilon_kr_k+bp,b\in\mathbb{Z} </math>。若<math>\epsilon_k=1</math>，则有<math>ak=r_k+bp </math>。注意到<math>0<r_k<\frac{p}{2}</math>，将等式两边同时乘2得到<math>2ak=R_k+B_kp </math>，其中<math>R_k=2r_k,0<R_k<p,B_k=2b </math>，可以发现<math>B_k </math>是偶数，而<math>\lfloor \frac{2ak}{p}\rfloor=\lfloor \frac{R_k}{p}+B_k\rfloor=B_k </math>也是偶数。同理可证若<math>\epsilon_k=-1</math>，<math>B_k=2b+1 </math>，而<math>\lfloor \frac{2ak}{p}\rfloor </math>是奇数。据此，可以知道<math>\sgn(r_k)=\lfloor \frac{2ak}{p}\rfloor</math>，其中<math>\sgn(r_k)</math>是<math>r_k</math>的符号，也就是<math>\epsilon_k=1</math>还是<math>\epsilon_k=-1</math>。

所以<math>a^{\frac{p-1}{2}}\equiv(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor 2ak/p\rfloor}\mod p </math>。又由[[欧拉准则]]知<math>\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\mod p </math>，所以<math>\left(\frac{a}{p}\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor 2ak/p\rfloor}</math>。

如果<math>a </math>是奇数，同时考虑勒让德符号的性质<math>\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right) </math>，可知<math>\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}}</math>，其中最后一步利用了[[等差数列]]的求和公式。

但是，当<math>a=1</math>时，由上式可得<math>\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}}</math>，所以<math>\left(\frac{a}{p}\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor \frac{ak}{p}\rfloor}</math>。

现在令<math>p</math>和<math>q</math>为奇素数，可得<math>\left(\frac{q}{p}\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor \frac{qk}{p}\rfloor}</math>以及<math>\left(\frac{p}{q}\right)=(-1)^{\sum_{l=1}^{(q-1)/2}\lfloor \frac{pl}{q}\rfloor}</math>，

所以<math>\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}}</math>。
[[File:二次互反律的证明.png|缩略图]]
现在考虑右边这幅图：设<math>A=\sum_{l=1}^{(q-1)/2}\lfloor \frac{pl}{q}\rfloor,B=\sum_{k=1}^{(p-1)/2}\lfloor \frac{qk}{p}\rfloor</math>，则<math>A</math>代表了三角形A中的格点个数，<math>B</math>代表了三角形B中的格点个数。它们加在一起等于整个<math>p\times q</math>长方形的格点个数的四分之一。需要注意的是由于<math>p,q</math>互素，所以对角线上不可能有格点。

由于整个长方形的格点个数是<math>(p-1)(q-1)</math>，所以<math>A+B=\frac{(p-1)(q-1)}{4}</math>，即得<math>\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^\frac{(p-1)(q-1)}{4}</math>。<br />

== 参考文献 ==
<references />