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

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

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

在数论中，二次同余方程的一般形式为 \(x^2 \equiv a \pmod{n}\)，其中 \(n\) 是合数。解此类方程的核心思路是利用中国剩余定理（CRT），将问题分解为模素数幂的子问题。以下是逐步分析：

1. 模 \(n\) 的分解

若 \(n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}\)，则原方程等价于方程组：

\[\begin{cases} 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{cases} \]

每个子方程的解可通过亨泽尔引理提升至模素数幂的解。

2. 模素数幂的解的结构（以 \(p^k\) 为例）

情况1：\(p \nmid a\)
若 \(x^2 \equiv a \pmod{p}\) 有解（即 \(a\) 是模 \(p\) 的二次剩余），且 \(p \neq 2\)：
- 若 \(x_0\) 是模 \(p\) 的解，且 \(p \nmid 2x_0\)（即解非奇异），则亨泽尔引理保证解可唯一提升至模 \(p^k\)。
- 此时模 \(p^k\) 的解数为 2（即 \(x \equiv \pm x_k \pmod{p^k}\)）。
情况2：\(p = 2\)
模 \(2^k\) 的二次同余方程需单独处理（因亨泽尔引理对 \(p=2\) 需修正）：
- 对 \(k=1\)（模 2）：仅 \(a \equiv 1 \pmod{2}\) 有解 \(x \equiv 1\)。
- 对 \(k=2\)（模 4）：解存在需 \(a \equiv 1 \pmod{4}\)，解为 \(x \equiv \pm 1\)。
- 对 \(k \geq 3\)：解存在需 \(a \equiv 1 \pmod{8}\)，此时有 4 个解（例如模 8 时 \(x \equiv \pm 1, \pm 3\)）。
情况3：\(p \mid a\)（即 \(a\) 含因子 \(p\)）
设 \(a = p^t \cdot b\)，其中 \(p \nmid b\)。方程变为 \(x^2 \equiv p^t b \pmod{p^k}\)。
- 若 \(t \geq k\)，方程恒成立（任意 \(x\) 均为解）。
- 若 \(t < k\)：需 \(t\) 为偶数（设 \(t=2s\)），且 \(b\) 是模 \(p\) 的二次剩余。此时解的形式为 \(x = p^s y\)，其中 \(y^2 \equiv b \pmod{p^{k-t}}\)。

3. 合并解（中国剩余定理）

设每个模 \(p_i^{k_i}\) 的子方程有 \(N_i\) 个解，则模 \(n\) 的总解数为 \(N_1 \cdot N_2 \cdots N_m\)。每个解由 CRT 组合各子解得到。

示例：解 \(x^2 \equiv 25 \pmod{36}\)。

分解为 \(n=4 \cdot 9\)：
- 模 4：\(x^2 \equiv 1 \pmod{4}\) → 解 \(x \equiv 1, 3\)。
- 模 9：\(x^2 \equiv 7 \pmod{9}\) → 检查 \(7\) 模 9 的剩余：\(1^2=1, 2^2=4, 3^2=0, 4^2=7\) → 解 \(x \equiv 4, 5\)。
组合解：
\(x \equiv 1 \pmod{4}\) 与 \(x \equiv 4 \pmod{9}\) → \(x \equiv 13 \pmod{36}\)
\(x \equiv 1 \pmod{4}\) 与 \(x \equiv 5 \pmod{9}\) → \(x \equiv 31 \pmod{36}\)
\(x \equiv 3 \pmod{4}\) 与 \(x \equiv 4 \pmod{9}\) → \(x \equiv 5 \pmod{36}\)
\(x \equiv 3 \pmod{4}\) 与 \(x \equiv 5 \pmod{9}\) → \(x \equiv 23 \pmod{36}\)
最终解为 \(x \equiv 5, 13, 23, 31 \pmod{36}\)。

4. 关键结论

解的存在性依赖于 \(a\) 是每个模 \(p_i^{k_i}\) 的二次剩余（或满足 \(p \mid a\) 时的可约条件）。
解的数量可能为 0、2、4 或更多，取决于 \(n\) 的质因数分解及幂次。
对于奇质数幂，非奇异解总是成对出现（±形式）；对于模 2 的幂，解数可能为 1、2 或 4。

此结构揭示了二次同余方程与数论核心工具（CRT、亨泽尔引理、二次剩余）的深刻联系。

二次同余方程与模合数的解的结构在数论中，二次同余方程的一般形式为 \( x^2 \equiv a \pmod{n} \)，其中 \( n \) 是合数。解此类方程的核心思路是利用中国剩余定理（CRT），将问题分解为模素数幂的子问题。以下是逐步分析： 1. 模 \( n \) 的分解若 \( n = p_ 1^{k_ 1} p_ 2^{k_ 2} \cdots p_ m^{k_ m} \)，则原方程等价于方程组： \[ \begin{cases} 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{cases} \] 每个子方程的解可通过亨泽尔引理提升至模素数幂的解。 2. 模素数幂的解的结构（以 \( p^k \) 为例）情况1：\( p \nmid a \) 若 \( x^2 \equiv a \pmod{p} \) 有解（即 \( a \) 是模 \( p \) 的二次剩余），且 \( p \neq 2 \)：若 \( x_ 0 \) 是模 \( p \) 的解，且 \( p \nmid 2x_ 0 \)（即解非奇异），则亨泽尔引理保证解可唯一提升至模 \( p^k \)。此时模 \( p^k \) 的解数为 2 （即 \( x \equiv \pm x_ k \pmod{p^k} \)）。情况2：\( p = 2 \) 模 \( 2^k \) 的二次同余方程需单独处理（因亨泽尔引理对 \( p=2 \) 需修正）：对 \( k=1 \)（模 2）：仅 \( a \equiv 1 \pmod{2} \) 有解 \( x \equiv 1 \)。对 \( k=2 \)（模 4）：解存在需 \( a \equiv 1 \pmod{4} \)，解为 \( x \equiv \pm 1 \)。对 \( k \geq 3 \)：解存在需 \( a \equiv 1 \pmod{8} \)，此时有 4 个解（例如模 8 时 \( x \equiv \pm 1, \pm 3 \)）。情况3：\( p \mid a \) （即 \( a \) 含因子 \( p \)）设 \( a = p^t \cdot b \)，其中 \( p \nmid b \)。方程变为 \( x^2 \equiv p^t b \pmod{p^k} \)。若 \( t \geq k \)，方程恒成立（任意 \( x \) 均为解）。若 \( t < k \)：需 \( t \) 为偶数（设 \( t=2s \)），且 \( b \) 是模 \( p \) 的二次剩余。此时解的形式为 \( x = p^s y \)，其中 \( y^2 \equiv b \pmod{p^{k-t}} \)。 3. 合并解（中国剩余定理）设每个模 \( p_ i^{k_ i} \) 的子方程有 \( N_ i \) 个解，则模 \( n \) 的总解数为 \( N_ 1 \cdot N_ 2 \cdots N_ m \)。每个解由 CRT 组合各子解得到。示例：解 \( x^2 \equiv 25 \pmod{36} \)。分解为 \( n=4 \cdot 9 \)：模 4：\( x^2 \equiv 1 \pmod{4} \) → 解 \( x \equiv 1, 3 \)。模 9：\( x^2 \equiv 7 \pmod{9} \) → 检查 \( 7 \) 模 9 的剩余：\( 1^2=1, 2^2=4, 3^2=0, 4^2=7 \) → 解 \( x \equiv 4, 5 \)。组合解： \( x \equiv 1 \pmod{4} \) 与 \( x \equiv 4 \pmod{9} \) → \( x \equiv 13 \pmod{36} \) \( x \equiv 1 \pmod{4} \) 与 \( x \equiv 5 \pmod{9} \) → \( x \equiv 31 \pmod{36} \) \( x \equiv 3 \pmod{4} \) 与 \( x \equiv 4 \pmod{9} \) → \( x \equiv 5 \pmod{36} \) \( x \equiv 3 \pmod{4} \) 与 \( x \equiv 5 \pmod{9} \) → \( x \equiv 23 \pmod{36} \) 最终解为 \( x \equiv 5, 13, 23, 31 \pmod{36} \)。 4. 关键结论解的存在性依赖于 \( a \) 是每个模 \( p_ i^{k_ i} \) 的二次剩余（或满足 \( p \mid a \) 时的可约条件）。解的数量可能为 0、2、4 或更多，取决于 \( n \) 的质因数分解及幂次。对于奇质数幂，非奇异解总是成对出现（±形式）；对于模 2 的幂，解数可能为 1、2 或 4。此结构揭示了二次同余方程与数论核心工具（CRT、亨泽尔引理、二次剩余）的深刻联系。