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

字数 3525 2025-10-28 08:37:22

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

我们继续深入探讨二次同余方程，这次聚焦于模数为素数幂（即 \(p^k\)）时的解的结构。你已经掌握了模合数情形的解可以通过中国剩余定理分解为模素数幂的情形，因此理解模素数幂的解是彻底解决一般二次同余方程的关键。

第一步：回顾基础——模素数 \(p\) 的解

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

\[x^2 \equiv a \pmod{n} \]

当 \(n = p\) 为奇素数（\(p \ne 2\)）时，我们使用勒让德符号 \(\left( \frac{a}{p} \right)\) 来判断解的存在性：

若 \(\left( \frac{a}{p} \right) = 1\)，则方程有两个不相等的解 \(\pm x_0 \mod p\)。
若 \(p \mid a\)，则方程有唯一解 \(x \equiv 0 \pmod{p}\)（这是一个重根情况）。
若 \(\left( \frac{a}{p} \right) = -1\)，则方程无解。

第二步：引入核心问题——模 \(p^k\) 的解如何从模 \(p\) 的解“提升”而来？

现在考虑模数 \(n = p^k\)，其中 \(p\) 是奇素数，\(k \ge 2\)。核心思想是 亨泽尔引理。这个引理告诉我们，如果模 \(p\) 的解满足某个条件，那么它可以唯一地“提升”为模 \(p^k\) 的解。

具体过程如下：

前提条件：假设 \(x_1\) 是方程 \(f(x) \equiv 0 \pmod{p}\) 的一个解，其中 \(f(x) = x^2 - a\)。
关键条件：计算导数 \(f'(x) = 2x\)。如果 \(f'(x_1) \not\equiv 0 \pmod{p}\)（即 \(p \nmid 2x_1\)），由于 \(p\) 是奇素数且 \(x_1 \not\equiv 0 \pmod{p}\)（因为 \(a \not\equiv 0 \pmod{p}\)），这个条件自动满足。
提升步骤：那么，存在唯一的解 \(x_k \mod p^k\)，使得 \(x_k \equiv x_1 \pmod{p}\)，并且 \(f(x_k) \equiv 0 \pmod{p^k}\)。

第三步：详细讲解亨泽尔引理的“提升”过程

这个过程是迭代的，从模 \(p\) 的解 \(x_1\) 开始，一步步构造出模 \(p^2\)，模 \(p^3\)，...，直到模 \(p^k\) 的解。

假设我们已经有一个解 \(x_n\) 满足 \(f(x_n) \equiv 0 \pmod{p^n}\)。我们想找到一个整数 \(t\)，使得新的数 \(x_{n+1} = x_n + t p^n\) 满足 \(f(x_{n+1}) \equiv 0 \pmod{p^{n+1}}\)。

将 \(f(x_{n+1})\) 在 \(x_n\) 处进行泰勒展开：

\[ f(x_n + t p^n) = f(x_n) + f'(x_n) \cdot t p^n + \dots \]

由于 \(p^{n+1}\) 整除更高阶的项（它们包含 \((p^n)^2 = p^{2n}\)，而 \(2n \ge n+1\) 当 \(n \ge 1\)），所以我们有：

\[ f(x_n + t p^n) \equiv f(x_n) + f'(x_n) \cdot t p^n \pmod{p^{n+1}} \]

我们希望 \(f(x_n + t p^n) \equiv 0 \pmod{p^{n+1}}\)。由于已知 \(f(x_n) \equiv 0 \pmod{p^n}\)，我们可以设 \(f(x_n) = b p^n\)。
于是同余式变为：

\[ b p^n + f'(x_n) \cdot t p^n \equiv 0 \pmod{p^{n+1}} \]

两边同时除以 \(p^n\)（因为模数也除以 \(p^n\)）：

\[ b + f'(x_n) \cdot t \equiv 0 \pmod{p} \]

这是一个关于 \(t\) 的线性同余方程：

\[ f'(x_n) \cdot t \equiv -b \pmod{p} \]

由于我们的前提条件是 \(f'(x_1) \not\equiv 0 \pmod{p}\)，并且 \(x_n \equiv x_1 \pmod{p}\)，所以 \(f'(x_n) \not\equiv 0 \pmod{p}\)。这意味着 \(f'(x_n)\) 在模 \(p\) 下有乘法逆元。因此，这个线性同余方程对 \(t\) 有唯一解模 \(p\)。

\[ t \equiv -b \cdot (f'(x_n))^{-1} \pmod{p} \]

一旦求出 \(t\)，我们就得到了模 \(p^{n+1}\) 下的解 \(x_{n+1} = x_n + t p^n\)。

通过重复这个过程，我们可以将模 \(p\) 的一个解唯一地提升为模任意 \(p^k\) 的一个解。

第四步：总结模 \(p^k\)（\(p\) 为奇素数）的解的结构

基于亨泽尔引理，我们可以完整描述方程 \(x^2 \equiv a \pmod{p^k}\) 的解：

情况 A：\(p \nmid a\)（即 \(a\) 与 \(p\) 互质）
解的存在性取决于模 \(p\) 的情形。
如果 \(\left( \frac{a}{p} \right) = 1\)，即模 \(p\) 下有两个解 \(\pm x_1\)。
那么，根据亨泽尔引理，每个解 \(x_1\) 和 \(-x_1\) 都可以唯一地提升为模 \(p^k\) 下的一个解。因此，模 \(p^k\) 下恰好也有两个解。
如果 \(\left( \frac{a}{p} \right) = -1\)，则模 \(p\) 下无解，模 \(p^k\) 下也无解。
情况 B：\(p \mid a\)（即 \(a\) 是 \(p\) 的倍数）
这种情况比较复杂，需要将方程写为 \(x^2 \equiv p^m \cdot c \pmod{p^k}\)，其中 \(p \nmid c\)，\(m \ge 1\)。解的存在性取决于指数 \(m\) 和 \(k\) 的关系。例如：
如果 \(m \ge k\)，那么方程变为 \(x^2 \equiv 0 \pmod{p^k}\)，解是所有满足 \(p^{\lceil k/2 \rceil} \mid x\) 的 \(x\)。
如果 \(m < k\) 且 \(m\) 是偶数，比如 \(m=2t\)，则方程可化为 \((x/p^t)^2 \equiv c \pmod{p^{k-2t}}\)，转化为情况 A 来求解。
如果 \(m < k\) 且 \(m\) 是奇数，则方程无解。

第五步：简要说明模 \(2^k\) 的特殊性

模数为 2 的幂次时，情况更为特殊，因为亨泽尔引理要求 \(f'(x_1) \not\equiv 0 \pmod{2}\)，而 \(f'(x) = 2x \equiv 0 \pmod{2}\) 总是成立，所以标准亨泽尔引理不适用。模 \(2^k\) 的解需要单独分析，其结构规律与奇素数模幂不同，解的数量可能是 1, 2, 4 个或者无解。

结论

对于奇素数 \(p\)，二次同余方程 \(x^2 \equiv a \pmod{p^k}\) 的解的结构清晰地由模 \(p\) 的情形决定（当 \(p \nmid a\) 时）。亨泽尔引理提供了一个强大的迭代方法，将模 \(p\) 的解“提升”到更高的模数，这不仅是解决二次同余方程的关键，也是处理许多多项式同余问题的通用工具。结合你已学过的中国剩余定理，你现在已经具备了求解任意模数 \(n\) 的二次同余方程的完整理论框架。

二次同余方程与素数模幂的解的结构我们继续深入探讨二次同余方程，这次聚焦于模数为素数幂（即 \( p^k \)）时的解的结构。你已经掌握了模合数情形的解可以通过中国剩余定理分解为模素数幂的情形，因此理解模素数幂的解是彻底解决一般二次同余方程的关键。第一步：回顾基础——模素数 \( p \) 的解一个二次同余方程的一般形式为： \[ x^2 \equiv a \pmod{n} \] 当 \( n = p \) 为奇素数（\( p \ne 2 \)）时，我们使用勒让德符号 \( \left( \frac{a}{p} \right) \) 来判断解的存在性：若 \( \left( \frac{a}{p} \right) = 1 \)，则方程有两个不相等的解 \( \pm x_ 0 \mod p \)。若 \( p \mid a \)，则方程有唯一解 \( x \equiv 0 \pmod{p} \)（这是一个重根情况）。若 \( \left( \frac{a}{p} \right) = -1 \)，则方程无解。第二步：引入核心问题——模 \( p^k \) 的解如何从模 \( p \) 的解“提升”而来？现在考虑模数 \( n = p^k \)，其中 \( p \) 是奇素数，\( k \ge 2 \)。核心思想是亨泽尔引理。这个引理告诉我们，如果模 \( p \) 的解满足某个条件，那么它可以唯一地“提升”为模 \( p^k \) 的解。具体过程如下：前提条件：假设 \( x_ 1 \) 是方程 \( f(x) \equiv 0 \pmod{p} \) 的一个解，其中 \( f(x) = x^2 - a \)。关键条件：计算导数 \( f'(x) = 2x \)。如果 \( f'(x_ 1) \not\equiv 0 \pmod{p} \)（即 \( p \nmid 2x_ 1 \)），由于 \( p \) 是奇素数且 \( x_ 1 \not\equiv 0 \pmod{p} \)（因为 \( a \not\equiv 0 \pmod{p} \)），这个条件自动满足。提升步骤：那么，存在唯一的解 \( x_ k \mod p^k \)，使得 \( x_ k \equiv x_ 1 \pmod{p} \)，并且 \( f(x_ k) \equiv 0 \pmod{p^k} \)。第三步：详细讲解亨泽尔引理的“提升”过程这个过程是迭代的，从模 \( p \) 的解 \( x_ 1 \) 开始，一步步构造出模 \( p^2 \)，模 \( p^3 \)，...，直到模 \( p^k \) 的解。假设我们已经有一个解 \( x_ n \) 满足 \( f(x_ n) \equiv 0 \pmod{p^n} \)。我们想找到一个整数 \( t \)，使得新的数 \( x_ {n+1} = x_ n + t p^n \) 满足 \( f(x_ {n+1}) \equiv 0 \pmod{p^{n+1}} \)。将 \( f(x_ {n+1}) \) 在 \( x_ n \) 处进行泰勒展开： \[ f(x_ n + t p^n) = f(x_ n) + f'(x_ n) \cdot t p^n + \dots \] 由于 \( p^{n+1} \) 整除更高阶的项（它们包含 \( (p^n)^2 = p^{2n} \)，而 \( 2n \ge n+1 \) 当 \( n \ge 1 \)），所以我们有： \[ f(x_ n + t p^n) \equiv f(x_ n) + f'(x_ n) \cdot t p^n \pmod{p^{n+1}} \] 我们希望 \( f(x_ n + t p^n) \equiv 0 \pmod{p^{n+1}} \)。由于已知 \( f(x_ n) \equiv 0 \pmod{p^n} \)，我们可以设 \( f(x_ n) = b p^n \)。于是同余式变为： \[ b p^n + f'(x_ n) \cdot t p^n \equiv 0 \pmod{p^{n+1}} \] 两边同时除以 \( p^n \)（因为模数也除以 \( p^n \)）： \[ b + f'(x_ n) \cdot t \equiv 0 \pmod{p} \] 这是一个关于 \( t \) 的线性同余方程： \[ f'(x_ n) \cdot t \equiv -b \pmod{p} \] 由于我们的前提条件是 \( f'(x_ 1) \not\equiv 0 \pmod{p} \)，并且 \( x_ n \equiv x_ 1 \pmod{p} \)，所以 \( f'(x_ n) \not\equiv 0 \pmod{p} \)。这意味着 \( f'(x_ n) \) 在模 \( p \) 下有乘法逆元。因此，这个线性同余方程对 \( t \) 有唯一解模 \( p \)。 \[ t \equiv -b \cdot (f'(x_ n))^{-1} \pmod{p} \] 一旦求出 \( t \)，我们就得到了模 \( p^{n+1} \) 下的解 \( x_ {n+1} = x_ n + t p^n \)。通过重复这个过程，我们可以将模 \( p \) 的一个解唯一地提升为模任意 \( p^k \) 的一个解。第四步：总结模 \( p^k \)（\( p \) 为奇素数）的解的结构基于亨泽尔引理，我们可以完整描述方程 \( x^2 \equiv a \pmod{p^k} \) 的解：情况 A：\( p \nmid a \)（即 \( a \) 与 \( p \) 互质）解的存在性取决于模 \( p \) 的情形。如果 \( \left( \frac{a}{p} \right) = 1 \)，即模 \( p \) 下有两个解 \( \pm x_ 1 \)。那么，根据亨泽尔引理，每个解 \( x_ 1 \) 和 \( -x_ 1 \) 都可以唯一地提升为模 \( p^k \) 下的一个解。因此，模 \( p^k \) 下恰好也有两个解。如果 \( \left( \frac{a}{p} \right) = -1 \)，则模 \( p \) 下无解，模 \( p^k \) 下也无解。情况 B：\( p \mid a \)（即 \( a \) 是 \( p \) 的倍数）这种情况比较复杂，需要将方程写为 \( x^2 \equiv p^m \cdot c \pmod{p^k} \)，其中 \( p \nmid c \)，\( m \ge 1 \)。解的存在性取决于指数 \( m \) 和 \( k \) 的关系。例如：如果 \( m \ge k \)，那么方程变为 \( x^2 \equiv 0 \pmod{p^k} \)，解是所有满足 \( p^{\lceil k/2 \rceil} \mid x \) 的 \( x \)。如果 \( m < k \) 且 \( m \) 是偶数，比如 \( m=2t \)，则方程可化为 \( (x/p^t)^2 \equiv c \pmod{p^{k-2t}} \)，转化为情况 A 来求解。如果 \( m < k \) 且 \( m \) 是奇数，则方程无解。第五步：简要说明模 \( 2^k \) 的特殊性模数为 2 的幂次时，情况更为特殊，因为亨泽尔引理要求 \( f'(x_ 1) \not\equiv 0 \pmod{2} \)，而 \( f'(x) = 2x \equiv 0 \pmod{2} \) 总是成立，所以标准亨泽尔引理不适用。模 \( 2^k \) 的解需要单独分析，其结构规律与奇素数模幂不同，解的数量可能是 1, 2, 4 个或者无解。结论对于奇素数 \( p \)，二次同余方程 \( x^2 \equiv a \pmod{p^k} \) 的解的结构清晰地由模 \( p \) 的情形决定（当 \( p \nmid a \) 时）。亨泽尔引理提供了一个强大的迭代方法，将模 \( p \) 的解“提升”到更高的模数，这不仅是解决二次同余方程的关键，也是处理许多多项式同余问题的通用工具。结合你已学过的中国剩余定理，你现在已经具备了求解任意模数 \( n \) 的二次同余方程的完整理论框架。