高次同余方程的解的结构

字数 5076 2025-12-08 15:28:41

高次同余方程的解的结构

我们先从最基础的同余概念出发。你已经知道“同余”是数论的核心概念，用符号 \(a \equiv b \pmod{m}\) 表示 \(m\) 整除 \(a-b\)。而“同余方程”则是形如 \(f(x) \equiv 0 \pmod{m}\) 的方程，其中 \(f(x)\) 是一个多项式。你已经了解过“一次同余方程”（即线性同余方程）的解法，以及“二次同余方程”的详细结构。今天，我们探讨更一般的情形：高次同余方程，即多项式的次数 \(n \ge 3\) 时的解的性质与求解策略。

第一步：高次同余方程与模的简化（中国剩余定理的应用）

一个基本而强大的工具是“中国剩余定理”。假设模数 \(m\) 有素幂分解 \(m = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\)。求解 \(f(x) \equiv 0 \pmod{m}\) 等价于求解方程组：

\[f(x) \equiv 0 \pmod{p_i^{e_i}}, \quad i = 1, 2, \dots, k \]

对每个同余方程求出解后，再利用中国剩余定理将这些解“拼接”成模 \(m\) 的解。因此，求解高次同余方程的核心，归结为求解模为素数幂 \(p^e\) 的同余方程。我们通常从最简单的模素数 \(p\) 开始。

第二步：模素数 \(p\) 的高次同余方程

考虑 \(f(x) \equiv 0 \pmod{p}\)，其中 \(p\) 是素数，\(f(x)\) 是整系数多项式，次数为 \(n\)。这里的关键点是，在模 \(p\) 的剩余系 \(\mathbb{F}_p = \{0, 1, \dots, p-1\}\) 中，费马小定理 \(a^{p-1} \equiv 1 \pmod{p}\)（当 \(a \not\equiv 0\) 时）成立。这意味着在 \(\mathbb{F}_p\) 上，多项式 \(x^p - x\) 的根恰好是全部 \(p\) 个元素。因此，我们有重要的多项式恒等同余：

\[x^p - x \equiv x(x-1)(x-2)\cdots(x-(p-1)) \pmod{p}. \]

这提示我们，任何多项式 \(f(x)\) 模 \(p\) 都可以用“带余除法”的思想处理。更具体地，有拉格朗日定理：模素数 \(p\) 的 \(n\) 次同余方程 \(f(x) \equiv 0 \pmod{p}\) 至多有 \(n\) 个互不同余的解（在 \(\mathbb{F}_p\) 中）。证明思路是：如果 \(f(a) \equiv 0 \pmod{p}\)，那么多项式 \(f(x)\) 可以分解出因子 \((x-a)\)，然后对次数做归纳。这个结论与复数域上的代数基本定理在形式上类似，但只给出了解数的上界，实际解数可能小于 \(n\)。

第三步：解的提升：从模 \(p\) 到模 \(p^e\) (亨泽尔引理)

这是求解高次同余方程最核心的技巧，称为亨泽尔引理。它允许我们将模 \(p\) 的解“提升”为模 \(p^2, p^3, \dots, p^e\) 的解。我们分两种情况讨论。

简单根的情况（亨泽尔引理的标准形式）：
假设我们已经找到一个模 \(p\) 的解 \(r\)，即 \(f(r) \equiv 0 \pmod{p}\)，并且满足导数值条件 \(f'(r) \not\equiv 0 \pmod{p}\)。那么，这个解可以唯一地提升为模 \(p^e\) 的解。具体算法是迭代的：

假设已有解 \(x_k\) 满足 \(f(x_k) \equiv 0 \pmod{p^k}\)。
我们寻找形如 \(x_{k+1} = x_k + t p^k\) 的解，其中 \(t\) 是待定的整数，\(0 \le t < p\)。
将 \(f(x_{k+1})\) 在 \(x_k\) 处做泰勒展开（模 \(p^{k+1}\) 下有效）：

\[ f(x_k + t p^k) \equiv f(x_k) + f'(x_k) \cdot t p^k \pmod{p^{k+1}}. \]

因为我们有 \(f(x_k) \equiv 0 \pmod{p^k}\)，可设 \(f(x_k) = A p^k\)。方程 \(f(x_{k+1}) \equiv 0 \pmod{p^{k+1}}\) 变为：

\[ A p^k + f'(x_k) t p^k \equiv 0 \pmod{p^{k+1}} \quad \Rightarrow \quad A + f'(x_k) t \equiv 0 \pmod{p}. \]

由于 \(f'(x_k) \equiv f'(r) \not\equiv 0 \pmod{p}\)，这个关于 \(t\) 的一次同余方程在模 \(p\) 下有唯一解。解出 \(t\)，就得到了模 \(p^{k+1}\) 的解 \(x_{k+1}\)。
通过这个迭代过程，我们可以从模 \(p\) 的解 \(r\) 出发，逐步构造出模任意 \(p^e\) 的唯一解（在同余意义下）。

重根的情况：
如果 \(f'(r) \equiv 0 \pmod{p}\)，情况就复杂得多。此时，解 \(r\) 被称为“非简单根”或“重根”。提升可能失败，也可能成功，但未必唯一。具体分析需要看 \(f(r)\) 被 \(p\) 整除的“阶数”：

设 \(f(r) \equiv 0 \pmod{p^m}\)，但 \(f(r) \not\equiv 0 \pmod{p^{m+1}}\)（即 \(p^m\) 恰好整除 \(f(r)\)）。
将 \(x = r + t p^k\) 代入，通过分析泰勒展开式，可以得出：只有当 \(m \ge 2k\) 时，解才可能从模 \(p^k\) 提升到模 \(p^{k+1}\)。这通常意味着，如果 \(f(r)\) 被 \(p\) 整除的幂次足够高，那么即使导数为零，解也可能有多个提升分支，或者根本不能提升。

第四步：高次同余方程解的结构总结与示例

综合以上，对于模 \(m\) 的高次同余方程 \(f(x) \equiv 0 \pmod{m}\)，其解的结构可以通过以下步骤确定：

分解模数：将 \(m\) 分解为素幂的乘积 \(m = \prod p_i^{e_i}\)。
对每个素因子 \(p_i\)：
a. 求解模 \(p_i\) 的方程 \(f(x) \equiv 0 \pmod{p_i}\)，找出所有解（最多 \(n\) 个）。
b. 对每个模 \(p_i\) 的解，尝试使用亨泽尔引理将其提升为模 \(p_i^{e_i}\) 的解。如果 \(f'(r) \not\equiv 0 \pmod{p_i}\)，则存在唯一的提升解。如果是重根，则需具体分析提升条件。
c. 得到模 \(p_i^{e_i}\) 下的全部解集 \(S_i\)。
合成模 \(m\) 的解：对于从每个解集 \(S_i\) 中各取一个解，利用中国剩余定理组合成一个模 \(m\) 的解。所有可能的组合构成了原方程的全部解。

示例：求解 \(x^3 + 2x + 6 \equiv 0 \pmod{125}\)。这里 \(125 = 5^3\)。

先解模 \(5\)：\(f(x)=x^3+2x+6 \pmod{5}\)。尝试 \(x=0,1,2,3,4\)，发现 \(f(2)=8+4+6=18 \equiv 3 \pmod{5}\)，\(f(3)=27+6+6=39 \equiv 4 \pmod{5}\)，而 \(f(4)=64+8+6=78 \equiv 3 \pmod{5}\)。等等，我们再算一遍：\(f(0)=6\equiv1\), \(f(1)=1+2+6=9\equiv4\), \(f(2)=8+4+6=18\equiv3\), \(f(3)=27+6+6=39\equiv4\), \(f(4)=64+8+6=78\equiv3\)。模5下无解。所以模125下也无解。这说明模素数无解是整个方程无解的充分条件。

另一个示例：求解 \(x^3 + x + 1 \equiv 0 \pmod{25}\)。模5下：\(f(0)=1\), \(f(1)=3\), \(f(2)=8+2+1=11\equiv1\), \(f(3)=27+3+1=31\equiv1\), \(f(4)=64+4+1=69\equiv4\)。发现 \(f(2)\equiv1\pmod5\)，等等，我算错了，重算：\(f(2)=2^3+2+1=8+2+1=11\equiv1\pmod5\)，确实非零。等等，我再仔细找：\(f(0)=1\), \(f(1)=1+1+1=3\), \(f(2)=8+2+1=11\equiv1\), \(f(3)=27+3+1=31\equiv1\), \(f(4)=64+4+1=69\equiv4\)。确实模5下无解。但已知 \(x=2\) 是模5的一个解吗？不，\(f(2)\equiv1\not\equiv0\)。我犯错了。我们换一个多项式：考虑 \(x^3 + 2x + 1 \equiv 0 \pmod{25}\)。模5下：\(f(0)=1\), \(f(1)=1+2+1=4\), \(f(2)=8+4+1=13\equiv3\), \(f(3)=27+6+1=34\equiv4\), \(f(4)=64+8+1=73\equiv3\)。还是无解。看来我举的例子不好。我们换一个已知有模5解的例子。

正确示例：求解 \(f(x) = x^3 + 2x + 6 \equiv 0 \pmod{25}\)。但我们刚才发现它模5无解。这不行。
修正：让我们用 \(f(x)=x^3 + 4x + 1\)。模5下：\(f(0)=1\), \(f(1)=1+4+1=6\equiv1\), \(f(2)=8+8+1=17\equiv2\), \(f(3)=27+12+1=40\equiv0\), \(f(4)=64+16+1=81\equiv1\)。太好了，\(r=3\) 是模5的解，且 \(f'(x)=3x^2+4\)，所以 \(f'(3)=3*9+4=27+4=31\equiv1 \not\equiv0\pmod5\)，满足亨泽尔引理条件。

从模5提升到模25：设 \(x_1 = 3\)。计算 \(f(3)=3^3+4*3+1=27+12+1=40\)，所以 \(A = f(3)/5 = 40/5 = 8\)。计算 \(f'(3)=31\)，在模5下 \(f'(3) \equiv 1\)。我们需要解同余方程：\(A + f'(3) t \equiv 0 \pmod{5}\)，即 \(8 + 1 \cdot t \equiv 0 \pmod{5}\)，即 \(t+3\equiv0\pmod5\)，所以 \(t\equiv2\pmod5\)。取 \(t=2\)，则 \(x_2 = x_1 + t*5 = 3 + 2*5 = 13\)。验证：\(f(13)=13^3+4*13+1=2197+52+1=2250\)，而 \(2250/25=90\)，能被25整除，正确。所以模25下的一个解是 \(x \equiv 13 \pmod{25}\)。
亨泽尔引理保证这是从 \(r=3\) 提升的唯一解。另外，我们还需要检查模5下是否还有其他解。我们已验证了0,1,2,4均非解，所以模5下只有 \(r=3\) 这一个解。因此，原方程 \(x^3+4x+1\equiv0\pmod{25}\) 的唯一解是 \(x \equiv 13 \pmod{25}\)。

通过这个例子，你可以清晰地看到，求解高次同余方程的过程是一个“化归”过程：通过中国剩余定理化归到模素数幂，再通过亨泽尔引理化归到模素数。其结构的清晰性，依赖于模素数的域结构（有至多n个解）和牛顿迭代法在p进数中的类比（亨泽尔引理）。理解这个结构，是研究更深的p进分析和代数数论中局部域上多项式方程解的基础。

高次同余方程的解的结构我们先从最基础的同余概念出发。你已经知道“同余”是数论的核心概念，用符号 \(a \equiv b \pmod{m}\) 表示 \(m\) 整除 \(a-b\)。而“同余方程”则是形如 \(f(x) \equiv 0 \pmod{m}\) 的方程，其中 \(f(x)\) 是一个多项式。你已经了解过“一次同余方程”（即线性同余方程）的解法，以及“二次同余方程”的详细结构。今天，我们探讨更一般的情形：高次同余方程，即多项式的次数 \(n \ge 3\) 时的解的性质与求解策略。第一步：高次同余方程与模的简化（中国剩余定理的应用）一个基本而强大的工具是“中国剩余定理”。假设模数 \(m\) 有素幂分解 \(m = p_ 1^{e_ 1} p_ 2^{e_ 2} \cdots p_ k^{e_ k}\)。求解 \(f(x) \equiv 0 \pmod{m}\) 等价于求解方程组： \[ f(x) \equiv 0 \pmod{p_ i^{e_ i}}, \quad i = 1, 2, \dots, k \] 对每个同余方程求出解后，再利用中国剩余定理将这些解“拼接”成模 \(m\) 的解。因此，求解高次同余方程的核心，归结为求解模为素数幂 \(p^e\) 的同余方程。我们通常从最简单的模素数 \(p\) 开始。第二步：模素数 \(p\) 的高次同余方程考虑 \(f(x) \equiv 0 \pmod{p}\)，其中 \(p\) 是素数，\(f(x)\) 是整系数多项式，次数为 \(n\)。这里的关键点是，在模 \(p\) 的剩余系 \(\mathbb{F}_ p = \{0, 1, \dots, p-1\}\) 中，费马小定理 \(a^{p-1} \equiv 1 \pmod{p}\)（当 \(a \not\equiv 0\) 时）成立。这意味着在 \(\mathbb{F}_ p\) 上，多项式 \(x^p - x\) 的根恰好是全部 \(p\) 个元素。因此，我们有重要的多项式恒等同余： \[ x^p - x \equiv x(x-1)(x-2)\cdots(x-(p-1)) \pmod{p}. \] 这提示我们，任何多项式 \(f(x)\) 模 \(p\) 都可以用“带余除法”的思想处理。更具体地，有拉格朗日定理：模素数 \(p\) 的 \(n\) 次同余方程 \(f(x) \equiv 0 \pmod{p}\) 至多有 \(n\) 个互不同余的解（在 \(\mathbb{F}_ p\) 中）。证明思路是：如果 \(f(a) \equiv 0 \pmod{p}\)，那么多项式 \(f(x)\) 可以分解出因子 \((x-a)\)，然后对次数做归纳。这个结论与复数域上的代数基本定理在形式上类似，但只给出了解数的上界，实际解数可能小于 \(n\)。第三步：解的提升：从模 \(p\) 到模 \(p^e\) (亨泽尔引理) 这是求解高次同余方程最核心的技巧，称为亨泽尔引理。它允许我们将模 \(p\) 的解“提升”为模 \(p^2, p^3, \dots, p^e\) 的解。我们分两种情况讨论。简单根的情况（亨泽尔引理的标准形式）：假设我们已经找到一个模 \(p\) 的解 \(r\)，即 \(f(r) \equiv 0 \pmod{p}\)，并且满足导数值条件 \(f'(r) \not\equiv 0 \pmod{p}\)。那么，这个解可以唯一地提升为模 \(p^e\) 的解。具体算法是迭代的：假设已有解 \(x_ k\) 满足 \(f(x_ k) \equiv 0 \pmod{p^k}\)。我们寻找形如 \(x_ {k+1} = x_ k + t p^k\) 的解，其中 \(t\) 是待定的整数，\(0 \le t < p\)。将 \(f(x_ {k+1})\) 在 \(x_ k\) 处做泰勒展开（模 \(p^{k+1}\) 下有效）： \[ f(x_ k + t p^k) \equiv f(x_ k) + f'(x_ k) \cdot t p^k \pmod{p^{k+1}}. \] 因为我们有 \(f(x_ k) \equiv 0 \pmod{p^k}\)，可设 \(f(x_ k) = A p^k\)。方程 \(f(x_ {k+1}) \equiv 0 \pmod{p^{k+1}}\) 变为： \[ A p^k + f'(x_ k) t p^k \equiv 0 \pmod{p^{k+1}} \quad \Rightarrow \quad A + f'(x_ k) t \equiv 0 \pmod{p}. \] 由于 \(f'(x_ k) \equiv f'(r) \not\equiv 0 \pmod{p}\)，这个关于 \(t\) 的一次同余方程在模 \(p\) 下有唯一解。解出 \(t\)，就得到了模 \(p^{k+1}\) 的解 \(x_ {k+1}\)。通过这个迭代过程，我们可以从模 \(p\) 的解 \(r\) 出发，逐步构造出模任意 \(p^e\) 的唯一解（在同余意义下）。重根的情况：如果 \(f'(r) \equiv 0 \pmod{p}\)，情况就复杂得多。此时，解 \(r\) 被称为“非简单根”或“重根”。提升可能失败，也可能成功，但未必唯一。具体分析需要看 \(f(r)\) 被 \(p\) 整除的“阶数”：设 \(f(r) \equiv 0 \pmod{p^m}\)，但 \(f(r) \not\equiv 0 \pmod{p^{m+1}}\)（即 \(p^m\) 恰好整除 \(f(r)\)）。将 \(x = r + t p^k\) 代入，通过分析泰勒展开式，可以得出：只有当 \(m \ge 2k\) 时，解才可能从模 \(p^k\) 提升到模 \(p^{k+1}\)。这通常意味着，如果 \(f(r)\) 被 \(p\) 整除的幂次足够高，那么即使导数为零，解也可能有多个提升分支，或者根本不能提升。第四步：高次同余方程解的结构总结与示例综合以上，对于模 \(m\) 的高次同余方程 \(f(x) \equiv 0 \pmod{m}\)，其解的结构可以通过以下步骤确定：分解模数：将 \(m\) 分解为素幂的乘积 \(m = \prod p_ i^{e_ i}\)。对每个素因子 \(p_ i\) ： a. 求解模 \(p_ i\) 的方程 \(f(x) \equiv 0 \pmod{p_ i}\)，找出所有解（最多 \(n\) 个）。 b. 对每个模 \(p_ i\) 的解，尝试使用亨泽尔引理将其提升为模 \(p_ i^{e_ i}\) 的解。如果 \(f'(r) \not\equiv 0 \pmod{p_ i}\)，则存在唯一的提升解。如果是重根，则需具体分析提升条件。 c. 得到模 \(p_ i^{e_ i}\) 下的全部解集 \(S_ i\)。合成模 \(m\) 的解：对于从每个解集 \(S_ i\) 中各取一个解，利用中国剩余定理组合成一个模 \(m\) 的解。所有可能的组合构成了原方程的全部解。示例：求解 \(x^3 + 2x + 6 \equiv 0 \pmod{125}\)。这里 \(125 = 5^3\)。先解模 \(5\)：\(f(x)=x^3+2x+6 \pmod{5}\)。尝试 \(x=0,1,2,3,4\)，发现 \(f(2)=8+4+6=18 \equiv 3 \pmod{5}\)，\(f(3)=27+6+6=39 \equiv 4 \pmod{5}\)，而 \(f(4)=64+8+6=78 \equiv 3 \pmod{5}\)。等等，我们再算一遍：\(f(0)=6\equiv1\), \(f(1)=1+2+6=9\equiv4\), \(f(2)=8+4+6=18\equiv3\), \(f(3)=27+6+6=39\equiv4\), \(f(4)=64+8+6=78\equiv3\)。模5下无解。所以模125下也无解。这说明模素数无解是整个方程无解的充分条件。另一个示例：求解 \(x^3 + x + 1 \equiv 0 \pmod{25}\)。模5下：\(f(0)=1\), \(f(1)=3\), \(f(2)=8+2+1=11\equiv1\), \(f(3)=27+3+1=31\equiv1\), \(f(4)=64+4+1=69\equiv4\)。发现 \(f(2)\equiv1\pmod5\)，等等，我算错了，重算：\(f(2)=2^3+2+1=8+2+1=11\equiv1\pmod5\)，确实非零。等等，我再仔细找：\(f(0)=1\), \(f(1)=1+1+1=3\), \(f(2)=8+2+1=11\equiv1\), \(f(3)=27+3+1=31\equiv1\), \(f(4)=64+4+1=69\equiv4\)。确实模5下无解。但已知 \(x=2\) 是模5的一个解吗？不，\(f(2)\equiv1\not\equiv0\)。我犯错了。我们换一个多项式：考虑 \(x^3 + 2x + 1 \equiv 0 \pmod{25}\)。模5下：\(f(0)=1\), \(f(1)=1+2+1=4\), \(f(2)=8+4+1=13\equiv3\), \(f(3)=27+6+1=34\equiv4\), \(f(4)=64+8+1=73\equiv3\)。还是无解。看来我举的例子不好。我们换一个已知有模5解的例子。正确示例：求解 \(f(x) = x^3 + 2x + 6 \equiv 0 \pmod{25}\)。但我们刚才发现它模5无解。这不行。修正：让我们用 \(f(x)=x^3 + 4x + 1\)。模5下：\(f(0)=1\), \(f(1)=1+4+1=6\equiv1\), \(f(2)=8+8+1=17\equiv2\), \(f(3)=27+12+1=40\equiv0\), \(f(4)=64+16+1=81\equiv1\)。太好了，\(r=3\) 是模5的解，且 \(f'(x)=3x^2+4\)，所以 \(f'(3)=3* 9+4=27+4=31\equiv1 \not\equiv0\pmod5\)，满足亨泽尔引理条件。从模5提升到模25 ：设 \(x_ 1 = 3\)。计算 \(f(3)=3^3+4 3+1=27+12+1=40\)，所以 \(A = f(3)/5 = 40/5 = 8\)。计算 \(f'(3)=31\)，在模5下 \(f'(3) \equiv 1\)。我们需要解同余方程：\(A + f'(3) t \equiv 0 \pmod{5}\)，即 \(8 + 1 \cdot t \equiv 0 \pmod{5}\)，即 \(t+3\equiv0\pmod5\)，所以 \(t\equiv2\pmod5\)。取 \(t=2\)，则 \(x_ 2 = x_ 1 + t 5 = 3 + 2 5 = 13\)。验证：\(f(13)=13^3+4 13+1=2197+52+1=2250\)，而 \(2250/25=90\)，能被25整除，正确。所以模25下的一个解是 \(x \equiv 13 \pmod{25}\)。亨泽尔引理保证这是从 \(r=3\) 提升的唯一解。另外，我们还需要检查模5下是否还有其他解。我们已验证了0,1,2,4均非解，所以模5下只有 \(r=3\) 这一个解。因此，原方程 \(x^3+4x+1\equiv0\pmod{25}\) 的唯一解是 \(x \equiv 13 \pmod{25}\)。通过这个例子，你可以清晰地看到，求解高次同余方程的过程是一个“化归”过程：通过中国剩余定理化归到模素数幂，再通过亨泽尔引理化归到模素数。其结构的清晰性，依赖于模素数的域结构（有至多n个解）和牛顿迭代法在p进数中的类比（亨泽尔引理）。理解这个结构，是研究更深的p进分析和代数数论中局部域上多项式方程解的基础。