勒让德符号

字数 4083 2025-10-26 19:16:23

勒让德符号

勒让德符号是数论中一个简洁而强大的记号和工具，它用于判断一个整数在模某个奇素数下是否是二次剩余。它的定义建立在我们之前讨论的二次剩余和模运算的知识之上。

定义
设 \(p\) 是一个奇素数（即 \(p > 2\) 的素数），\(a\) 是一个整数。勒让德符号 \(\left(\frac{a}{p}\right)\) 定义如下：

\(\left(\frac{a}{p}\right) = 1\)，如果 \(a\) 不是 \(p\) 的倍数，并且 \(a\) 是模 \(p\) 的二次剩余（即同余方程 \(x^2 \equiv a \pmod{p}\) 有解）。
\(\left(\frac{a}{p}\right) = -1\)，如果 \(a\) 不是 \(p\) 的倍数，并且 \(a\) 是模 \(p\) 的二次非剩余（即同余方程 \(x^2 \equiv a \pmod{p}\) 无解）。
\(\left(\frac{a}{p}\right) = 0\)，如果 \(a\) 是 \(p\) 的倍数（即 \(a \equiv 0 \pmod{p}\)）。

这个符号将一个关于同余方程解的存在性问题，转化为了一个简单的数值（1， -1 或 0）。

核心性质与计算规则
勒让德符号的价值不仅在于其定义，更在于它遵循一系列优美的计算规则，使得我们无需直接求解二次同余方程就能计算出它的值。

周期性（模 p）: \(\left(\frac{a + kp}{p}\right) = \left(\frac{a}{p}\right)\) 对任意整数 \(k\) 成立。这意味着在计算符号时，我们可以随时将 \(a\) 替换为它除以 \(p\) 的余数。
完全积性: 对于任意整数 \(a\) 和 \(b\)，有 \(\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\)。这个性质极其重要，它意味着我们可以将一个复杂数的符号分解成其质因数符号的乘积。
二次互反律: 这是数论中最优美和深刻的定理之一。设 \(p\) 和 \(q\) 都是奇素数且 \(p \neq q\)，则有：

\[ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}} \]

这个定律表明，符号 \(\left(\frac{p}{q}\right)\) 和 \(\left(\frac{q}{p}\right)\) 在绝大多数情况下是相等的，除非 \(p\) 和 \(q\) 模 4 都余 3，此时它们互为相反数。这使我们能够“翻转”分子和分母，极大地简化了计算。
* 特殊值:

\(\left(\frac{1}{p}\right) = 1\)，因为 \(1^2 \equiv 1 \pmod{p}\)。
\(\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}\)。这意味着 \(-1\) 是模 \(p\) 的二次剩余当且仅当 \(p \equiv 1 \pmod{4}\)。
\(\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}\)。这意味着 \(2\) 是模 \(p\) 的二次剩余当且仅当 \(p \equiv \pm 1 \pmod{8}\)。

计算示例
让我们利用这些规则来计算 \(\left(\frac{42}{97}\right)\)，而不去检查 0 到 96 之间有哪些数的平方模 97 等于 42。

步骤 1：分解
利用积性：\(\left(\frac{42}{97}\right) = \left(\frac{2 \times 3 \times 7}{97}\right) = \left(\frac{2}{97}\right) \left(\frac{3}{97}\right) \left(\frac{7}{97}\right)\)

步骤 2：计算 \(\left(\frac{2}{97}\right)\)
使用特殊值规则。判断 97 模 8 的余数：\(97 \div 8 = 12\) 余 \(1\)，即 \(97 \equiv 1 \pmod{8}\)。因为 \(1 \equiv \pm 1 \pmod{8}\)，所以 \(\left(\frac{2}{97}\right) = 1\)。

步骤 3：计算 \(\left(\frac{3}{97}\right)\) 和 \(\left(\frac{7}{97}\right)\) 使用二次互反律

对于 \(\left(\frac{3}{97}\right)\): 因为 3 和 97 都是奇素数，应用二次互反律：

\[ \left(\frac{3}{97}\right) \left(\frac{97}{3}\right) = (-1)^{\frac{3-1}{2} \cdot \frac{97-1}{2}} = (-1)^{1 \cdot 48} = 1 \]

所以 \(\left(\frac{3}{97}\right) = \left(\frac{97}{3}\right)\)。
现在计算 \(\left(\frac{97}{3}\right)\)。利用周期性，求 97 模 3 的余数：\(97 \div 3 = 32\) 余 \(1\)，所以 \(\left(\frac{97}{3}\right) = \left(\frac{1}{3}\right) = 1\)。
因此，\(\left(\frac{3}{97}\right) = 1\)。

对于 \(\left(\frac{7}{97}\right)\): 应用二次互反律：

\[ \left(\frac{7}{97}\right) \left(\frac{97}{7}\right) = (-1)^{\frac{7-1}{2} \cdot \frac{97-1}{2}} = (-1)^{3 \cdot 48} = 1 \]

所以 \(\left(\frac{7}{97}\right) = \left(\frac{97}{7}\right)\)。
计算 \(\left(\frac{97}{7}\right)\)。求 97 模 7 的余数：\(97 \div 7 = 13\) 余 \(6\)（因为 \(7 \times 13 = 91, 97-91=6\)），所以 \(\left(\frac{97}{7}\right) = \left(\frac{6}{7}\right)\)。
利用积性分解：\(\left(\frac{6}{7}\right) = \left(\frac{2 \times 3}{7}\right) = \left(\frac{2}{7}\right) \left(\frac{3}{7}\right)\)。

计算 \(\left(\frac{2}{7}\right)\): 判断 7 模 8：\(7 \equiv 7 \pmod{8}\)，而 \(7 \equiv -1 \pmod{8}\)，属于 \(\pm 1\)，所以 \(\left(\frac{2}{7}\right) = 1\)。
计算 \(\left(\frac{3}{7}\right)\): 再次应用二次互反律：\(\left(\frac{3}{7}\right) \left(\frac{7}{3}\right) = (-1)^{1 \cdot 3} = -1\)，所以 \(\left(\frac{3}{7}\right) = -\left(\frac{7}{3}\right)\)。
计算 \(\left(\frac{7}{3}\right)\): 7 模 3 余 1，所以 \(\left(\frac{7}{3}\right) = \left(\frac{1}{3}\right) = 1\)。
因此，\(\left(\frac{3}{7}\right) = -1\)。
综合起来，\(\left(\frac{6}{7}\right) = 1 \times (-1) = -1\)。
所以，\(\left(\frac{7}{97}\right) = \left(\frac{97}{7}\right) = \left(\frac{6}{7}\right) = -1\)。

步骤 4：汇总结果
\(\left(\frac{42}{97}\right) = \left(\frac{2}{97}\right) \times \left(\frac{3}{97}\right) \times \left(\frac{7}{97}\right) = 1 \times 1 \times (-1) = -1\)。

结论: 勒让德符号 \(\left(\frac{42}{97}\right) = -1\)，这意味着 42 是模奇素数 97 的二次非剩余，方程 \(x^2 \equiv 42 \pmod{97}\) 没有解。

通过这个例子，你可以看到勒让德符号如何将复杂的判定问题转化为一个系统性的代数计算过程，这充分体现了其作为数论工具的威力。

勒让德符号勒让德符号是数论中一个简洁而强大的记号和工具，它用于判断一个整数在模某个奇素数下是否是二次剩余。它的定义建立在我们之前讨论的二次剩余和模运算的知识之上。定义设 \( p \) 是一个奇素数（即 \( p > 2 \) 的素数），\( a \) 是一个整数。勒让德符号 \( \left(\frac{a}{p}\right) \) 定义如下： \( \left(\frac{a}{p}\right) = 1 \)，如果 \( a \) 不是 \( p \) 的倍数，并且 \( a \) 是模 \( p \) 的二次剩余（即同余方程 \( x^2 \equiv a \pmod{p} \) 有解）。 \( \left(\frac{a}{p}\right) = -1 \)，如果 \( a \) 不是 \( p \) 的倍数，并且 \( a \) 是模 \( p \) 的二次非剩余（即同余方程 \( x^2 \equiv a \pmod{p} \) 无解）。 \( \left(\frac{a}{p}\right) = 0 \)，如果 \( a \) 是 \( p \) 的倍数（即 \( a \equiv 0 \pmod{p} \)）。这个符号将一个关于同余方程解的存在性问题，转化为了一个简单的数值（1， -1 或 0）。核心性质与计算规则勒让德符号的价值不仅在于其定义，更在于它遵循一系列优美的计算规则，使得我们无需直接求解二次同余方程就能计算出它的值。周期性（模 p） : \( \left(\frac{a + kp}{p}\right) = \left(\frac{a}{p}\right) \) 对任意整数 \( k \) 成立。这意味着在计算符号时，我们可以随时将 \( a \) 替换为它除以 \( p \) 的余数。完全积性 : 对于任意整数 \( a \) 和 \( b \)，有 \( \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \)。这个性质极其重要，它意味着我们可以将一个复杂数的符号分解成其质因数符号的乘积。二次互反律 : 这是数论中最优美和深刻的定理之一。设 \( p \) 和 \( q \) 都是奇素数且 \( p \neq q \)，则有： \[ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}} \] 这个定律表明，符号 \( \left(\frac{p}{q}\right) \) 和 \( \left(\frac{q}{p}\right) \) 在绝大多数情况下是相等的，除非 \( p \) 和 \( q \) 模 4 都余 3，此时它们互为相反数。这使我们能够“翻转”分子和分母，极大地简化了计算。特殊值 : \( \left(\frac{1}{p}\right) = 1 \)，因为 \( 1^2 \equiv 1 \pmod{p} \)。 \( \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} \)。这意味着 \( -1 \) 是模 \( p \) 的二次剩余当且仅当 \( p \equiv 1 \pmod{4} \)。 \( \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} \)。这意味着 \( 2 \) 是模 \( p \) 的二次剩余当且仅当 \( p \equiv \pm 1 \pmod{8} \)。计算示例让我们利用这些规则来计算 \( \left(\frac{42}{97}\right) \)，而不去检查 0 到 96 之间有哪些数的平方模 97 等于 42。步骤 1：分解利用积性：\( \left(\frac{42}{97}\right) = \left(\frac{2 \times 3 \times 7}{97}\right) = \left(\frac{2}{97}\right) \left(\frac{3}{97}\right) \left(\frac{7}{97}\right) \) 步骤 2：计算 \( \left(\frac{2}{97}\right) \) 使用特殊值规则。判断 97 模 8 的余数：\( 97 \div 8 = 12 \) 余 \( 1 \)，即 \( 97 \equiv 1 \pmod{8} \)。因为 \( 1 \equiv \pm 1 \pmod{8} \)，所以 \( \left(\frac{2}{97}\right) = 1 \)。步骤 3：计算 \( \left(\frac{3}{97}\right) \) 和 \( \left(\frac{7}{97}\right) \) 使用二次互反律对于 \( \left(\frac{3}{97}\right) \): 因为 3 和 97 都是奇素数，应用二次互反律： \[ \left(\frac{3}{97}\right) \left(\frac{97}{3}\right) = (-1)^{\frac{3-1}{2} \cdot \frac{97-1}{2}} = (-1)^{1 \cdot 48} = 1 \] 所以 \( \left(\frac{3}{97}\right) = \left(\frac{97}{3}\right) \)。现在计算 \( \left(\frac{97}{3}\right) \)。利用周期性，求 97 模 3 的余数：\( 97 \div 3 = 32 \) 余 \( 1 \)，所以 \( \left(\frac{97}{3}\right) = \left(\frac{1}{3}\right) = 1 \)。因此，\( \left(\frac{3}{97}\right) = 1 \)。对于 \( \left(\frac{7}{97}\right) \): 应用二次互反律： \[ \left(\frac{7}{97}\right) \left(\frac{97}{7}\right) = (-1)^{\frac{7-1}{2} \cdot \frac{97-1}{2}} = (-1)^{3 \cdot 48} = 1 \] 所以 \( \left(\frac{7}{97}\right) = \left(\frac{97}{7}\right) \)。计算 \( \left(\frac{97}{7}\right) \)。求 97 模 7 的余数：\( 97 \div 7 = 13 \) 余 \( 6 \)（因为 \( 7 \times 13 = 91, 97-91=6 \)），所以 \( \left(\frac{97}{7}\right) = \left(\frac{6}{7}\right) \)。利用积性分解：\( \left(\frac{6}{7}\right) = \left(\frac{2 \times 3}{7}\right) = \left(\frac{2}{7}\right) \left(\frac{3}{7}\right) \)。计算 \( \left(\frac{2}{7}\right) \): 判断 7 模 8：\( 7 \equiv 7 \pmod{8} \)，而 \( 7 \equiv -1 \pmod{8} \)，属于 \( \pm 1 \)，所以 \( \left(\frac{2}{7}\right) = 1 \)。计算 \( \left(\frac{3}{7}\right) \): 再次应用二次互反律：\( \left(\frac{3}{7}\right) \left(\frac{7}{3}\right) = (-1)^{1 \cdot 3} = -1 \)，所以 \( \left(\frac{3}{7}\right) = -\left(\frac{7}{3}\right) \)。计算 \( \left(\frac{7}{3}\right) \): 7 模 3 余 1，所以 \( \left(\frac{7}{3}\right) = \left(\frac{1}{3}\right) = 1 \)。因此，\( \left(\frac{3}{7}\right) = -1 \)。综合起来，\( \left(\frac{6}{7}\right) = 1 \times (-1) = -1 \)。所以，\( \left(\frac{7}{97}\right) = \left(\frac{97}{7}\right) = \left(\frac{6}{7}\right) = -1 \)。步骤 4：汇总结果 \( \left(\frac{42}{97}\right) = \left(\frac{2}{97}\right) \times \left(\frac{3}{97}\right) \times \left(\frac{7}{97}\right) = 1 \times 1 \times (-1) = -1 \)。结论 : 勒让德符号 \( \left(\frac{42}{97}\right) = -1 \)，这意味着 42 是模奇素数 97 的二次非剩余，方程 \( x^2 \equiv 42 \pmod{97} \) 没有解。通过这个例子，你可以看到勒让德符号如何将复杂的判定问题转化为一个系统性的代数计算过程，这充分体现了其作为数论工具的威力。