二次同余方程与模合数

字数 2160 2025-10-28 00:29:42

二次同余方程与模合数

问题引入
你已学习素数模 \(p\) 的二次同余方程 \(x^2 \equiv a \ (\text{mod} \ p)\) 的解法（如勒让德符号、模平方根）。现考虑模数为合数 \(n\) 的情况：

\[ x^2 \equiv a \ (\text{mod} \ n), \quad \gcd(a, n) = 1. \]

合数模会带来新挑战，因为模 \(n\) 的剩余类环不是域，需分解模数以简化问题。

模数分解为素数幂
若 \(n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}\)，根据中国剩余定理，解 \(x^2 \equiv a \ (\text{mod} \ n)\) 等价于解方程组：

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

每个素数幂模方程的解可独立求解，再通过中国剩余定理组合为模 \(n\) 的解。

素数幂模方程 \(x^2 \equiv a \ (\text{mod} \ p^k)\)
- 当 \(p\) 为奇素数：
  若 \(x^2 \equiv a \ (\text{mod} \ p)\) 有解（即勒让德符号 \(\left( \frac{a}{p} \right) = 1\)），则模 \(p^k\) 的解可通过亨泽尔引理提升：
  设 \(x_1\) 是模 \(p\) 的解且 \(\gcd(2x_1, p) = 1\)（即 \(p \nmid 2x_1\)），则存在唯一解 \(x_k \equiv x_1 \ (\text{mod} \ p)\) 满足 \(x_k^2 \equiv a \ (\text{mod} \ p^k)\)。
  提升公式：从解 \(x_i \ (\text{mod} \ p^i)\) 得到 \(x_{i+1} = x_i + t p^i\)，其中 \(t\) 由方程 \(2x_i t \equiv \frac{a - x_i^2}{p^i} \ (\text{mod} \ p)\) 决定。
- 当 \(p = 2\)：
  模 \(2^k\) 的情况更复杂，因 \(2\) 是唯一偶素数，且 \(\gcd(2x, 2)\) 可能不互质。

若 \(k = 1\)（模 2）：方程 \(x^2 \equiv a \ (\text{mod} \ 2)\) 仅当 \(a \equiv 1\) 时有解 \(x \equiv 1\)。
若 \(k = 2\)（模 4）：解存在当且仅当 \(a \equiv 1 \ (\text{mod} \ 4)\)，解为 \(x \equiv 1, 3\)。
若 \(k \geq 3\)：解存在需满足 \(a \equiv 1 \ (\text{mod} \ 8)\)，此时恰有 4 个解。例如模 8 时，\(x \equiv 1, 3, 5, 7\) 是 \(x^2 \equiv 1\) 的解。

合数模的解数
设 \(n = 2^e p_1^{k_1} \cdots p_m^{k_m}\)，每个奇素数幂模方程 \(x^2 \equiv a \ (\text{mod} \ p_i^{k_i})\) 的解数：
- 若 \(\left( \frac{a}{p_i} \right) = 1\) 则有 2 个解；若 \(\left( \frac{a}{p_i} \right) = -1\) 则无解。
  模 \(2^e\) 的解数：
- \(e = 1\)：1 个解（若解存在）；
- \(e = 2\)：2 个解；
- \(e \geq 3\)：4 个解（需 \(a \equiv 1 \ (\text{mod} \ 8)\)）。
  总解数为各素数幂模解数的乘积。例如若 \(n\) 为奇合数且 \(a\) 是模每个 \(p_i\) 的二次剩余，则解数为 \(2^m\)。
应用示例
解 \(x^2 \equiv 9 \ (\text{mod} \ 28)\)。分解 \(28 = 4 \times 7\)：
- 模 4：\(x^2 \equiv 1 \ (\text{mod} \ 4)\) 解为 \(x \equiv 1, 3\)。
- 模 7：\(x^2 \equiv 2 \ (\text{mod} \ 7)\)，检查平方剩余：\(1^2=1, 2^2=4, 3^2=2\)，解为 \(x \equiv 3, 4\)。
  组合得 4 个解：
  \(x \equiv 3, 11, 17, 25 \ (\text{mod} \ 28)\)。
关键点总结
- 合数模二次同余方程通过分解为素数幂模简化。
- 奇素数幂模用亨泽尔引理提升解；模 2 的幂需单独处理。
- 解数由模数的素因子分解决定，反映中国剩余定理的乘积结构。

二次同余方程与模合数问题引入你已学习素数模 \( p \) 的二次同余方程 \( x^2 \equiv a \ (\text{mod} \ p) \) 的解法（如勒让德符号、模平方根）。现考虑模数为合数 \( n \) 的情况： \[ x^2 \equiv a \ (\text{mod} \ n), \quad \gcd(a, n) = 1. \] 合数模会带来新挑战，因为模 \( n \) 的剩余类环不是域，需分解模数以简化问题。模数分解为素数幂若 \( n = p_ 1^{k_ 1} p_ 2^{k_ 2} \cdots p_ m^{k_ m} \)，根据中国剩余定理，解 \( x^2 \equiv a \ (\text{mod} \ n) \) 等价于解方程组： \[ x^2 \equiv a \ (\text{mod} \ p_ i^{k_ i}) \quad (i=1,2,\dots,m). \] 每个素数幂模方程的解可独立求解，再通过中国剩余定理组合为模 \( n \) 的解。素数幂模方程 \( x^2 \equiv a \ (\text{mod} \ p^k) \) 当 \( p \) 为奇素数：若 \( x^2 \equiv a \ (\text{mod} \ p) \) 有解（即勒让德符号 \( \left( \frac{a}{p} \right) = 1 \)），则模 \( p^k \) 的解可通过亨泽尔引理提升：设 \( x_ 1 \) 是模 \( p \) 的解且 \( \gcd(2x_ 1, p) = 1 \)（即 \( p \nmid 2x_ 1 \)），则存在唯一解 \( x_ k \equiv x_ 1 \ (\text{mod} \ p) \) 满足 \( x_ k^2 \equiv a \ (\text{mod} \ p^k) \)。提升公式：从解 \( x_ i \ (\text{mod} \ p^i) \) 得到 \( x_ {i+1} = x_ i + t p^i \)，其中 \( t \) 由方程 \( 2x_ i t \equiv \frac{a - x_ i^2}{p^i} \ (\text{mod} \ p) \) 决定。当 \( p = 2 \) ：模 \( 2^k \) 的情况更复杂，因 \( 2 \) 是唯一偶素数，且 \( \gcd(2x, 2) \) 可能不互质。若 \( k = 1 \)（模 2）：方程 \( x^2 \equiv a \ (\text{mod} \ 2) \) 仅当 \( a \equiv 1 \) 时有解 \( x \equiv 1 \)。若 \( k = 2 \)（模 4）：解存在当且仅当 \( a \equiv 1 \ (\text{mod} \ 4) \)，解为 \( x \equiv 1, 3 \)。若 \( k \geq 3 \)：解存在需满足 \( a \equiv 1 \ (\text{mod} \ 8) \)，此时恰有 4 个解。例如模 8 时，\( x \equiv 1, 3, 5, 7 \) 是 \( x^2 \equiv 1 \) 的解。合数模的解数设 \( n = 2^e p_ 1^{k_ 1} \cdots p_ m^{k_ m} \)，每个奇素数幂模方程 \( x^2 \equiv a \ (\text{mod} \ p_ i^{k_ i}) \) 的解数：若 \( \left( \frac{a}{p_ i} \right) = 1 \) 则有 2 个解；若 \( \left( \frac{a}{p_ i} \right) = -1 \) 则无解。模 \( 2^e \) 的解数： \( e = 1 \)：1 个解（若解存在）； \( e = 2 \)：2 个解； \( e \geq 3 \)：4 个解（需 \( a \equiv 1 \ (\text{mod} \ 8) \)）。总解数为各素数幂模解数的乘积。例如若 \( n \) 为奇合数且 \( a \) 是模每个 \( p_ i \) 的二次剩余，则解数为 \( 2^m \)。应用示例解 \( x^2 \equiv 9 \ (\text{mod} \ 28) \)。分解 \( 28 = 4 \times 7 \)：模 4：\( x^2 \equiv 1 \ (\text{mod} \ 4) \) 解为 \( x \equiv 1, 3 \)。模 7：\( x^2 \equiv 2 \ (\text{mod} \ 7) \)，检查平方剩余：\( 1^2=1, 2^2=4, 3^2=2 \)，解为 \( x \equiv 3, 4 \)。组合得 4 个解： \( x \equiv 3, 11, 17, 25 \ (\text{mod} \ 28) \)。关键点总结合数模二次同余方程通过分解为素数幂模简化。奇素数幂模用亨泽尔引理提升解；模 2 的幂需单独处理。解数由模数的素因子分解决定，反映中国剩余定理的乘积结构。