查看“︁高斯引理”︁的源代码

{{For|多項式的「高斯引理」|高斯引理 (多項式)}}
在[[数论]]中，'''高斯引理'''给出了一个[[整数]]是[[同余|模]]另一个整数的[[二次剩余]]的条件。尽管高斯引理没有实际计算上的意义，但作为[[二次互反律]]的证明中的一环，高斯引理有着理论上的重要性。

高斯引理最早出现在[[高斯]]1808年发表的二次互反律的[[二次互反律的证明|第三个证明]]中<ref>"Neuer Beweis eines arithmetischen Satzes"; pp 458-462 of ''Untersuchungen uber hohere Arithmetik''</ref>，并在第五个证明中再次用到<ref>"Neue Beweise und Erweiterungen des Fundalmentalsatzes in der Lehre von den quadratischen Reste"; pp 496-501 of ''Untersuchungen uber hohere Arithmetik''</ref>。

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

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

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

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

==证明==

一个常见的简单证明<ref>在一般的初等数论教材或相关著作中都可以看到这个证明，这里引用的是高斯的''Untersuchungen uber hohere Arithmetik''，pp 458-462</ref>用的是一个令人联想到[[费马小定理]]之最简单证明的方法：考虑乘积
: <math>Z = a \cdot 2a \cdot 3a \cdot \cdots \cdot \frac{p-1}2 a</math>
用两种方式模''p''之后，一方面可以得到：
: <math>Z = a^{\frac{p-1}{2}} \left(1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2 \right)</math>

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

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

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

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

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

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

==应用==
在很多的二次互反律的证明中都可以见到高斯引理的身影<ref>Lemmermeyer, ch. 1</ref><ref>Lemmermeyer, p. 9 "like most of the simplest proofs [ of QR], [Gauss's] 3 and 5 rest on what we now call Gauss's Lemma</ref>。比如[[費迪南·艾森斯坦|艾森斯坦]]曾用高斯引理证明了在''<math>p</math>''为奇质数时，有下式成立
:<math>\left(\frac{a}{p}\right)=\prod_{n=1}^{(p-1)/2}\frac{\sin{(\frac{2\pi an}{p})}}{\sin{(\frac{2\pi n}{p})}},</math>
并运用这个公式证明二次互反律（并且运用[[椭圆函数]]而不是[[三角函数]]来证明三次以及四次的互反律<ref>Lemmermeyer, ch. 8</ref>）。

[[克罗内克]]运用高斯引理证明了
:<math>\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)</math>。
翻转''p''和''q''后就可立即得到二次互反律。

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

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

==注释==
{{reflist}}

==参考来源==

*{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | last2 = Maser | first2 = H.（translator into German）  
  | title = Untersuchungen uber hohere Arithmetik（Disqusitiones Arithemeticae & other papers on number theory）（Second edition）
  | publisher = Chelsea
  | location = New York
  | date = 1965
  | isbn = 0-8284-0191-8}}

*{{citation
  | last1 = Lemmermeyer  | first1 = Franz
  | title = Reciprocity Laws: from Euler to Eisenstein
  | publisher = {{tsl|en|Springer||Springer}}
  | location = Berlin
  | date = 2000
  | isbn = 3-540-66967-4}}

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