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

字数 2141 2025-10-28 20:05:42

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

我们已讨论过二次同余方程 \(x^2 \equiv a \pmod{p}\) 在奇素数模 \(p\) 下的解（如勒让德符号、二次互反律）。现在推广到素数幂模 \(p^k\)（\(p\) 为奇素数，\(k \geq 1\)）的求解方法。核心思想是：通过模 \(p\) 的解逐步“提升”到模 \(p^k\) 的解。

1. 问题描述
设 \(p\) 为奇素数，\(a\) 为整数，且 \(p \nmid a\)。考虑同余方程：

\[x^2 \equiv a \pmod{p^k}, \quad k \geq 1. \]

若解存在，称 \(a\) 是模 \(p^k\) 的二次剩余。

2. 模 \(p\) 的基础解（k=1）
首先解 \(x^2 \equiv a \pmod{p}\)。若勒让德符号 \(\left( \frac{a}{p} \right) = 1\)，则存在两个解 \(x \equiv r_1, r_2 \pmod{p}\)，且 \(r_2 \equiv -r_1 \pmod{p}\)。以 \(r\) 表示其中一个解。

3. 亨泽尔引理（提升解的核心工具）
亨泽尔引理提供了一种迭代方法：若已知模 \(p^k\) 的解，可构造模 \(p^{k+1}\) 的解。
设 \(f(x) = x^2 - a\)，已知 \(f(r) \equiv 0 \pmod{p^k}\)。我们寻找解 \(r' = r + t p^k\)，满足 \(f(r') \equiv 0 \pmod{p^{k+1}}\)。

展开：

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

要求 \(f(r) + f'(r) t p^k \equiv 0 \pmod{p^{k+1}}\)。
设 \(f(r) = m p^k\)，则方程化为：

\[m + f'(r) t \equiv 0 \pmod{p}. \]

由于 \(f'(r) = 2r\)，且 \(p \nmid r\)（因 \(p \nmid a\)），故 \(f'(r) \not\equiv 0 \pmod{p}\)。
解一次同余方程：

\[2r \cdot t \equiv -m \pmod{p}, \]

可唯一确定 \(t \mod p\)。从而得到模 \(p^{k+1}\) 的解 \(r'\)。

4. 求解步骤示例
以方程 \(x^2 \equiv 2 \pmod{7^3}\) 为例：

步骤1（k=1）：解 \(x^2 \equiv 2 \pmod{7}\)。尝试得 \(r \equiv 3 \pmod{7}\)（或 \(r \equiv 4\)）。
步骤2（k=2）：设 \(r_1 = 3\)，提升到模 \(7^2\)。
\(f(3) = 9 - 2 = 7\)，故 \(m = 1\)。
解 \(2 \cdot 3 \cdot t \equiv -1 \pmod{7} \Rightarrow 6t \equiv 6 \pmod{7} \Rightarrow t \equiv 1 \pmod{7}\)。
得 \(r_2 = 3 + 1 \cdot 7 = 10\)。验证： \(10^2 \equiv 2 \pmod{49}\)。
步骤3（k=3）：提升到模 \(7^3\)。
\(f(10) = 100 - 2 = 98 = 2 \cdot 49\)，故 \(m = 2\)。
解 \(2 \cdot 10 \cdot t \equiv -2 \pmod{7} \Rightarrow 20t \equiv 5 \pmod{7} \Rightarrow 6t \equiv 5 \pmod{7} \Rightarrow t \equiv 2 \pmod{7}\)（因 \(6 \times 2 = 12 \equiv 5\)）。
得 \(r_3 = 10 + 2 \cdot 49 = 108\)。验证： \(108^2 = 11664\)，且 \(11664 - 2 = 11662 = 238 \cdot 49 \equiv 0 \pmod{343}\)。

5. 解的数量与形式
每步提升从模 \(p^k\) 的一个解得到模 \(p^{k+1}\) 的唯一解。因此：

若 \(a\) 是模 \(p\) 的二次剩余，则对任意 \(k \geq 1\)，模 \(p^k\) 下恰有两个解。
两个解互为相反数模 \(p^k\)，即若 \(r\) 是解，则另一个解为 \(-r\)。

6. 对比模 p=2 的特殊情况
模 \(2^k\) 的二次同余方程需单独讨论（例如解数可能为 1、2 或 4），此处仅处理奇素数模。

二次同余方程与素数模幂的求解方法我们已讨论过二次同余方程 \( x^2 \equiv a \pmod{p} \) 在奇素数模 \( p \) 下的解（如勒让德符号、二次互反律）。现在推广到素数幂模 \( p^k \)（\( p \) 为奇素数，\( k \geq 1 \)）的求解方法。核心思想是：通过模 \( p \) 的解逐步“提升”到模 \( p^k \) 的解。 1. 问题描述设 \( p \) 为奇素数，\( a \) 为整数，且 \( p \nmid a \)。考虑同余方程： \[ x^2 \equiv a \pmod{p^k}, \quad k \geq 1. \] 若解存在，称 \( a \) 是模 \( p^k \) 的二次剩余。 2. 模 \( p \) 的基础解（k=1）首先解 \( x^2 \equiv a \pmod{p} \)。若勒让德符号 \( \left( \frac{a}{p} \right) = 1 \)，则存在两个解 \( x \equiv r_ 1, r_ 2 \pmod{p} \)，且 \( r_ 2 \equiv -r_ 1 \pmod{p} \)。以 \( r \) 表示其中一个解。 3. 亨泽尔引理（提升解的核心工具）亨泽尔引理提供了一种迭代方法：若已知模 \( p^k \) 的解，可构造模 \( p^{k+1} \) 的解。设 \( f(x) = x^2 - a \)，已知 \( f(r) \equiv 0 \pmod{p^k} \)。我们寻找解 \( r' = r + t p^k \)，满足 \( f(r') \equiv 0 \pmod{p^{k+1}} \)。展开： \[ f(r + t p^k) = f(r) + f'(r) \cdot t p^k \pmod{p^{k+1}}. \] 要求 \( f(r) + f'(r) t p^k \equiv 0 \pmod{p^{k+1}} \)。设 \( f(r) = m p^k \)，则方程化为： \[ m + f'(r) t \equiv 0 \pmod{p}. \] 由于 \( f'(r) = 2r \)，且 \( p \nmid r \)（因 \( p \nmid a \)），故 \( f'(r) \not\equiv 0 \pmod{p} \)。解一次同余方程： \[ 2r \cdot t \equiv -m \pmod{p}, \] 可唯一确定 \( t \mod p \)。从而得到模 \( p^{k+1} \) 的解 \( r' \)。 4. 求解步骤示例以方程 \( x^2 \equiv 2 \pmod{7^3} \) 为例：步骤1（k=1）：解 \( x^2 \equiv 2 \pmod{7} \)。尝试得 \( r \equiv 3 \pmod{7} \)（或 \( r \equiv 4 \)）。步骤2（k=2）：设 \( r_ 1 = 3 \)，提升到模 \( 7^2 \)。 \( f(3) = 9 - 2 = 7 \)，故 \( m = 1 \)。解 \( 2 \cdot 3 \cdot t \equiv -1 \pmod{7} \Rightarrow 6t \equiv 6 \pmod{7} \Rightarrow t \equiv 1 \pmod{7} \)。得 \( r_ 2 = 3 + 1 \cdot 7 = 10 \)。验证： \( 10^2 \equiv 2 \pmod{49} \)。步骤3（k=3）：提升到模 \( 7^3 \)。 \( f(10) = 100 - 2 = 98 = 2 \cdot 49 \)，故 \( m = 2 \)。解 \( 2 \cdot 10 \cdot t \equiv -2 \pmod{7} \Rightarrow 20t \equiv 5 \pmod{7} \Rightarrow 6t \equiv 5 \pmod{7} \Rightarrow t \equiv 2 \pmod{7} \)（因 \( 6 \times 2 = 12 \equiv 5 \)）。得 \( r_ 3 = 10 + 2 \cdot 49 = 108 \)。验证： \( 108^2 = 11664 \)，且 \( 11664 - 2 = 11662 = 238 \cdot 49 \equiv 0 \pmod{343} \)。 5. 解的数量与形式每步提升从模 \( p^k \) 的一个解得到模 \( p^{k+1} \) 的唯一解。因此：若 \( a \) 是模 \( p \) 的二次剩余，则对任意 \( k \geq 1 \)，模 \( p^k \) 下恰有两个解。两个解互为相反数模 \( p^k \)，即若 \( r \) 是解，则另一个解为 \( -r \)。 6. 对比模 p=2 的特殊情况模 \( 2^k \) 的二次同余方程需单独讨论（例如解数可能为 1、2 或 4），此处仅处理奇素数模。