二次互反律

二次互反律常用勒让德符号表述：对于两个奇素数 p 和 q， (p/q)· (q/p)=(-1)^(((p-1)(q-1))/4)

其中 (p/q) 是勒让德符号。但是对于更一般的雅可比符号和希尔伯特符号也有对应的二次互反律。

欧拉和勒让德都曾经提出过二次互反律的猜想。但第一个严格的证明是由高斯在1796年作出的，随后他又发现了另外七个不同的证明。在《算数研究》一书和相关论文中，高斯将其称为“基石”：

这个定理肯定属于最优雅的基本定理。(Art. 151)

私下里高斯把二次互反律誉为算术理论中的宝石，是一个黄金定律。

高斯之后雅可比、柯西、刘维尔、克罗内克、弗洛贝尼乌斯等也相继给出了新的证明。至今，二次互反律已有超过200个不同的的证明。二次互反律可以推广到更高次的情况，如三次互反律等等。

几个简单情况

有了上节的关于乘积的性质，可以发现：研究一个合数是否是模某个质数 p 的剩余，只需将这个合数进行质因数分解，研究其每个质因数是不是模 p 的剩余即可。因此，为了寻找模质数的二次剩余的规律，可以先研究对于前几个质数2、3、5等的情况，看对于什么样的质数 p，2、3、5等是模它们的剩余。此外为了研究正负号对乘积的影响，也要研究-1的情况。为了发现规律，可以借助50以内的质数的二次剩余表。

50以内的质数的二次剩余表

例如，要检查7是不是模37的剩余，可以查看7是否出现在模37的一行中。实际上7出现在左数第9个格子里，因此7是模37的二次剩余。

又如，要检查7是不是模43的剩余，可以查看7是否出现在模43的一行中。实际上并没有7出现，因此7是模43的二次非剩余。

又如，要检查7是不是模41的剩余，可以查看7是否出现在模41的一行中。实际上并没有7出现，因此7是模41的二次非剩余。

又如，要检查18是不是模47的剩余，可以查看18是否出现在模47的一行中。实际上并没有18出现，但是注意了，当 n=21 时，（公式略），因此18是模47的二次剩余(如要判断质数 p≠ 2，至少须写到 (p-1)/2)。

–1的情况

首先，看看对于什么样的质数，–1是模它的二次剩余。查对上表后可以发现：–1对于模 5,13,17,29,37 是二次剩余，而对 3,7,11,19,23,31,43 则不是。比如：（公式略），（公式略），（公式略），等等。

可以发现前者都是模4余1的质数，后者都是模4余3的质数。于是可以猜想：

同余方程（公式略）有解当且仅当（公式略）。

2的情况

接下来看对什么样的质数，2是模它的二次剩余。同样查对上表后可以发现：对于模8余±1的质数，如 7,17,23,31,41,47，2是模它的二次剩余。对于模8余±3的质数如 3,5,11,13,19,29,37 等则不然。

3的情况

3是模11、13、23、37和47的剩余，但不是模5、7、17、19、29、31、41或43的剩余。

前者模12都余±1，后者都模12余±5。

–3是模7、13、19、31、37和43的剩余，但不是模5、11、17、23、29、41或47的剩余，前者模3都余1，后者模3都余2。

由于模3的剩余只有1，可以发现一个规律：对于所有为模3的剩余的质数，-3是模它的剩余。

5的情况

5是模11、19、29、31和41的剩余，但不是模3、7、13、17、23、37、43或47的剩余，前者模5都余±1，后者模5都余±2。

由于模5的剩余只有±1，可以发现规律：对于所有为模5的剩余的质数，5是模它的剩余。

6的情况

6是模5、19、23、29、43和47的剩余，但不是模7、11、13、17、31、37或41的剩余，前者模24都余±1或±5，后者模24都余±7或±11。

7的情况

7是模3、19、29、31、37和47的剩余，但不是模5、11、13、17、23、41或43的剩余，前者模28都余±1、±3或±9，后者模28都余±5、±11或±13。

–7是模2、11、23、29、37和43的剩余，但不是模3、5、13、17、19、31、41或47的剩余，前者模7都余1、2、4，后者模7都余3、5、6。

由于模7的剩余只有1、2或4，可以发现一个规律：对于所有为模7的剩余的质数，-7是模它的剩余。

n2+n+2 的因数

不难发现 n²+n+2，在 n 是整数的情况，只能被模7二次剩余的质数整除，不可能被模7二次非剩余的质数整除，因为 b²-4ac=-7，所以只能被模7二次剩余的质数整除。

对于2、7、11、23、29、37、43、53、67、71、79、107、109、113、127、137等质数都是模7的二次剩余。（OEIS数列A045373）

对于3、5、13、17、19、31、41、47、59、61、73、83、89、97、101、103、131、139等质数都是模7的二次非剩余。（OEIS数列A003625）

高斯和勒让德的叙述

对于一般的情况，也有类似的规律。在此基础上，高斯和勒让德提出了两个一般性的叙述（没有使用勒让德符号），两者是等价的。

高斯的叙述

如果（公式略）那么（公式略）可解当且仅当（公式略）可解。

借助于以下变量： q^(*)=(-1)^((q-1)/2)q，命题可以简化为：（公式略）可解当且仅当（公式略）可解。

下表列明了质数之间相互是否为二次剩余的情况。方格内为R表示对应的 q （横列元素）为对应的 p （竖列元素）的二次剩余，N则表示相反情况（此表示法由高斯创造）。可以看到白格内的元素是关于对角线对称的，黄格内则关于对角线反对称。可以说黄格代表了一种“特殊情况”。

勒让德的叙述

观察上表中黄格的情况，可以看出相对应的两个质数都是模4余3的。因此勒让德的陈述为：

如果（公式略）或者（公式略）那么（公式略）可解当且仅当（公式略）可解。

如果（公式略）那么（公式略）可解当且仅当（公式略）不可解。

研究历史

二次互反律曾被不少的数学家研究，因此二次互反律的叙述有很多种。要注意的是当时的数学记号并不统一。欧拉和勒让德并没有高斯的同余记号，高斯也不知道勒让德符号。 p 和 q 总是不相等的正奇质数。

前期探索

费马曾经证明了（或声称证明了）一系列关于将质数表示成平方和的定理 p=x²+ y² 当且仅当 p=2 或（公式略）

p=x²+2y² 当且仅当 p=2 或（公式略）

p=x²+3y² 当且仅当 p=3 或（公式略）

他并没有给出二次互反律的陈述，尽管由此类的定理可以得到–1、±2和±3的情况。

此外欧拉曾经猜想（后被勒让德证明）：

如果（公式略）那么 p=x²+5y²

如果（公式略）那么 pq=x²+5y².

证明费马的这类命题是导致二次互反律的发现的因素之一。

定理的首次叙述：欧拉

欧拉在1783年曾经写过（以现今的符号表示）：

1) 如果（公式略）那么 q 是模 p 的二次剩余当且仅当（公式略），其中 r 是一个模 q 的二次剩余。

2) 如果（公式略）那么 q 是模 p 的二次剩余当且仅当（公式略）, 其中 b 为奇数但不被 q 整除。

这是二次互反律首次被完整地陈述。欧拉也证明了 2的情况。

勒让德与他的符号

勒让德用 a 和 A 表示模4余1的正质数，用 b 和 B 表示模4余3的正质数。他建立了一个有8个定理的表格，这8个定理合起来就是二次互反律。

勒让德认为表达式（公式略）出现了太多次，可以简写为：（公式略）

其中 N、 c 为互质的数。

这个符号就是现在使用的勒让德符号：

对于所有的整数 a 以及任意奇质数 p：

勒让德使用勒让德符号的叙述为： (p/q)=(q/p)，如果（公式略）或（公式略）

( (p/q)=-(q/p)，如果（公式略）

他也提到上面的两种情况可以合并为： (p/q)(q/p)=(-1)^(((p-1)(q-1))/4)

勒让德完整地证明了八种情况中的第一、第二和第七种。在证明第八种情况时，勒让德作了一个可以等价于狄利克雷定理的假设。正如高斯在其《算术研究》中指出的。勒让德实际上证明了二次互反律是狄利克雷定理成立的情况下的一个推论。

首次的证明：高斯

第一个完整地给出二次互反律的证明的人是德国数学家高斯。高斯在1796年给出了二次互反律的第一个证明。高斯首先证明了 -1和2的情况。作为进行数学归纳法的开始，他证明了±3和±5的情况。他注意到-3和+5的情况较有规律，容易叙述，因此把定理叙述为： p 是形式为 4n+1，那么 p （如果 p 是形式为 4n+3 那么 -p）是模每个为模 p 的二次剩余（非剩余）的质数的二次剩余（非剩余）。

在下一句中，高斯将其列为“基本定理”（但没有用到“互反律”的称谓）。

在引进 a R b （ a N b）表示 a 是模 b 的二次剩余（非剩余）后，高斯令 a 和 a^(′) 表示模4余1的质数，用 b 和 b^(′) 表示模4余3的，于是写出了勒让德得到的8种情况：

在接下来的文章中他将其推广到关于所谓的雅可比符号，以下的大写字母表示的意思和相应的小写字母一样，但不再是质数。

最后他分各种情况分别运用强数学归纳法将其证明。

证明中高斯用到了一个引理：

如果（公式略）是质数，那么存在奇质数 q<2√p+1 使得 (p/q)=-1

如果使用勒让德符号，那么高斯的陈述就是

令 q^(*)=(-1)^((q-1)/2)q，也就是说 |q^(*)|=|q| 且（公式略）。

那么（公式略）

高斯一生中给出了二次互反律的八个证明，其中他最为满意的是第五个证明。