二次同余方程与素数模幂的解的结构

字数 2450 2025-10-28 00:41:32

二次同余方程与素数模幂的解的结构

我们继续深入探讨二次同余方程，这次聚焦于模数是素数幂（即 \(p^k\)）时的解的结构。你已经了解了模素数 \(p\) 的情况，以及如何利用中国剩余定理处理模合数。模素数幂是连接这两者的关键桥梁。

第一步：回顾基础——模素数 \(p\) 的二次同余方程

一个二次同余方程的一般形式为：

\[ ax^2 + bx + c \equiv 0 \pmod{n} \]

当 \(n = p\) 是一个奇素数（\(p \neq 2\)）时，我们可以通过配方等方法将其简化，并利用勒让德符号来判断解的存在性。我们已经知道，对于模素数 \(p\)，一个二次同余方程要么无解，要么恰好有两个不同的解（当 \(p \mid a\) 等特殊情况除外，我们通常考虑 \(p \nmid a\) 的情形）。

第二步：提出问题——模素数幂 \(p^k\) 会有什么不同？

现在，我们考虑模数 \(n = p^k\)，其中 \(p\) 是一个奇素数，\(k > 1\)。
方程变为：

\[ x^2 \equiv a \pmod{p^k} \]

（这里我们讨论最简形式 \(x^2 \equiv a \pmod{p^k}\)，因为它揭示了核心结构。更一般的方程可以通过变换归结为此类。）

一个自然的问题是：如果这个方程在模 \(p^k\) 下有解，那么这些解与它在模 \(p\) 下的解有什么关系？解的数量会是多少？

第三步：核心定理——亨泽尔引理（Hensel's Lemma）

亨泽尔引理是解决这个问题的强大工具。它告诉我们，在特定条件下，模 \(p\) 的一个解可以“提升”为模 \(p^k\) 的一个解。

定理（亨泽尔引理，适用于二次同余方程）：
设 \(p\) 是一个奇素数，\(a\) 是一个整数，且 \(p \nmid a\)。考虑同余方程 \(f(x) = x^2 - a \equiv 0 \pmod{p^k}\)。
假设 \(x_1\) 是方程在模 \(p\) 下的一个解，即 \(f(x_1) \equiv 0 \pmod{p}\)。
那么：

这个解 \(x_1\) 可以唯一地“提升”为模 \(p^k\) 下的一个解，当且仅当 \(f'(x_1) \not\equiv 0 \pmod{p}\)。

这里 \(f'(x) = 2x\) 是 \(f(x)\) 的导数。
条件 \(f'(x_1) \not\equiv 0 \pmod{p}\) 等价于 \(p \nmid 2x_1\)。由于 \(p\) 是奇素数且 \(p \nmid a\) (从而 \(p \nmid x_1\))，这个条件自动满足。

提升过程是迭代的：

我们从模 \(p\) 的解 \(x_1\) 开始。
我们寻找一个数 \(t\)，使得新的解 \(x_2 = x_1 + p t\) 满足 \(f(x_2) \equiv 0 \pmod{p^2}\)。
这个 \(t\) 可以通过解一个简单的线性同余方程 \(f'(x_1) t \equiv -f(x_1)/p \pmod{p}\) 得到。由于 \(f'(x_1)\) 在模 \(p\) 下可逆，\(t\) 是唯一确定的。
然后，我们再用 \(x_2\) 去寻找模 \(p^3\) 的解 \(x_3 = x_2 + p^2 t_2\)，依此类推，直到提升到模 \(p^k\)。

第四步：解的结构——从模 \(p\) 到模 \(p^k\)

基于亨泽尔引理，我们可以清晰地描述解的结构：

解的存在性：方程 \(x^2 \equiv a \pmod{p^k}\) 有解，当且仅当 方程 \(x^2 \equiv a \pmod{p}\) 有解。也就是说，\(a\) 是模 \(p^k\) 的二次剩余，当且仅当它是模 \(p\) 的二次剩余（即勒让德符号 \((a/p) = 1\)）。
解的数量：如果方程 \(x^2 \equiv a \pmod{p^k}\) 有解，那么它恰好有 两个解。

推理：方程 \(x^2 \equiv a \pmod{p}\) 有两个不同的解，记作 \(x \equiv \pm r \pmod{p}\)。
根据亨泽尔引理，每个解 \(r\) 和 \(-r\) 都可以唯一地提升为模 \(p^k\) 的一个解。我们得到两个模 \(p^k\) 的解，记作 \(x \equiv \pm s \pmod{p^k}\)。
这两个解在模 \(p^k\) 下是不同的，因为如果 \(s \equiv -s \pmod{p^k}\)，则 \(2s \equiv 0 \pmod{p^k}\)，但由于 \(p\) 是奇素数且 \(p \nmid s\)，这是不可能的。

总结

对于奇素数 \(p\) 和整数 \(k \ge 1\)，二次同余方程 \(x^2 \equiv a \pmod{p^k}\)（其中 \(p \nmid a\)）的解的结构非常规整：

存在性 完全由模 \(p\) 的情形决定。
数量恒为 2。
关系模 \(p^k\) 的解是模 \(p\) 的解通过亨泽尔引理“提升”得到的。每个模 \(p\) 的解唯一地对应一个模 \(p^k\) 的解。

这个优美的结论，结合中国剩余定理，就构成了求解模任意合数的二次同余方程的一般方法的基础：先将模数分解为素数幂，再分别求解每个素数幂模下的方程（利用亨泽尔引理），最后用中国剩余定理组合这些解。

二次同余方程与素数模幂的解的结构我们继续深入探讨二次同余方程，这次聚焦于模数是素数幂（即 \( p^k \)）时的解的结构。你已经了解了模素数 \( p \) 的情况，以及如何利用中国剩余定理处理模合数。模素数幂是连接这两者的关键桥梁。第一步：回顾基础——模素数 \( p \) 的二次同余方程一个二次同余方程的一般形式为： \[ ax^2 + bx + c \equiv 0 \pmod{n} \] 当 \( n = p \) 是一个奇素数（\( p \neq 2 \)）时，我们可以通过配方等方法将其简化，并利用勒让德符号来判断解的存在性。我们已经知道，对于模素数 \( p \)，一个二次同余方程要么无解，要么恰好有两个不同的解（当 \( p \mid a \) 等特殊情况除外，我们通常考虑 \( p \nmid a \) 的情形）。第二步：提出问题——模素数幂 \( p^k \) 会有什么不同？现在，我们考虑模数 \( n = p^k \)，其中 \( p \) 是一个奇素数，\( k > 1 \)。方程变为： \[ x^2 \equiv a \pmod{p^k} \] （这里我们讨论最简形式 \( x^2 \equiv a \pmod{p^k} \)，因为它揭示了核心结构。更一般的方程可以通过变换归结为此类。）一个自然的问题是：如果这个方程在模 \( p^k \) 下有解，那么这些解与它在模 \( p \) 下的解有什么关系？解的数量会是多少？第三步：核心定理——亨泽尔引理（Hensel's Lemma）亨泽尔引理是解决这个问题的强大工具。它告诉我们，在特定条件下，模 \( p \) 的一个解可以“提升”为模 \( p^k \) 的一个解。定理（亨泽尔引理，适用于二次同余方程）：设 \( p \) 是一个奇素数，\( a \) 是一个整数，且 \( p \nmid a \)。考虑同余方程 \( f(x) = x^2 - a \equiv 0 \pmod{p^k} \)。假设 \( x_ 1 \) 是方程在模 \( p \) 下的一个解，即 \( f(x_ 1) \equiv 0 \pmod{p} \)。那么：这个解 \( x_ 1 \) 可以唯一地 “提升”为模 \( p^k \) 下的一个解，当且仅当 \( f'(x_ 1) \not\equiv 0 \pmod{p} \)。这里 \( f'(x) = 2x \) 是 \( f(x) \) 的导数。条件 \( f'(x_ 1) \not\equiv 0 \pmod{p} \) 等价于 \( p \nmid 2x_ 1 \)。由于 \( p \) 是奇素数且 \( p \nmid a \) (从而 \( p \nmid x_ 1 \))，这个条件自动满足。提升过程是迭代的：我们从模 \( p \) 的解 \( x_ 1 \) 开始。我们寻找一个数 \( t \)，使得新的解 \( x_ 2 = x_ 1 + p t \) 满足 \( f(x_ 2) \equiv 0 \pmod{p^2} \)。这个 \( t \) 可以通过解一个简单的线性同余方程 \( f'(x_ 1) t \equiv -f(x_ 1)/p \pmod{p} \) 得到。由于 \( f'(x_ 1) \) 在模 \( p \) 下可逆，\( t \) 是唯一确定的。然后，我们再用 \( x_ 2 \) 去寻找模 \( p^3 \) 的解 \( x_ 3 = x_ 2 + p^2 t_ 2 \)，依此类推，直到提升到模 \( p^k \)。第四步：解的结构——从模 \( p \) 到模 \( p^k \) 基于亨泽尔引理，我们可以清晰地描述解的结构：解的存在性：方程 \( x^2 \equiv a \pmod{p^k} \) 有解，当且仅当方程 \( x^2 \equiv a \pmod{p} \) 有解。也就是说，\( a \) 是模 \( p^k \) 的二次剩余，当且仅当它是模 \( p \) 的二次剩余（即勒让德符号 \( (a/p) = 1 \)）。解的数量：如果方程 \( x^2 \equiv a \pmod{p^k} \) 有解，那么它恰好有两个解。推理：方程 \( x^2 \equiv a \pmod{p} \) 有两个不同的解，记作 \( x \equiv \pm r \pmod{p} \)。根据亨泽尔引理，每个解 \( r \) 和 \( -r \) 都可以唯一地提升为模 \( p^k \) 的一个解。我们得到两个模 \( p^k \) 的解，记作 \( x \equiv \pm s \pmod{p^k} \)。这两个解在模 \( p^k \) 下是不同的，因为如果 \( s \equiv -s \pmod{p^k} \)，则 \( 2s \equiv 0 \pmod{p^k} \)，但由于 \( p \) 是奇素数且 \( p \nmid s \)，这是不可能的。总结对于奇素数 \( p \) 和整数 \( k \ge 1 \)，二次同余方程 \( x^2 \equiv a \pmod{p^k} \)（其中 \( p \nmid a \)）的解的结构非常规整：存在性完全由模 \( p \) 的情形决定。数量恒为 2。关系模 \( p^k \) 的解是模 \( p \) 的解通过亨泽尔引理“提升”得到的。每个模 \( p \) 的解唯一地对应一个模 \( p^k \) 的解。这个优美的结论，结合中国剩余定理，就构成了求解模任意合数的二次同余方程的一般方法的基础：先将模数分解为素数幂，再分别求解每个素数幂模下的方程（利用亨泽尔引理），最后用中国剩余定理组合这些解。