高斯引理

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

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

叙述
设p为奇质数，a是一个与p互质的整数。考虑以下数组：a, 2a, 3a, \dots, \frac{p-1}{2}a, 取它们模p的最小非负剩余。这些剩余两两不等，因此我们共有\frac{p-1}{2}个两两不等的介于1和p-1之间的整数：t_1, t_2, t_3, \dots, t_{ \frac{p-1}{2} }。设其中有n个数比\frac{p}{2}大，那么高斯引理声称：
:\left(\frac{a}{p}\right) =(-1)^n
上式左边是勒让德符号，当其值为+1时，表示a是模p的二次剩余；其值为-1时，表示a是模p的二次非剩余。

用通俗的语言来说，就是：如果t_1, t_2, t_3, \dots, t_{ \frac{p-1}{2} }里面比\frac{p}{2}大的有偶数个，那么a是模p的二次剩余，如果有奇数个，那么a是模p的二次非剩余。

例子
令p=11，a=7，则我们考虑的数组是7, 14, 21, 28, 35。模11之后，就得到7, 3, 10, 6, 2。其中比\frac{11}{2}大的有三个：6,7,10。3是奇数，因此由高斯引理得到结论：7是模11的二次非剩余。

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

证明
一个常见的简单证明用的是一个令人联想到费马小定理之最简单证明的方法：考虑乘积
: Z = a \cdot 2a \cdot 3a \cdot \cdots \cdot \frac{p-1}2 a
用两种方式模p之后，一方面可以得到：
: Z = a^{\frac{p-1}{2}} \left(1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2 \right)

另一方面，我们将t_1,t_2, \cdots t_{ \frac{p-1}{2} }中每一个比\frac{p}{2}大的数都减去p，这样我们得到一个新数组t'_1,t'_2, \cdots t'_{ \frac{p-1}{2} }，其中每个数都介于- \frac{p}{2}与\frac{p}{2}之间。取绝对值后，我们便得到\frac{p-1}{2}个介于1和\frac{p-1}{2}之间（含等于\frac{p-1}{2}）的整数（这是因为\frac{p}{2}不是整数，因此比\frac{p}{2}小的整数必然小于等于\frac{p-1}{2}）。

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

证明是用反证法：假设在这些数中有两个数|x|和|y|相等，那么找出其对应的“原型”：x \equiv k \cdot a \mod p与y \equiv l \cdot a \mod p，其中k和l是两个介于1和\frac{p-1}{2}之间的整数。分别平方后，就有：
:(ka)^2 \equiv x^2 \equiv y^2 \equiv (la)^2 \mod p
因此p整除两者之差：p |(ka)^2 -(la)^2 = a^2 \cdot(k+l) \cdot (k-l)。

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

因此这\frac{p-1}{2}个数都在1和\frac{p-1}{2}之间，且两两不等。于是它们就是1,2, \cdots \frac{p-1}{2}。这样，
: Z \equiv t_1 t_2 \cdots t_{ \frac{p-1}{2} }
: .\ \ \equiv t'_1 t'_2 \cdots t'_{ \frac{p-1}{2} } (因为我们知道t_i \equiv t_i - p \mod p)
: .\ \ \equiv (-1)^n \cdot |t'_1| |t'_2| \cdots |t'_{ \frac{p-1}{2} }| (比\frac{p}{2}大的减去p之后为负数，因此共有n个-1)
: .\ \ \equiv (-1)^n \left(1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2 \right) \mod p

总结两次不同算法的结果，可以得出：(-1)^n \equiv a^{\frac{p-1}{2}} \mod p（因为p不整除1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2 ）。然而由欧拉判别法可以得出
:\left(\frac{a}{p}\right) = a^{\frac{p-1}{2}}
因此有
:\left(\frac{a}{p}\right) =(-1)^n
引理得证。

应用
在很多的二次互反律的证明中都可以见到高斯引理的身影。比如艾森斯坦曾用高斯引理证明了在p为奇质数时，有下式成立
:\left(\frac{a}{p}\right)=\prod_{n=1}^{(p-1)/2}\frac{\sin{(\frac{2\pi an}{p})}}{\sin{(\frac{2\pi n}{p})}},
并运用这个公式证明二次互反律（并且运用椭圆函数而不是三角函数来证明三次以及四次的互反律）。

克罗内克运用高斯引理证明了
:\left(\frac{p}{q}\right)=\sgn\prod_{i=1}^{\frac{q-1}{2}}\prod_{k=1}^{\frac{p-1}{2}}\left(\frac{k}{p}-\frac{i}{q}\right)。
翻转p和q后就可立即得到二次互反律。

与群论中迁移的关系
令G为Z/pZ中全体非零的二次剩余类组成的乘法群，令H为此群的子群\{+1,-1\}。考虑如下的G中H*的陪集代表：
:1, 2, 3, \dots, \frac{p-1}{2}。
在这些陪集上应用迁移，就可以得到迁移同态：\phi : G \to H，将a射到(-1)^n，其中a与n为高斯引理中所定义的。高斯引理可以被看做一个清楚地将这个同态等同到二次剩余特征的计算。

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

注释
参考来源
*

*