二次同余方程与模合数的解的结构
字数 2085 2025-10-28 08:37:22

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

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

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

其中 \(n\) 是正整数，\(a\) 是整数。当 \(n\) 为合数时，求解需结合模数的素因子分解。以下是逐步分析：

1. 模数为素数幂的情况

设 \(n = p^k\)（\(p\) 为奇素数，\(k \geq 1\)）。

步骤 1.1：解的存在条件（局部条件）

方程 \(x^2 \equiv a \pmod{p^k}\) 有解的必要条件是 \(x^2 \equiv a \pmod{p}\) 有解，即 \(a\) 是模 \(p\) 的二次剩余（若 \(p \nmid a\)，由勒让德符号判定）。

若 \(p \mid a\)，则需分类讨论：

  • 当 \(k=1\)：解为 \(x \equiv 0 \pmod{p}\)。
  • 当 \(k \geq 2\)：设 \(a = p^t \cdot m\)，其中 \(p \nmid m\)。
    • 若 \(t \geq k\)，方程恒成立（任意 \(x\) 满足）。
    • 若 \(t < k\)，则要求 \(t\) 为偶数（否则无解），且问题转化为解 \(x^2 \equiv m \pmod{p^{k-t}}\)。

步骤 1.2：解的提升（Hensel 引理）

若 \(x_0\) 是 \(x^2 \equiv a \pmod{p}\) 的解，且 \(p \nmid 2x_0\)（即 \(p \neq 2\) 时自动满足），则解可唯一提升到模 \(p^k\)：

  1. 从 \(x_1 \equiv x_0 \pmod{p}\) 开始，迭代求解

\[x_{i+1} = x_i + p^i \cdot t_i, \quad \text{其中 } t_i \equiv -\frac{f(x_i)}{p^i} \cdot (2x_0)^{-1} \pmod{p}, \]

这里 \(f(x) = x^2 - a\)。
2. 最终得到模 \(p^k\) 下的两个解（若 \(a \not\equiv 0 \pmod{p}\)）。

2. 模数为 2 的幂的情况

方程 \(x^2 \equiv a \pmod{2^k}\) 的解需单独分析（因 2 是唯一偶素数）：

  • \(k=1\)：解为 \(x \equiv a \pmod{2}\)（平凡）。
  • \(k=2\)：方程 \(x^2 \equiv a \pmod{4}\) 有解当且仅当 \(a \equiv 0,1 \pmod{4}\)。
  • \(k \geq 3\)：
    • 若 \(a\) 为奇数，解存在当且仅当 \(a \equiv 1 \pmod{8}\)，且此时恰有 4 个解。
    • 若 \(a\) 为偶数，需类似奇素数幂情况讨论指数。

3. 一般合数模数

设 \(n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}\)，方程 \(x^2 \equiv a \pmod{n}\) 等价于方程组：

\[x^2 \equiv a \pmod{p_i^{k_i}} \quad (i=1,\dots,r). \]

步骤 3.1：解的存在条件

原方程有解当且仅当每个模 \(p_i^{k_i}\) 的方程有解。

步骤 3.2：解的构造

  1. 对每个 \(i\)，求出 \(x^2 \equiv a \pmod{p_i^{k_i}}\) 的所有解（若存在）。
  2. 使用中国剩余定理（CRT）组合不同素幂模数的解：
    • 若每个模 \(p_i^{k_i}\) 有 \(t_i\) 个解，则模 \(n\) 下的解数为 \(t_1 t_2 \cdots t_r\)。
    • 解的形式为：对每个素幂模数选取一个解，通过 CRT 得到唯一模 \(n\) 的解。

4. 示例

求解 \(x^2 \equiv 25 \pmod{56}\)（\(n=56=2^3 \cdot 7\)）：

  1. 模 \(8\)：\(x^2 \equiv 25 \equiv 1 \pmod{8}\)，解为 \(x \equiv 1,3,5,7 \pmod{8}\)（4 个解）。
  2. 模 \(7\)：\(x^2 \equiv 25 \equiv 4 \pmod{7}\)，解为 \(x \equiv 2,5 \pmod{7}\)（2 个解）。
  3. 组合：\(4 \times 2 = 8\) 个解模 56，例如 \(x \equiv 5 \pmod{8}\) 与 \(x \equiv 2 \pmod{7}\) 得 \(x \equiv 37 \pmod{56}\)。

5. 关键结论

  • 模合数下二次同余方程的解数不一定是 2（与模素数不同），取决于模数的分解。
  • 解的存在性由局部条件（每个素因子）决定，全局解通过 CRT 合成。
  • 对 \(p=2\) 需单独处理，因其在 Hensel 引理中不适用。

此结构揭示了数论中“局部-整体”原理的雏形，是更高级理论（如哈塞原理）的特例。

二次同余方程与模合数的解的结构 二次同余方程的一般形式为 \[ x^2 \equiv a \pmod{n}, \] 其中 \(n\) 是正整数，\(a\) 是整数。当 \(n\) 为合数时，求解需结合模数的素因子分解。以下是逐步分析： 1. 模数为素数幂的情况 设 \(n = p^k\)（\(p\) 为奇素数，\(k \geq 1\)）。 步骤 1.1：解的存在条件（局部条件） 方程 \(x^2 \equiv a \pmod{p^k}\) 有解的必要条件是 \(x^2 \equiv a \pmod{p}\) 有解，即 \(a\) 是模 \(p\) 的二次剩余（若 \(p \nmid a\)，由勒让德符号判定）。 若 \(p \mid a\)，则需分类讨论： 当 \(k=1\)：解为 \(x \equiv 0 \pmod{p}\)。 当 \(k \geq 2\)：设 \(a = p^t \cdot m\)，其中 \(p \nmid m\)。 若 \(t \geq k\)，方程恒成立（任意 \(x\) 满足）。 若 \(t < k\)，则要求 \(t\) 为偶数（否则无解），且问题转化为解 \(x^2 \equiv m \pmod{p^{k-t}}\)。 步骤 1.2：解的提升（Hensel 引理） 若 \(x_ 0\) 是 \(x^2 \equiv a \pmod{p}\) 的解，且 \(p \nmid 2x_ 0\)（即 \(p \neq 2\) 时自动满足），则解可唯一提升到模 \(p^k\)： 从 \(x_ 1 \equiv x_ 0 \pmod{p}\) 开始，迭代求解 \[ x_ {i+1} = x_ i + p^i \cdot t_ i, \quad \text{其中 } t_ i \equiv -\frac{f(x_ i)}{p^i} \cdot (2x_ 0)^{-1} \pmod{p}, \] 这里 \(f(x) = x^2 - a\)。 最终得到模 \(p^k\) 下的两个解（若 \(a \not\equiv 0 \pmod{p}\)）。 2. 模数为 2 的幂的情况 方程 \(x^2 \equiv a \pmod{2^k}\) 的解需单独分析（因 2 是唯一偶素数）： \(k=1\)：解为 \(x \equiv a \pmod{2}\)（平凡）。 \(k=2\)：方程 \(x^2 \equiv a \pmod{4}\) 有解当且仅当 \(a \equiv 0,1 \pmod{4}\)。 \(k \geq 3\)： 若 \(a\) 为奇数，解存在当且仅当 \(a \equiv 1 \pmod{8}\)，且此时恰有 4 个解。 若 \(a\) 为偶数，需类似奇素数幂情况讨论指数。 3. 一般合数模数 设 \(n = p_ 1^{k_ 1} p_ 2^{k_ 2} \cdots p_ r^{k_ r}\)，方程 \(x^2 \equiv a \pmod{n}\) 等价于方程组： \[ x^2 \equiv a \pmod{p_ i^{k_ i}} \quad (i=1,\dots,r). \] 步骤 3.1：解的存在条件 原方程有解当且仅当每个模 \(p_ i^{k_ i}\) 的方程有解。 步骤 3.2：解的构造 对每个 \(i\)，求出 \(x^2 \equiv a \pmod{p_ i^{k_ i}}\) 的所有解（若存在）。 使用中国剩余定理（CRT）组合不同素幂模数的解： 若每个模 \(p_ i^{k_ i}\) 有 \(t_ i\) 个解，则模 \(n\) 下的解数为 \(t_ 1 t_ 2 \cdots t_ r\)。 解的形式为：对每个素幂模数选取一个解，通过 CRT 得到唯一模 \(n\) 的解。 4. 示例 求解 \(x^2 \equiv 25 \pmod{56}\)（\(n=56=2^3 \cdot 7\)）： 模 \(8\)：\(x^2 \equiv 25 \equiv 1 \pmod{8}\)，解为 \(x \equiv 1,3,5,7 \pmod{8}\)（4 个解）。 模 \(7\)：\(x^2 \equiv 25 \equiv 4 \pmod{7}\)，解为 \(x \equiv 2,5 \pmod{7}\)（2 个解）。 组合：\(4 \times 2 = 8\) 个解模 56，例如 \(x \equiv 5 \pmod{8}\) 与 \(x \equiv 2 \pmod{7}\) 得 \(x \equiv 37 \pmod{56}\)。 5. 关键结论 模合数下二次同余方程的解数不一定是 2（与模素数不同），取决于模数的分解。 解的存在性由局部条件（每个素因子）决定，全局解通过 CRT 合成。 对 \(p=2\) 需单独处理，因其在 Hensel 引理中不适用。 此结构揭示了数论中“局部-整体”原理的雏形，是更高级理论（如哈塞原理）的特例。