高斯引理

在数论中，高斯引理给出了一个整数是模另一个整数的二次剩余的条件。尽管高斯引理没有实际计算上的意义，但作为二次互反律的证明中的一环，高斯引理有着理论上的重要性。

高斯引理最早出现在高斯1808年发表的二次互反律的第三个证明中，并在第五个证明中再次用到。

叙述
设为奇质数，是一个与互质的整数。考虑以下数组：, 取它们模的最小非负剩余。这些剩余两两不等，因此我们共有个两两不等的介于1和之间的整数：。设其中有个数比大，那么高斯引理声称：

上式左边是勒让德符号，当其值为+1时，表示是模的二次剩余；其值为-1时，表示是模的二次非剩余。

用通俗的语言来说，就是：如果里面比大的有偶数个，那么是模的二次剩余，如果有奇数个，那么是模的二次非剩余。

例子
令，，则我们考虑的数组是。模11之后，就得到。其中比大的有三个：。3是奇数，因此由高斯引理得到结论：7是模11的二次非剩余。

这个结论是正确的，因为模11的全部二次剩余是，不包括7在内。

证明

一个常见的简单证明用的是一个令人联想到费马小定理之最简单证明的方法：考虑乘积
 
用两种方式模p之后，一方面可以得到：
 

另一方面，我们将中每一个比大的数都减去，这样我们得到一个新数组，其中每个数都介于与之间。取绝对值后，我们便得到个介于1和之间（含等于）的整数（这是因为不是整数，因此比小的整数必然小于等于）。

关键的一步，是证明这些数两两不等。

证明是用反证法：假设在这些数中有两个数和相等，那么找出其对应的“原型”：与，其中k和l是两个介于1和之间的整数。分别平方后，就有：

因此p整除两者之差：。

但这不可能，因为p不整除，并且由于k和l是两个介于1和之间的整数，它们的和与差的都介于与之间，绝对值比小，不可能被整除。这导致了矛盾！

因此这个数都在1和之间，且两两不等。于是它们就是。这样，
 
   (因为我们知道)
   (比大的减去之后为负数，因此共有个-1)
 

总结两次不同算法的结果，可以得出：（因为不整除）。然而由欧拉判别法可以得出

因此有

引理得证。

应用
在很多的二次互反律的证明中都可以见到高斯引理的身影。比如艾森斯坦曾用高斯引理证明了在为奇质数时，有下式成立

并运用这个公式证明二次互反律（并且运用椭圆函数而不是三角函数来证明三次以及四次的互反律）。

克罗内克运用高斯引理证明了
。
翻转p和q后就可立即得到二次互反律。

与群论中迁移的关系
令为Z/pZ中全体非零的二次剩余类组成的乘法群，令为此群的子群。考虑如下的中的陪集代表：
。
在这些陪集上应用迁移，就可以得到迁移同态：，将射到，其中与为高斯引理中所定义的。高斯引理可以被看做一个清楚地将这个同态等同到二次剩余特征的计算。

参见
同余
二次剩余
勒让德符号
二次互反律
欧拉判别法
佐罗塔列夫引理

注释

参考来源

包含证明的条目
数论引理
同余
二次剩余
数论中的平方