二次互反律

一个整数 ${\displaystyle a}$  是模整数 ${\displaystyle n}$  的二次剩余，是指它与某个整数的平方关于模${\displaystyle n}$  同余。直观来说，是指二次同余方程${\displaystyle x^{2}\equiv a{\pmod {n}}}$ 有整数解。如果这样的整数解不存在，则称 ${\displaystyle a}$  是模整数 ${\displaystyle n}$  的二次非剩余。术语中的“二次”一词是为了表示与平方同余，在不至于混淆的行文中，可以略掉。当模数是质数时，通常将0的情况区别讨论，因此有：

1. 在模为质数时，二次剩余与二次非剩余的个数是相等的。
2. 在模为质数时，剩余与剩余、非剩余与非剩余的乘积都是剩余，剩余与非剩余的乘积是非剩余。

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

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

下表列出了1至20模50以内的质数的二次剩余。其中每一行列出了模相应质数的所有剩余。因此要看某个整数 ${\displaystyle k}$  是否是模某个质数 ${\displaystyle p}$  的剩余，只需要看 ${\displaystyle k}$  是否在模 ${\displaystyle p}$  的那一行中出现就行了。

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

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

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

–1的情况

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

${\displaystyle -1\equiv 2{\pmod {3}}}$ ，${\displaystyle -1\equiv 4{\pmod {5}}}$ ，${\displaystyle -1\equiv 10{\pmod {11}}}$ ，等等。

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

同余方程${\displaystyle x^{2}\equiv -1{\pmod {p}}}$  有解当且仅当 ${\displaystyle p\equiv 1{\pmod {4}}}$ 。

2的情况

接下来看对什么样的质数，2是模它的二次剩余。同样查对上表后可以发现：对于模8余±1的质数，如${\displaystyle 7,17,23,31,41,47}$ ，2是模它的二次剩余。对于模8余±3的质数如${\displaystyle 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是模它的剩余。

${\displaystyle n^{2}+n+2}$ 的因数

不难发现${\displaystyle n^{2}+n+2}$ ，在${\displaystyle n}$ 是整数的情况，只能被模7二次剩余的质数整除，不可能被模7二次非剩余的质数整除，因为${\displaystyle b^{2}-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）

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

高斯的叙述

如果${\displaystyle q\equiv 1{\pmod {4}}}$  那么 ${\displaystyle x^{2}\equiv p{\pmod {q}}}$  可解当且仅当${\displaystyle x^{2}\equiv q{\pmod {p}}}$ 可解。

如果${\displaystyle q\equiv 3{\pmod {4}}}$  那么 ${\displaystyle x^{2}\equiv p{\pmod {q}}}$  可解当且仅当${\displaystyle x^{2}\equiv -q{\pmod {p}}}$ 可解。 借助于以下变量：${\displaystyle q^{*}=(-1)^{\frac {q-1}{2}}q}$ ，命题可以简化为：

${\displaystyle x^{2}\equiv p{\pmod {q}}}$ 可解当且仅当${\displaystyle x^{2}\equiv q^{*}{\pmod {p}}}$ 可解。

在高斯的叙述中已经可以见到“互反”的体现，即将${\displaystyle x^{2}\equiv p{\pmod {q}}}$  的可解性与${\displaystyle x^{2}\equiv q{\pmod {p}}}$ 的可解性联系起来。在下表中可以看出，这表现了一种对称性（反对称性）。

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

勒让德的叙述

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

如果${\displaystyle p\equiv 1{\pmod {4}}}$  或者 ${\displaystyle q\equiv 1{\pmod {4}}}$  那么

${\displaystyle x^{2}\equiv q{\pmod {p}}x^{2}}$  可解当且仅当 ${\displaystyle x^{2}\equiv p{\pmod {q}}}$  可解。

如果${\displaystyle p\equiv q\equiv 3{\pmod {4}}}$  那么

${\displaystyle x^{2}\equiv q{\pmod {p}}x^{2}}$  可解当且仅当 ${\displaystyle x^{2}\equiv p{\pmod {q}}}$  不可解。

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

 下文中的${\displaystyle p}$ 和${\displaystyle q}$ 总是不相等的正奇质数。

前期探索

费马曾经证明了^[4]（或声称证明了^[5]）一系列关于将质数表示成平方和的定理

${\displaystyle p=x^{2}+\;\,y^{2}}$  当且仅当 ${\displaystyle p=2}$  或 ${\displaystyle p\equiv 1{\pmod {4}}}$ 

${\displaystyle p=x^{2}+2y^{2}}$  当且仅当 ${\displaystyle p=2}$  或 ${\displaystyle p\equiv 1,3{\pmod {8}}}$ 

${\displaystyle p=x^{2}+3y^{2}}$  当且仅当 ${\displaystyle p=3}$  或 ${\displaystyle p\equiv 1{\pmod {3}}}$ 

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

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

如果${\displaystyle \;\,p\equiv 1,9,{\pmod {20}}}$  那么 ${\displaystyle \;\,p=x^{2}+5y^{2}}$ 

如果${\displaystyle p,q\equiv 3,7{\pmod {20}}}$  那么 ${\displaystyle pq=x^{2}+5y^{2}.}$ 

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

定理的首次叙述：欧拉

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

1) 如果 ${\displaystyle q\equiv 1{\pmod {4}}}$  那么${\displaystyle q}$ 是模${\displaystyle p}$ 的二次剩余当且仅当${\displaystyle p\equiv r{\pmod {q}}}$ ，其中${\displaystyle r}$ 是一个模${\displaystyle q}$ 的二次剩余。

2) 如果 ${\displaystyle q\equiv 3{\pmod {4}}}$  那么${\displaystyle q}$ 是模${\displaystyle p}$ 的二次剩余当且仅当${\displaystyle p\equiv \pm b^{2}{\pmod {4q}}}$ , 其中${\displaystyle b}$ 为奇数但不被${\displaystyle q}$ 整除。

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

勒让德与他的符号

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

勒让德认为表达式${\displaystyle N^{\frac {c-1}{2}}{\pmod {c}}}$ 出现了太多次，可以简写为：

${\displaystyle \left({\frac {N}{c}}\right)=\pm 1\equiv N^{\frac {c-1}{2}}{\pmod {c}}}$ 

其中${\displaystyle N}$ 、${\displaystyle c}$ 为互质的数^[11]。

这个符号就是现在使用的勒让德符号^[12]： 对于所有的整数${\displaystyle a}$ 以及任意奇质数${\displaystyle p}$ ：

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0\\+1\\-1\end{cases}}}$	如果${\displaystyle p}$ 整除${\displaystyle a}$ ；
	如果${\displaystyle a}$ 是模${\displaystyle p}$ 的二次剩余且${\displaystyle p}$ 不整除${\displaystyle a}$
	如果${\displaystyle a}$ 是模${\displaystyle p}$ 的二次非剩余。

.

；

.

.

勒让德使用勒让德符号的叙述为：

${\displaystyle \left({\frac {p}{q}}\right)=\left({\frac {q}{p}}\right)}$ ，如果 ${\displaystyle p\equiv 1{\pmod {4}}}$  或 ${\displaystyle q\equiv 1{\pmod {4}}}$ 

${\displaystyle \left({\frac {p}{q}}\right)=-\left({\frac {q}{p}}\right)}$ ，如果 ${\displaystyle p\equiv q\equiv 3{\pmod {4}}}$ 

他也提到上面的两种情况可以合并为：

${\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}}$ 

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

首次的证明：高斯

第一个完整地给出二次互反律的证明的人是德国数学家高斯。高斯在1796年给出了二次互反律的第一个证明^[14]。高斯首先证明了^[15] -1和2的情况。作为进行数学归纳法的开始，他证明了^[16]±3和±5的情况。他注意到-3和+5的情况较有规律，容易叙述^[17]，因此把定理叙述为^[18]：

如果 ${\displaystyle p}$  是形式为${\displaystyle 4n+1}$ ，那么 ${\displaystyle p}$ （如果 ${\displaystyle p}$  是形式为${\displaystyle 4n+3}$ 那么${\displaystyle -p}$ ）是模每个为模${\displaystyle p}$ 的二次剩余（非剩余）的质数的二次剩余（非剩余）。

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

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

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

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

证明中高斯用到了^[20]一个引理：

如果${\displaystyle p\equiv 1{\pmod {8}}}$  是质数，那么存在奇质数 ${\displaystyle q<2{\sqrt {p}}+1}$  使得 ${\displaystyle \left({\frac {p}{q}}\right)=-1}$ 

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

令${\displaystyle q^{*}=(-1)^{\frac {q-1}{2}}q}$ ，也就是说 ${\displaystyle |q^{*}|=|q|}$  且 ${\displaystyle q^{*}\equiv 1{\pmod {4}}}$ 。

那么 ${\displaystyle \left({\frac {p}{q}}\right)=\left({\frac {q^{*}}{p}}\right)}$ 

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

欧拉

如果${\displaystyle p\equiv \pm q{\pmod {4a}}}$  那么 ${\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {a}{q}}\right).}$  ^[21]

艾森斯坦

艾森斯坦^[22]曾声称：

如果 ${\displaystyle p\neq q,p'\neq q',p\equiv p'{\pmod {4}}}$  并且 ${\displaystyle q\equiv q'{\pmod {4}}}$  那么 ${\displaystyle {\Bigg (}{\frac {p}{q}}{\Bigg )}\left({\frac {q}{p}}\right)=\left({\frac {p'}{q'}}\right)\left({\frac {q'}{p'}}\right)}$ 

莫德尔

莫德尔^[23]证明了以下命题与二次互反律等价：

令 ${\displaystyle a,b}$ 和 ${\displaystyle c}$  为整数，那么对每个整除 ${\displaystyle abc}$  的质数${\displaystyle p}$ 有：

如果 ${\displaystyle ax^{2}+by^{2}+cz^{2}\equiv 0{\pmod {4abc/p}}}$ 有一个非平凡解，那么

${\displaystyle ax^{2}+by^{2}+cz^{2}\equiv 0{\pmod {4abc}}}$ 也有。

雅可比符号是勒让德符号的一个推广，与后者主要的区别是“分母”只需为正奇数，而不需要一定是质数。当“分母”为质数时，两者意义相同。雅可比符号的运算规律与勒让德符号相同，即：

${\displaystyle \left({\frac {-1}{n}}\right)=(-1)^{\frac {(n-1)}{2}}=\left\{{\begin{array}{cl}1&\ \;n\equiv 1{\pmod {4}}\\-1&\ \;n\equiv 3{\pmod {4}}\end{array}}\right.}$ 

${\displaystyle {\left({\frac {2}{n}}\right)=(-1)^{\frac {(n^{2}-1)}{8}}=\left\{{\begin{array}{cl}1&\ \;n\equiv 1,7{\pmod {8}}\\-1&\ \;n\equiv 3,5{\pmod {8}}\end{array}}\right.}}$ 

如果两个数都是正奇数，那么二次互反律对雅可比符号也成立：

${\displaystyle \left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{\frac {(m-1)(n-1)}{4}}.}$ 

然而，当雅可比符号为+1，“分母”为合数时，“分子”不一定是“分母”的二次剩余。高斯的第九至十四种情况可以被表示为：

${\displaystyle \left({\frac {M}{p}}\right)=(-1)^{\frac {(p-1)(M-1)}{4}}{\Bigg (}{\frac {p}{M}}{\Bigg )}}$ 

由于${\displaystyle p}$ 为质数，上式左边是勒让德符号，于是我们可以知道${\displaystyle M}$ 是否是模${\displaystyle p}$ 的剩余。

以上各节的公式对雅可比符号仍然成立。欧拉的公式可以写作：

${\displaystyle {\frac {a}{m}}={\frac {a}{m\pm 4an}}}$ 

其中${\displaystyle n}$ 为整数，${\displaystyle m\pm 4an>0}$ 

举例来说： ${\displaystyle {\frac {2}{7}}={\frac {2}{15}}={\frac {2}{23}}={\frac {2}{31}}\dots =1,}$ 

2是模7、23、31的剩余，但2是模5的非剩余，因此也不是模15的。这与勒让德提出过的一个问题有关：若已知${\displaystyle {\frac {a}{m}}=-1}$  ，我们知道${\displaystyle a}$ 是模${\displaystyle m+4a}$ 、${\displaystyle m+8a}$ 、……中所有质数的非剩余，如果这种质数存在的话。但此种质数的存在性直到数十年后才由狄利克雷证明。

艾森斯坦的公式则需要两数互质才能成立： 如果${\displaystyle a,b,a',b'}$  是正奇数，且 ${\displaystyle \gcd(a,b)=\gcd(a',b')=1}$ ，那么

如果${\displaystyle a\equiv a'{\pmod {4}}}$  且 ${\displaystyle b\equiv b'{\pmod {4}}}$ ，则

${\displaystyle {\Bigg (}{\frac {a}{b}}{\Bigg )}\left({\frac {b}{a}}\right)=\left({\frac {a'}{b'}}\right)\left({\frac {b'}{a'}}\right)}$ 

二次互反律也可以用希尔伯特符号：${\displaystyle (a,b)_{v}}$  来叙述。其中${\displaystyle a}$ 、${\displaystyle b}$ 是两个非零的有理数，${\displaystyle v}$ 则可代表任意非平凡的有理数绝对值（${\displaystyle p}$ 的常用的或p进的绝对值）。希尔伯特符号：${\displaystyle (a,b)_{v}}$  的值取1或−1。按照定义，它的值取1当且仅当方程${\displaystyle ax^{2}+by^{2}=z^{2}}$ 在有理数关于${\displaystyle v}$ 的完备空间中有除了${\displaystyle x=y=z=0}$ 之外的解。希尔伯特二次互反律声称：对于固定的${\displaystyle a}$ 、${\displaystyle b}$ ，当${\displaystyle v}$ 变动时，除了对有限个${\displaystyle v}$ 以外，${\displaystyle (a,b)_{v}}$ 的值都是1，并且取遍所有${\displaystyle v}$ 时，所有 ${\displaystyle (a,b)_{v}}$  的乘积为1（这与复分析中的留数定理相似）。

希尔伯特二次互反律的证明可以归结到几个特殊情况，可以证明其中非平凡的情况与勒让德符号下的二次互反律的两个辅助定理（-1和2的情况）是等价的。在希尔伯特二次互反律中其实并没有“互反”的情形，它的名字只是表明它的历史来源是作为二次互反律的研究成果。不同于二次互反律要考虑正负问题，并要区分2的情况，希尔伯特二次互反律对所有的有理数都是平等的。因此使用希尔伯特符号的二次互反律推广起来更为自然：其推广到整体域时只需做出很少改变，并对所有的整体域都适用^[24]。

以二次互反律配合以下两个辅助定理

${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\frac {p^{2}-1}{8}}}$ 

${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}}$ 

即能迅速地计算勒让德符号，从而解决二次剩余的判别问题。

例如判别37是否是模89的二次剩余：

${\displaystyle \left({\frac {37}{89}}\right)\left({\frac {89}{37}}\right)=(-1)^{\frac {(37-1)(89-1)}{4}}=1}$ 

所以 ${\displaystyle \left({\frac {37}{89}}\right)=\left({\frac {89}{37}}\right)=\left({\frac {89-37-37}{37}}\right)=\left({\frac {15}{37}}\right)=\left({\frac {3}{37}}\right)\left({\frac {5}{37}}\right)=\left({\frac {37}{3}}\right)\left({\frac {37}{5}}\right)=\left({\frac {1}{3}}\right)\left({\frac {2}{5}}\right)=-1}$ 

因此37不是模89的二次剩余。

二次互反律的推广主要是在代数数论中。

例如：高斯考察过四次互反律。在他的^[25]首篇论文里他证明了一系列定理，其中最重要的是：如果${\displaystyle p\equiv 1\mod 4}$ ，那么${\displaystyle x^{4}\equiv 2\mod p}$ 有解当且仅当${\displaystyle p=a^{2}+64b^{2}}$ ，其中${\displaystyle a}$ 、${\displaystyle b}$ 是整数，如果${\displaystyle p\equiv 1\mod 4}$ ，那么${\displaystyle x^{4}\equiv -3\mod p}$ 有解当且仅当${\displaystyle p=a^{2}+36b^{2}}$ ，其中${\displaystyle a}$ 、${\displaystyle b}$ 是整数，如果${\displaystyle p\equiv 1\mod 4}$ ，那么${\displaystyle x^{4}\equiv 5\mod p}$ 有解当且仅当${\displaystyle p=a^{2}+100b^{2}}$ ，其中${\displaystyle a}$ 、${\displaystyle b}$ 是整数，如果${\displaystyle p\equiv 3\mod 4}$ ，那么模${\displaystyle p}$ 的二次剩余必然是四次剩余。

在第二篇论文中^[26]，高斯引进了著名的高斯整数。高斯证明了模4余1的质数总能分解为两个高斯整数中质数的乘积、唯一分解定理等其它代数数论的基础定理，并引进了一些基本概念，如范数和单位元。在高斯整数中，四次互反律的叙述十分简单。高斯并且注意到在艾森斯坦整环中，三次互反律最为简单。一部分的原因是高斯整数中1有4个四次方根，而艾森斯坦整数中1有3个三次方根。

其它的推广是在以上整环中的二次互反律。高斯率先研究了高斯整数中的二次互反律^[27]。

• 同余
• 同余方程
• 二次剩余
• 高斯引理
• 二次互反律的证明
• 三次互反律
• 阿廷互反律

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, 1986, ISBN 0387962549 

• Gauss, Carl Friedrich; Maser, H. (translator into German), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, 1965, ISBN 0-8284-0191-8 

• Lemmermeyer, Franz, Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, 2000, ISBN 3-540-66967-4 请检查|isbn=值 (帮助) 

• Ireland, Kenneth; Rosen, Michael, A Classical Introduction to Modern Number Theory (second edition), New York: Springer, 1990, ISBN 0-387-97329-X 

• 二次互反律^{[永久失效链接]}
• 高斯二次互反律^{[永久失效链接]}
• （英文）二次互反律的246个证明. [2010-12-01]. （原始内容存档于2011-05-18）.  （页面存档备份，存于互联网档案馆）