二次同余方程与模合数的求解方法

字数 3247 2025-10-29 12:22:04

二次同余方程与模合数的求解方法

我们之前讨论过素数模的二次同余方程。现在，我们进入更具挑战性的领域：模数为合数时的求解。其核心思想是将问题分解为模其素因子幂次的子问题，然后利用中国剩余定理进行组合。

第一步：分解问题——模为素数幂

设我们需要解的方程为：

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

其中 \(n\) 是一个大于1的正整数。

关键分解：根据算术基本定理，我们可以将 \(n\) 分解为其素因子幂的乘积：\(n = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m}\)。中国剩余定理告诉我们，原方程有解，当且仅当下面这一系列方程都有解：

\[ \begin{aligned} x^2 &\equiv a \pmod{p_1^{k_1}} \\ x^2 &\equiv a \pmod{p_2^{k_2}} \\ &\vdots \\ x^2 &\equiv a \pmod{p_m^{k_m}} \end{aligned} \]

并且，原方程的解数等于所有这些子方程解数的乘积。

问题简化：因此，求解模合数 \(n\) 的二次同余方程，其核心就转化为求解模数为素数幂 \(p^k\) 的二次同余方程。

第二步：亨泽尔引理——提升解的核心工具

现在，我们有了一个模 \(p^k\) 的方程：\(x^2 \equiv a \pmod{p^k}\)。亨泽尔引理提供了一个系统性的方法，将一个模低次幂（如模 \(p\)）的解“提升”到模高次幂（如模 \(p^2, p^3, \dots\)）的解。

基础情况（k=1）：首先，我们必须解模 \(p\) 的方程 \(x^2 \equiv a \pmod{p}\)。这是我们熟悉的情况。使用勒让德符号判断解的存在性。如果 \(\left(\frac{a}{p}\right) = -1\)，则方程无解，整个提升过程终止。如果 \(\left(\frac{a}{p}\right) = 1\)，则方程在模 \(p\) 下有两个解，记其中一个为 \(x_1\)（满足 \(0 \le x_1 < p\)）。
亨泽尔引理的应用：亨泽尔引理指出，如果 \(x_k\) 是方程 \(f(x) \equiv 0 \pmod{p^k}\) 的一个解，并且导数 \(f'(x_k) \not\equiv 0 \pmod{p}\)，那么存在唯一的一个解 \(x_{k+1} \pmod{p^{k+1}}\) 使得 \(x_{k+1} \equiv x_k \pmod{p^k}\)。

在我们的二次方程 \(f(x) = x^2 - a\) 中，导数 \(f'(x) = 2x\)。
条件 \(f'(x_k) \not\equiv 0 \pmod{p}\) 意味着 \(p \nmid 2x_k\)。由于 \(x_k\) 是模 \(p\) 的解，且 \(p\) 不整除 \(a\)（否则问题平凡），通常 \(p \nmid x_k\)。因此，只要 \(p \ne 2\)，这个条件自动满足。

提升步骤（对于奇素数 p）：

假设我们已经找到一个解 \(x_k\)，满足 \(x_k^2 \equiv a \pmod{p^k}\)。
我们寻找形式为 \(x_{k+1} = x_k + t p^k\) 的解，其中 \(t\) 是待定的整数。
- 代入方程：

\[ (x_k + t p^k)^2 \equiv a \pmod{p^{k+1}} \]

\[ x_k^2 + 2 x_k t p^k + t^2 p^{2k} \equiv a \pmod{p^{k+1}} \]

由于 \(2k \ge k+1\)（当 \(k \ge 1\)），项 \(t^2 p^{2k}\) 是 \(p^{k+1}\) 的倍数，可以忽略。同时，由归纳假设 \(x_k^2 = a + b p^k\)（\(b\) 是某个整数）。代入得：

\[ a + b p^k + 2 x_k t p^k \equiv a \pmod{p^{k+1}} \]

\[ (b + 2 x_k t) p^k \equiv 0 \pmod{p^{k+1}} \]

这等价于求解关于 \(t\) 的线性同余方程：

\[ b + 2 x_k t \equiv 0 \pmod{p} \]

因为 \(p \nmid 2x_k\)，这个线性同余方程在模 \(p\) 下有唯一解 \(t_0\)。那么，\(x_{k+1} = x_k + t_0 p^k\) 就是模 \(p^{k+1}\) 下的解。
从一个模 \(p\) 的解 \(x_1\) 开始，重复此过程，我们可以逐步得到模 \(p^2, p^3, \dots, p^k\) 的解。

第三步：处理特殊的模数——素数2的幂次

当 \(p=2\) 时，情况变得特殊，因为 \(f'(x) = 2x\) 在模2下恒为0，亨泽尔引理的标准形式不适用。我们需要单独处理。

模2和模4：

模2：方程 \(x^2 \equiv a \pmod{2}\)。只有当 \(a \equiv 0, 1 \pmod{2}\) 时有解。解是平凡的。
模4：方程 \(x^2 \equiv a \pmod{4}\)。平方数模4只能同余于0或1。所以有解当且仅当 \(a \equiv 0, 1 \pmod{4}\)。解为：
若 \(a \equiv 0\)，则 \(x \equiv 0, 2 \pmod{4}\)。
若 \(a \equiv 1\)，则 \(x \equiv 1, 3 \pmod{4}\)。

模 \(2^k\) (k≥3)：此时需要更细致的分析。一个结论是，方程 \(x^2 \equiv a \pmod{2^k}\) 有解，当且仅当 \(a\) 具有特定的形式（例如，如果 \(a\) 是奇数，则必须是 \(1 \pmod{8}\)），并且解的数量可能是1、2或4个，而不是简单的两个。提升过程也比奇素数情况更复杂，通常需要从模8的解开始提升。

第四步：综合求解——使用中国剩余定理

在成功求解了所有形如 \(x^2 \equiv a \pmod{p_i^{k_i}}\) 的方程后：

组合解：对于每一个素数幂模数 \(p_i^{k_i}\)，假设我们找到了 \(N_i\) 个解。那么，原方程模 \(n\) 的解的总数就是 \(N_1 \times N_2 \times \dots \times N_m\)。
具体步骤：从每个素数幂模数的解集中任意选取一个解，这样就得到一组同余条件：

\[ \begin{aligned} x &\equiv r_1 \pmod{p_1^{k_1}} \\ x &\equiv r_2 \pmod{p_2^{k_2}} \\ &\vdots \\ x &\equiv r_m \pmod{p_m^{k_m}} \end{aligned} \]

应用中国剩余定理：这一组同余方程在模 \(n\) 下有唯一解。通过求解这个方程组，我们就得到了原二次同余方程 \(x^2 \equiv a \pmod{n}\) 的一个解。通过遍历所有可能的组合（共 \(N_1 \times N_2 \times \dots \times N_m\) 种），我们可以得到所有不同的解。

总结
求解模合数的二次同余方程是一个系统性的过程：分解 -> 提升 -> 组合。它深刻体现了数论中“化繁为简，分而治之”的思想，将复杂的模合数问题转化为相对简单的模素数幂问题，并利用亨泽尔引理和中国剩余定理这两个强大工具架起桥梁。理解这一方法，是掌握高次同余方程求解的基础。

二次同余方程与模合数的求解方法我们之前讨论过素数模的二次同余方程。现在，我们进入更具挑战性的领域：模数为合数时的求解。其核心思想是将问题分解为模其素因子幂次的子问题，然后利用中国剩余定理进行组合。第一步：分解问题——模为素数幂设我们需要解的方程为： \[ x^2 \equiv a \pmod{n} \] 其中 \(n\) 是一个大于1的正整数。关键分解：根据算术基本定理，我们可以将 \(n\) 分解为其素因子幂的乘积：\(n = p_ 1^{k_ 1} p_ 2^{k_ 2} \dots p_ m^{k_ m}\)。中国剩余定理告诉我们，原方程有解，当且仅当下面这一系列方程都有解： \[ \begin{aligned} x^2 &\equiv a \pmod{p_ 1^{k_ 1}} \\ x^2 &\equiv a \pmod{p_ 2^{k_ 2}} \\ &\vdots \\ x^2 &\equiv a \pmod{p_ m^{k_ m}} \end{aligned} \] 并且，原方程的解数等于所有这些子方程解数的乘积。问题简化：因此，求解模合数 \(n\) 的二次同余方程，其核心就转化为求解模数为素数幂 \(p^k\) 的二次同余方程。第二步：亨泽尔引理——提升解的核心工具现在，我们有了一个模 \(p^k\) 的方程：\(x^2 \equiv a \pmod{p^k}\)。亨泽尔引理提供了一个系统性的方法，将一个模低次幂（如模 \(p\)）的解“提升”到模高次幂（如模 \(p^2, p^3, \dots\)）的解。基础情况（k=1）：首先，我们必须解模 \(p\) 的方程 \(x^2 \equiv a \pmod{p}\)。这是我们熟悉的情况。使用勒让德符号判断解的存在性。如果 \(\left(\frac{a}{p}\right) = -1\)，则方程无解，整个提升过程终止。如果 \(\left(\frac{a}{p}\right) = 1\)，则方程在模 \(p\) 下有两个解，记其中一个为 \(x_ 1\)（满足 \(0 \le x_ 1 < p\)）。亨泽尔引理的应用：亨泽尔引理指出，如果 \(x_ k\) 是方程 \(f(x) \equiv 0 \pmod{p^k}\) 的一个解，并且导数 \(f'(x_ k) \not\equiv 0 \pmod{p}\)，那么存在唯一的一个解 \(x_ {k+1} \pmod{p^{k+1}}\) 使得 \(x_ {k+1} \equiv x_ k \pmod{p^k}\)。在我们的二次方程 \(f(x) = x^2 - a\) 中，导数 \(f'(x) = 2x\)。条件 \(f'(x_ k) \not\equiv 0 \pmod{p}\) 意味着 \(p \nmid 2x_ k\)。由于 \(x_ k\) 是模 \(p\) 的解，且 \(p\) 不整除 \(a\)（否则问题平凡），通常 \(p \nmid x_ k\)。因此，只要 \(p \ne 2\)，这个条件自动满足。提升步骤（对于奇素数 p）：假设我们已经找到一个解 \(x_ k\)，满足 \(x_ k^2 \equiv a \pmod{p^k}\)。我们寻找形式为 \(x_ {k+1} = x_ k + t p^k\) 的解，其中 \(t\) 是待定的整数。代入方程： \[ (x_ k + t p^k)^2 \equiv a \pmod{p^{k+1}} \] \[ x_ k^2 + 2 x_ k t p^k + t^2 p^{2k} \equiv a \pmod{p^{k+1}} \] 由于 \(2k \ge k+1\)（当 \(k \ge 1\)），项 \(t^2 p^{2k}\) 是 \(p^{k+1}\) 的倍数，可以忽略。同时，由归纳假设 \(x_ k^2 = a + b p^k\)（\(b\) 是某个整数）。代入得： \[ a + b p^k + 2 x_ k t p^k \equiv a \pmod{p^{k+1}} \] \[ (b + 2 x_ k t) p^k \equiv 0 \pmod{p^{k+1}} \] 这等价于求解关于 \(t\) 的线性同余方程： \[ b + 2 x_ k t \equiv 0 \pmod{p} \] 因为 \(p \nmid 2x_ k\)，这个线性同余方程在模 \(p\) 下有唯一解 \(t_ 0\)。那么，\(x_ {k+1} = x_ k + t_ 0 p^k\) 就是模 \(p^{k+1}\) 下的解。从一个模 \(p\) 的解 \(x_ 1\) 开始，重复此过程，我们可以逐步得到模 \(p^2, p^3, \dots, p^k\) 的解。第三步：处理特殊的模数——素数2的幂次当 \(p=2\) 时，情况变得特殊，因为 \(f'(x) = 2x\) 在模2下恒为0，亨泽尔引理的标准形式不适用。我们需要单独处理。模2和模4 ：模2：方程 \(x^2 \equiv a \pmod{2}\)。只有当 \(a \equiv 0, 1 \pmod{2}\) 时有解。解是平凡的。模4：方程 \(x^2 \equiv a \pmod{4}\)。平方数模4只能同余于0或1。所以有解当且仅当 \(a \equiv 0, 1 \pmod{4}\)。解为：若 \(a \equiv 0\)，则 \(x \equiv 0, 2 \pmod{4}\)。若 \(a \equiv 1\)，则 \(x \equiv 1, 3 \pmod{4}\)。模 \(2^k\) (k≥3) ：此时需要更细致的分析。一个结论是，方程 \(x^2 \equiv a \pmod{2^k}\) 有解，当且仅当 \(a\) 具有特定的形式（例如，如果 \(a\) 是奇数，则必须是 \(1 \pmod{8}\)），并且解的数量可能是1、2或4个，而不是简单的两个。提升过程也比奇素数情况更复杂，通常需要从模8的解开始提升。第四步：综合求解——使用中国剩余定理在成功求解了所有形如 \(x^2 \equiv a \pmod{p_ i^{k_ i}}\) 的方程后：组合解：对于每一个素数幂模数 \(p_ i^{k_ i}\)，假设我们找到了 \(N_ i\) 个解。那么，原方程模 \(n\) 的解的总数就是 \(N_ 1 \times N_ 2 \times \dots \times N_ m\)。具体步骤：从每个素数幂模数的解集中任意选取一个解，这样就得到一组同余条件： \[ \begin{aligned} x &\equiv r_ 1 \pmod{p_ 1^{k_ 1}} \\ x &\equiv r_ 2 \pmod{p_ 2^{k_ 2}} \\ &\vdots \\ x &\equiv r_ m \pmod{p_ m^{k_ m}} \end{aligned} \] 应用中国剩余定理：这一组同余方程在模 \(n\) 下有唯一解。通过求解这个方程组，我们就得到了原二次同余方程 \(x^2 \equiv a \pmod{n}\) 的一个解。通过遍历所有可能的组合（共 \(N_ 1 \times N_ 2 \times \dots \times N_ m\) 种），我们可以得到所有不同的解。总结求解模合数的二次同余方程是一个系统性的过程：分解 -> 提升 -> 组合。它深刻体现了数论中“化繁为简，分而治之”的思想，将复杂的模合数问题转化为相对简单的模素数幂问题，并利用亨泽尔引理和中国剩余定理这两个强大工具架起桥梁。理解这一方法，是掌握高次同余方程求解的基础。