高斯引理
字数 2155 2025-10-28 20:05:42

高斯引理

我们先从二次剩余的判定问题开始。设 \(p\) 是一个奇素数，\(a\) 是一个与 \(p\) 互质的整数。勒让德符号 \(\left( \frac{a}{p} \right)\) 用于判断 \(a\) 是否是模 \(p\) 的二次剩余。计算勒让德符号的一个基本方法是使用欧拉判别准则：\(a^{\frac{p-1}{2}} \equiv \left( \frac{a}{p} \right) \pmod{p}\)。然而，当 \(p\) 很大时，计算模幂可能非常低效。高斯引理提供了一个不需要进行大量指数运算的替代方法，它通过一个简单的计数过程来判定二次剩余性。

高斯引理的陈述如下：考虑整数集合 \(S = \{1, 2, \dots, \frac{p-1}{2} \}\)。将集合 \(a \times S = \{ a, 2a, 3a, \dots, \frac{p-1}{2}a \}\) 中的每个数对 \(p\) 取模，得到一组绝对最小剩余（即每个剩余被替换为模 \(p\) 意义下与其同余且绝对值最小的数，范围在 \(-\frac{p-1}{2}\) 到 \(\frac{p-1}{2}\) 之间）。设 \(m\) 为这些绝对最小剩余中负数的个数。那么，勒让德符号由公式 \(\left( \frac{a}{p} \right) = (-1)^m\) 给出。

让我们通过一个具体的例子来理解这个过程。取 \(p = 11\)，\(a = 7\)。

  1. 集合 \(S = \{1, 2, 3, 4, 5\}\)。
  2. 计算 \(a \times S = \{7, 14, 21, 28, 35\}\)。
  3. 计算每个元素模 11 的绝对最小剩余：
    • 7 mod 11 = 7 (正)
    • 14 mod 11 = 3 (正)
    • 21 mod 11 = 10，其绝对最小剩余是 -1 (负)
    • 28 mod 11 = 6 (正)
    • 35 mod 11 = 2 (正)
  4. 负数的个数 \(m = 1\)。
  5. 因此，\(\left( \frac{7}{11} \right) = (-1)^1 = -1\)，说明 7 是模 11 的二次非剩余。

高斯引理为什么成立？其证明思路揭示了模运算的优美对称性。关键点在于，集合 \(a \times S\) 中所有数的绝对最小剩余（在取绝对值后）实际上就是集合 \(S\) 本身的一个排列。也就是说，集合 \(\{ |a \cdot 1|_p, |a \cdot 2|_p, \dots, |a \cdot \frac{p-1}{2}|_p \}\)（其中 \(|x|_p\) 表示 \(x\) 模 \(p\) 的绝对最小剩余）正好是 \(\{1, 2, \dots, \frac{p-1}{2}\}\)，只是顺序可能不同。这是因为这些绝对最小剩余两两不同，且都落在 \([1, (p-1)/2]\) 区间内，而该区间恰好有 \((p-1)/2\) 个数。

现在，我们将集合 \(a \times S\) 中所有元素模 \(p\) 的结果相乘。一方面，由于这 \((p-1)/2\) 个数是 \(a \times S\) 中的元素，其乘积为 \(a^{(p-1)/2} \times (1 \cdot 2 \cdot ... \cdot (p-1)/2)\)。
另一方面，这个乘积也等于其绝对最小剩余的乘积。每个绝对最小剩余要么是正数 \(r_i\)，要么是负数 \(-s_j\)。所有正数的乘积记为 \(R\)，所有负数的乘积是 \((-1)^m\) 乘以这些负数的绝对值。而根据前面的关键点，所有这些绝对值（正数的和负数的）的乘积正好是 \(1 \cdot 2 \cdot ... \cdot (p-1)/2\)。
因此，我们有：
\(a^{(p-1)/2} \times (1 \cdot 2 \cdot ... \cdot (p-1)/2) \equiv R \times (-1)^m \times (\text{绝对值的乘积}) \equiv (1 \cdot 2 \cdot ... \cdot (p-1)/2) \times (-1)^m \pmod{p}\)。
由于 \((1 \cdot 2 \cdot ... \cdot (p-1)/2)\) 与 \(p\) 互质，我们可以将其从同余式两边约去，得到：
\(a^{(p-1)/2} \equiv (-1)^m \pmod{p}\)。
再根据欧拉判别准则 \(a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod{p}\)，我们就得到了 \(\left( \frac{a}{p} \right) = (-1)^m\)。

高斯引理的价值在于它将一个指数运算问题转化为了一个计数问题（数负数的个数），这在理论和计算上都非常有用。它是证明二次互反律的一个关键步骤。

高斯引理 我们先从二次剩余的判定问题开始。设 \( p \) 是一个奇素数，\( a \) 是一个与 \( p \) 互质的整数。勒让德符号 \( \left( \frac{a}{p} \right) \) 用于判断 \( a \) 是否是模 \( p \) 的二次剩余。计算勒让德符号的一个基本方法是使用欧拉判别准则：\( a^{\frac{p-1}{2}} \equiv \left( \frac{a}{p} \right) \pmod{p} \)。然而，当 \( p \) 很大时，计算模幂可能非常低效。高斯引理提供了一个不需要进行大量指数运算的替代方法，它通过一个简单的计数过程来判定二次剩余性。 高斯引理的陈述如下：考虑整数集合 \( S = \{1, 2, \dots, \frac{p-1}{2} \} \)。将集合 \( a \times S = \{ a, 2a, 3a, \dots, \frac{p-1}{2}a \} \) 中的每个数对 \( p \) 取模，得到一组绝对最小剩余（即每个剩余被替换为模 \( p \) 意义下与其同余且绝对值最小的数，范围在 \( -\frac{p-1}{2} \) 到 \( \frac{p-1}{2} \) 之间）。设 \( m \) 为这些绝对最小剩余中负数的个数。那么，勒让德符号由公式 \( \left( \frac{a}{p} \right) = (-1)^m \) 给出。 让我们通过一个具体的例子来理解这个过程。取 \( p = 11 \)，\( a = 7 \)。 集合 \( S = \{1, 2, 3, 4, 5\} \)。 计算 \( a \times S = \{7, 14, 21, 28, 35\} \)。 计算每个元素模 11 的绝对最小剩余： 7 mod 11 = 7 (正) 14 mod 11 = 3 (正) 21 mod 11 = 10，其绝对最小剩余是 -1 (负) 28 mod 11 = 6 (正) 35 mod 11 = 2 (正) 负数的个数 \( m = 1 \)。 因此，\( \left( \frac{7}{11} \right) = (-1)^1 = -1 \)，说明 7 是模 11 的二次非剩余。 高斯引理为什么成立？其证明思路揭示了模运算的优美对称性。关键点在于，集合 \( a \times S \) 中所有数的绝对最小剩余（在取绝对值后）实际上就是集合 \( S \) 本身的一个排列。也就是说，集合 \( \{ |a \cdot 1|_ p, |a \cdot 2|_ p, \dots, |a \cdot \frac{p-1}{2}|_ p \} \)（其中 \( |x|_ p \) 表示 \( x \) 模 \( p \) 的绝对最小剩余）正好是 \( \{1, 2, \dots, \frac{p-1}{2}\} \)，只是顺序可能不同。这是因为这些绝对最小剩余两两不同，且都落在 \( [ 1, (p-1)/2 ] \) 区间内，而该区间恰好有 \( (p-1)/2 \) 个数。 现在，我们将集合 \( a \times S \) 中所有元素模 \( p \) 的结果相乘。一方面，由于这 \( (p-1)/2 \) 个数是 \( a \times S \) 中的元素，其乘积为 \( a^{(p-1)/2} \times (1 \cdot 2 \cdot ... \cdot (p-1)/2) \)。 另一方面，这个乘积也等于其绝对最小剩余的乘积。每个绝对最小剩余要么是正数 \( r_ i \)，要么是负数 \( -s_ j \)。所有正数的乘积记为 \( R \)，所有负数的乘积是 \( (-1)^m \) 乘以这些负数的绝对值。而根据前面的关键点，所有这些绝对值（正数的和负数的）的乘积正好是 \( 1 \cdot 2 \cdot ... \cdot (p-1)/2 \)。 因此，我们有： \( a^{(p-1)/2} \times (1 \cdot 2 \cdot ... \cdot (p-1)/2) \equiv R \times (-1)^m \times (\text{绝对值的乘积}) \equiv (1 \cdot 2 \cdot ... \cdot (p-1)/2) \times (-1)^m \pmod{p} \)。 由于 \( (1 \cdot 2 \cdot ... \cdot (p-1)/2) \) 与 \( p \) 互质，我们可以将其从同余式两边约去，得到： \( a^{(p-1)/2} \equiv (-1)^m \pmod{p} \)。 再根据欧拉判别准则 \( a^{(p-1)/2} \equiv \left( \frac{a}{p} \right) \pmod{p} \)，我们就得到了 \( \left( \frac{a}{p} \right) = (-1)^m \)。 高斯引理的价值在于它将一个指数运算问题转化为了一个计数问题（数负数的个数），这在理论和计算上都非常有用。它是证明二次互反律的一个关键步骤。