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

字数 3477 2025-10-28 20:05:50

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

我们先从最基础的情况开始。设 \(p\) 是一个奇素数，\(a\) 是一个整数，且 \(p \nmid a\)。我们想要求解同余方程：

\[ x^2 \equiv a \pmod{p^k} \]

其中 \(k \ge 1\)。

第一步：模素数 \(p\) 的情况 (k=1)

这是所有讨论的基础。方程是：

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

解的存在性：这个方程有解，当且仅当 \(a\) 是模 \(p\) 的二次剩余。这可以用勒让德符号 \(\left(\frac{a}{p}\right)\) 来判断。如果 \(\left(\frac{a}{p}\right) = 1\)，则方程有两个不相等的解，记为 \(\pm r\)，且满足 \(0 < r < p\)。
求解方法：当 \(p \equiv 3 \pmod{4}\) 时，有一个简单的求解公式：如果解存在，那么 \(x \equiv \pm a^{(p+1)/4} \pmod{p}\)。对于其他形式的素数，有更复杂的算法，如 Tonelli-Shanks 算法。

第二步：从模 \(p\) 的解“提升”到模 \(p^2\) 的解 (k=2)

现在我们假设已经找到了一个模 \(p\) 的解 \(x_1\)，满足：

\[ x_1^2 \equiv a \pmod{p} \]

我们的目标是找到一个模 \(p^2\) 的解 \(x_2\)，使得：

\[ x_2^2 \equiv a \pmod{p^2} \quad \text{并且} \quad x_2 \equiv x_1 \pmod{p} \]

我们设 \(x_2 = x_1 + t p\)，其中 \(t\) 是待确定的整数。将其代入模 \(p^2\) 的方程：

\[ (x_1 + t p)^2 \equiv a \pmod{p^2} \]

展开左边：

\[ x_1^2 + 2 x_1 t p + t^2 p^2 \equiv a \pmod{p^2} \]

注意 \(t^2 p^2\) 是 \(p^2\) 的倍数，所以在模 \(p^2\) 下它为 0。同时，由 \(x_1^2 \equiv a \pmod{p}\) 可知，存在整数 \(k\) 使得 \(x_1^2 = a + k p\)。代入上式：

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

两边减去 \(a\)：

\[ k p + 2 x_1 t p \equiv 0 \pmod{p^2} \]

两边同时除以 \(p\)（因为 \(p^2\) 整除左边，所以除以 \(p\) 后同余式仍然在模 \(p\) 下成立）：

\[ k + 2 x_1 t \equiv 0 \pmod{p} \]

这是一个关于未知数 \(t\) 的一次同余方程。由于 \(p \nmid a\) 且 \(x_1^2 \equiv a \pmod{p}\)，所以 \(p \nmid x_1\)。这意味着 \(2x_1\) 在模 \(p\) 下有乘法逆元。因此，这个同余方程对 \(t\) 有唯一解：

\[ t \equiv -k (2 x_1)^{-1} \pmod{p} \]

其中 \((2 x_1)^{-1}\) 是 \(2x_1\) 模 \(p\) 的逆元。

一旦我们找到了这个 \(t\)，那么 \(x_2 = x_1 + t p\) 就是方程 \(x^2 \equiv a \pmod{p^2}\) 的一个解。

第三步：亨泽尔引理——提升到任意幂次 \(p^k\)

第二步中使用的方法可以系统性地推广，这就是亨泽尔引理。它告诉我们如何将一个模 \(p^k\) 的解“提升”为一个模 \(p^{k+1}\) 的解。

亨泽尔引理（适用于多项式）：设 \(f(x)\) 是一个整系数多项式，\(p\) 是素数，\(k \ge 1\)。如果整数 \(r\) 满足：

\(f(r) \equiv 0 \pmod{p^k}\)
\(f'(r) \not\equiv 0 \pmod{p}\)（即 \(f'(r)\) 不能被 \(p\) 整除，这里 \(f'\) 是导数）

那么存在唯一的整数 \(s\)，满足 \(0 \le s < p\)，使得：

\[ f(r + s p^k) \equiv 0 \pmod{p^{k+1}} \]

并且 \(s\) 可以由以下同余式解出：

\[ s \cdot f'(r) \equiv -\frac{f(r)}{p^k} \pmod{p} \]

应用于我们的二次方程 \(f(x) = x^2 - a\)：

\(f'(x) = 2x\)。
条件 \(f'(r) \not\equiv 0 \pmod{p}\) 等价于 \(p \nmid 2r\)。由于 \(p\) 是奇素数且 \(r^2 \equiv a \pmod{p^k}\) 意味着 \(p \nmid r\)（因为 \(p \nmid a\)），所以这个条件自动满足。

求解步骤：

基础步骤 (k=1)：找到一个模 \(p\) 的解 \(r_1\)。
提升步骤：假设我们已经有一个模 \(p^k\) 的解 \(r_k\)，即 \(r_k^2 \equiv a \pmod{p^k}\)。我们寻找形如 \(r_{k+1} = r_k + t p^k\) 的解，使其满足模 \(p^{k+1}\)。
代入方程：\((r_k + t p^k)^2 \equiv a \pmod{p^{k+1}}\)。
展开：\(r_k^2 + 2 r_k t p^k + t^2 p^{2k} \equiv a \pmod{p^{k+1}}\)。
因为 \(k \ge 1\)，所以 \(2k \ge k+1\)，项 \(t^2 p^{2k}\) 可以被 \(p^{k+1}\) 整除，可以忽略。
同时，因为 \(r_k^2 \equiv a \pmod{p^k}\)，所以存在整数 \(m\) 使得 \(r_k^2 = a + m p^k\)。
代入得到：\(a + m p^k + 2 r_k t p^k \equiv a \pmod{p^{k+1}}\)。
化简：\((m + 2 r_k t) p^k \equiv 0 \pmod{p^{k+1}}\)。
两边除以 \(p^k\)：\(m + 2 r_k t \equiv 0 \pmod{p}\)。
解这个关于 \(t\) 的线性同余方程：\(t \equiv -m (2 r_k)^{-1} \pmod{p}\)。这里 \((2 r_k)^{-1}\) 是模 \(p\) 的逆元，因为 \(p \nmid 2r_k\)。
找到 \(t\) 后，\(r_{k+1} = r_k + t p^k\) 就是模 \(p^{k+1}\) 的一个解。

通过重复这个过程，我们可以从模 \(p\) 的一个解，逐步构造出模 \(p^2, p^3, \dots, p^k\) 的解。

总结：
对于奇素数 \(p\) 和整数 \(a\)（满足 \(p \nmid a\)），求解 \(x^2 \equiv a \pmod{p^k}\) 的关键是：

首先判断模 \(p\) 下解是否存在（使用勒让德符号）。
如果存在，先求出一个模 \(p\) 的解。
然后利用亨泽尔引理，通过一个迭代过程，将这个解逐步“提升”到更高的模 \(p^k\) 幂次。每一步提升都需要解一个简单的线性同余方程。这个过程保证了对于任意 \(k \ge 1\)，只要模 \(p\) 解存在，模 \(p^k\) 的解就存在，并且我们可以有效地将它构造出来。

二次同余方程与素数模幂的求解方法我们先从最基础的情况开始。设 \( p \) 是一个奇素数，\( a \) 是一个整数，且 \( p \nmid a \)。我们想要求解同余方程： \[ x^2 \equiv a \pmod{p^k} \] 其中 \( k \ge 1 \)。第一步：模素数 \( p \) 的情况 (k=1) 这是所有讨论的基础。方程是： \[ x^2 \equiv a \pmod{p} \] 解的存在性：这个方程有解，当且仅当 \( a \) 是模 \( p \) 的二次剩余。这可以用勒让德符号 \( \left(\frac{a}{p}\right) \) 来判断。如果 \( \left(\frac{a}{p}\right) = 1 \)，则方程有两个不相等的解，记为 \( \pm r \)，且满足 \( 0 < r < p \)。求解方法：当 \( p \equiv 3 \pmod{4} \) 时，有一个简单的求解公式：如果解存在，那么 \( x \equiv \pm a^{(p+1)/4} \pmod{p} \)。对于其他形式的素数，有更复杂的算法，如 Tonelli-Shanks 算法。第二步：从模 \( p \) 的解“提升”到模 \( p^2 \) 的解 (k=2) 现在我们假设已经找到了一个模 \( p \) 的解 \( x_ 1 \)，满足： \[ x_ 1^2 \equiv a \pmod{p} \] 我们的目标是找到一个模 \( p^2 \) 的解 \( x_ 2 \)，使得： \[ x_ 2^2 \equiv a \pmod{p^2} \quad \text{并且} \quad x_ 2 \equiv x_ 1 \pmod{p} \] 我们设 \( x_ 2 = x_ 1 + t p \)，其中 \( t \) 是待确定的整数。将其代入模 \( p^2 \) 的方程： \[ (x_ 1 + t p)^2 \equiv a \pmod{p^2} \] 展开左边： \[ x_ 1^2 + 2 x_ 1 t p + t^2 p^2 \equiv a \pmod{p^2} \] 注意 \( t^2 p^2 \) 是 \( p^2 \) 的倍数，所以在模 \( p^2 \) 下它为 0。同时，由 \( x_ 1^2 \equiv a \pmod{p} \) 可知，存在整数 \( k \) 使得 \( x_ 1^2 = a + k p \)。代入上式： \[ a + k p + 2 x_ 1 t p \equiv a \pmod{p^2} \] 两边减去 \( a \)： \[ k p + 2 x_ 1 t p \equiv 0 \pmod{p^2} \] 两边同时除以 \( p \)（因为 \( p^2 \) 整除左边，所以除以 \( p \) 后同余式仍然在模 \( p \) 下成立）： \[ k + 2 x_ 1 t \equiv 0 \pmod{p} \] 这是一个关于未知数 \( t \) 的一次同余方程。由于 \( p \nmid a \) 且 \( x_ 1^2 \equiv a \pmod{p} \)，所以 \( p \nmid x_ 1 \)。这意味着 \( 2x_ 1 \) 在模 \( p \) 下有乘法逆元。因此，这个同余方程对 \( t \) 有唯一解： \[ t \equiv -k (2 x_ 1)^{-1} \pmod{p} \] 其中 \( (2 x_ 1)^{-1} \) 是 \( 2x_ 1 \) 模 \( p \) 的逆元。一旦我们找到了这个 \( t \)，那么 \( x_ 2 = x_ 1 + t p \) 就是方程 \( x^2 \equiv a \pmod{p^2} \) 的一个解。第三步：亨泽尔引理——提升到任意幂次 \( p^k \) 第二步中使用的方法可以系统性地推广，这就是亨泽尔引理。它告诉我们如何将一个模 \( p^k \) 的解“提升”为一个模 \( p^{k+1} \) 的解。亨泽尔引理（适用于多项式）：设 \( f(x) \) 是一个整系数多项式，\( p \) 是素数，\( k \ge 1 \)。如果整数 \( r \) 满足： \( f(r) \equiv 0 \pmod{p^k} \) \( f'(r) \not\equiv 0 \pmod{p} \)（即 \( f'(r) \) 不能被 \( p \) 整除，这里 \( f' \) 是导数）那么存在唯一的整数 \( s \)，满足 \( 0 \le s < p \)，使得： \[ f(r + s p^k) \equiv 0 \pmod{p^{k+1}} \] 并且 \( s \) 可以由以下同余式解出： \[ s \cdot f'(r) \equiv -\frac{f(r)}{p^k} \pmod{p} \] 应用于我们的二次方程 \( f(x) = x^2 - a \) ： \( f'(x) = 2x \)。条件 \( f'(r) \not\equiv 0 \pmod{p} \) 等价于 \( p \nmid 2r \)。由于 \( p \) 是奇素数且 \( r^2 \equiv a \pmod{p^k} \) 意味着 \( p \nmid r \)（因为 \( p \nmid a \)），所以这个条件自动满足。求解步骤：基础步骤 (k=1) ：找到一个模 \( p \) 的解 \( r_ 1 \)。提升步骤：假设我们已经有一个模 \( p^k \) 的解 \( r_ k \)，即 \( r_ k^2 \equiv a \pmod{p^k} \)。我们寻找形如 \( r_ {k+1} = r_ k + t p^k \) 的解，使其满足模 \( p^{k+1} \)。代入方程：\( (r_ k + t p^k)^2 \equiv a \pmod{p^{k+1}} \)。展开：\( r_ k^2 + 2 r_ k t p^k + t^2 p^{2k} \equiv a \pmod{p^{k+1}} \)。因为 \( k \ge 1 \)，所以 \( 2k \ge k+1 \)，项 \( t^2 p^{2k} \) 可以被 \( p^{k+1} \) 整除，可以忽略。同时，因为 \( r_ k^2 \equiv a \pmod{p^k} \)，所以存在整数 \( m \) 使得 \( r_ k^2 = a + m p^k \)。代入得到：\( a + m p^k + 2 r_ k t p^k \equiv a \pmod{p^{k+1}} \)。化简：\( (m + 2 r_ k t) p^k \equiv 0 \pmod{p^{k+1}} \)。两边除以 \( p^k \)：\( m + 2 r_ k t \equiv 0 \pmod{p} \)。解这个关于 \( t \) 的线性同余方程：\( t \equiv -m (2 r_ k)^{-1} \pmod{p} \)。这里 \( (2 r_ k)^{-1} \) 是模 \( p \) 的逆元，因为 \( p \nmid 2r_ k \)。找到 \( t \) 后，\( r_ {k+1} = r_ k + t p^k \) 就是模 \( p^{k+1} \) 的一个解。通过重复这个过程，我们可以从模 \( p \) 的一个解，逐步构造出模 \( p^2, p^3, \dots, p^k \) 的解。总结：对于奇素数 \( p \) 和整数 \( a \)（满足 \( p \nmid a \)），求解 \( x^2 \equiv a \pmod{p^k} \) 的关键是：首先判断模 \( p \) 下解是否存在（使用勒让德符号）。如果存在，先求出一个模 \( p \) 的解。然后利用亨泽尔引理，通过一个迭代过程，将这个解逐步“提升”到更高的模 \( p^k \) 幂次。每一步提升都需要解一个简单的线性同余方程。这个过程保证了对于任意 \( k \ge 1 \)，只要模 \( p \) 解存在，模 \( p^k \) 的解就存在，并且我们可以有效地将它构造出来。