二次同余方程的解数
字数 4792 2025-10-26 09:01:44

二次同余方程的解数

我们先从二次同余方程的一般形式开始。一个二次同余方程可以写作：

\[ax^2 + bx + c \equiv 0 \pmod{m} \]

其中 \(a \not\equiv 0 \pmod{m}\)。要确定这个方程在模 \(m\) 下的解的数量，我们需要一个系统的方法。

第一步：化简为首项系数为1的形式
如果 \(\gcd(a, m) = 1\)，我们可以将方程两边同时乘以 \(a\) 在模 \(m\) 下的逆元（即模逆元），将其化为首项系数为1的形式。但更常用的一种代数技巧是“配方法”。我们对方程进行变换：

\[ax^2 + bx + c \equiv 0 \pmod{m} \]

两边乘以 \(4a\)（这要求 \(\gcd(2a, m) = 1\) 才能保证变换是等价的，但这是一个经典步骤）：

\[4a^2x^2 + 4abx + 4ac \equiv 0 \pmod{m} \]

观察到 \(4a^2x^2 + 4abx\) 是 \((2ax + b)^2\) 的前两项。实际上，我们有：

\[(2ax + b)^2 = 4a^2x^2 + 4abx + b^2 \]

所以，原方程可以改写为：

\[(2ax + b)^2 - b^2 + 4ac \equiv 0 \pmod{m} \]

\[ (2ax + b)^2 \equiv b^2 - 4ac \pmod{m} \]

我们令 \(y = 2ax + b\) 和 \(D = b^2 - 4ac\)。于是，二次同余方程被简化为一个更简单的形式：

\[y^2 \equiv D \pmod{m} \]

这个新方程 \(y^2 \equiv D \pmod{m}\) 就是关于 \(y\) 的二次剩余问题。而原方程的解 \(x\) 可以通过解线性同余方程 \(2ax + b \equiv y \pmod{m}\) 得到。因此，原二次同余方程的解数，取决于简化后的二次剩余方程的解数以及后续线性方程的解的情况。

第二步：当模数 \(m\) 是奇素数 \(p\) 时
这是最基础也是最核心的情况。假设 \(p\) 是一个奇素数（即 \(p > 2\)），且 \(p \nmid a\)（这保证了我们可以使用上面的配方法）。

  1. 简化方程：如上所述，方程被简化为 \(y^2 \equiv D \pmod{p}\)，其中 \(D = b^2 - 4ac\) 称为二次同余方程的判别式。

  2. 分析 \(y^2 \equiv D \pmod{p}\)：根据二次剩余的知识：

  • 如果 \(p \mid D\)（即 \(D \equiv 0 \pmod{p}\)），则方程 \(y^2 \equiv 0 \pmod{p}\) 有唯一解 \(y \equiv 0 \pmod{p}\)。
  • 如果 \(D\) 是模 \(p\) 的二次剩余（即 \(\left(\frac{D}{p}\right) = 1\)），并且 \(D \not\equiv 0 \pmod{p}\)，则方程 \(y^2 \equiv D \pmod{p}\) 有两个解，记作 \(y \equiv \pm t \pmod{p}\)。
  • 如果 \(D\) 是模 \(p\) 的二次非剩余（即 \(\left(\frac{D}{p}\right) = -1\)），则方程 \(y^2 \equiv D \pmod{p}\) 无解。

  1. 回代求解 \(x\)：对于每一个解出的 \(y\)，我们需要解线性同余方程 \(2ax + b \equiv y \pmod{p}\)。由于 \(p\) 是奇素数且 \(p \nmid a\)，则 \(p \nmid 2a\)，所以 \(\gcd(2a, p) = 1\)。这个线性同余方程有且仅有一个解。

  2. 综合解数：

  • 情况A：如果 \(D \equiv 0 \pmod{p}\)，则 \(y\) 有 1 个解。对于这个 \(y\)，线性方程 \(2ax + b \equiv y\) 有 1 个解。所以原方程有 1 个解。
  • 情况B：如果 \(\left(\frac{D}{p}\right) = 1\)，则 \(y\) 有 2 个不同的解。对于每一个 \(y\)，线性方程都有 1 个解。由于 \(y\) 的两个值不同，它们产生的两个 \(x\) 解也必然不同（因为 \(2a\) 有模逆元，映射是双射）。所以原方程有 2 个解。
  • 情况C：如果 \(\left(\frac{D}{p}\right) = -1\)，则 \(y\) 无解。所以原方程有 0 个解。

结论（模奇素数 \(p\)）：对于同余方程 \(ax^2 + bx + c \equiv 0 \pmod{p}\)（\(p \nmid a\)），其解的数量完全由判别式 \(D = b^2 - 4ac\) 决定：

  • 1 个解，当且仅当 \(p \mid D\)。
  • 2 个解，当且仅当 \(D\) 是模 \(p\) 的二次剩余。
  • 0 个解，当且仅当 \(D\) 是模 \(p\) 的二次非剩余。

第三步：当模数是素数幂 \(p^k\) 时（\(p\) 为奇素数）
现在我们将情况推广到模数是奇素数的幂次 \(m = p^k\)（\(k \ge 1\)）。我们仍然假设 \(p \nmid a\)。

  1. 简化方程：同样的配方法可以将方程化为 \(y^2 \equiv D \pmod{p^k}\)，其中 \(y = 2ax + b\)，\(D = b^2 - 4ac\)。

  2. 关键引理（亨泽尔引理）：亨泽尔引理为解决这类问题提供了强大工具。它告诉我们，对于一个模 \(p\) 有解的多项式方程，其解能否“提升”到模 \(p^k\) 上。

  • 具体到我们的简化方程 \(f(y) = y^2 - D \equiv 0 \pmod{p^k}\)。
  • 假设我们在模 \(p\) 上找到了一个解 \(y_1\)（即 \(y_1^2 \equiv D \pmod{p}\)）。
  • 这个解能否提升到模 \(p^k\)，取决于导数 \(f'(y) = 2y\) 在 \(y_1\) 处的值模 \(p\) 的情况。
  • 如果 \(p \nmid f'(y_1)\)（即 \(p \nmid 2y_1\)），由于 \(p\) 是奇素数，这等价于 \(p \nmid y_1\)。在这种情况下，亨泽尔引理保证，对于每个 \(k > 1\)，存在唯一的一个解 \(y_k\) 模 \(p^k\)，使得 \(y_k \equiv y_1 \pmod{p}\)。
  • 如果 \(p \mid f'(y_1)\)（即 \(p \mid y_1\)），情况更复杂。此时，如果 \(y_1\) 是模 \(p^2\) 的解，那么它可以提升到所有更高的幂次；否则，它无法提升。
  1. 应用到我们的问题：
  • 情况B的推广（\(D\) 是模 \(p\) 的二次剩余，且 \(p \nmid D\))：此时模 \(p\) 有两个解 \(y \equiv \pm t \pmod{p}\)。由于 \(D \not\equiv 0 \pmod{p}\)，我们有 \(t \not\equiv 0 \pmod{p}\)，所以 \(p \nmid (\pm t)\)。因此，\(p \nmid f'(\pm t)\)。根据亨泽尔引理，模 \(p\) 的这两个解中的每一个，都能唯一地提升到模 \(p^k\) 的一个解。所以，方程 \(y^2 \equiv D \pmod{p^k}\) 恰好有 2 个解。
  • 情况A的推广（\(p \mid D\))：此时模 \(p\) 只有一个解 \(y \equiv 0 \pmod{p}\)。这里 \(f'(0) = 0\)，所以 \(p \mid f'(0)\)，属于亨泽尔引理的特殊情况。我们需要检查 \(y \equiv 0\) 是否是模 \(p^2\) 的解。即检查 \(0^2 \equiv D \pmod{p^2}\) 是否成立，这要求 \(p^2 \mid D\)。通过更细致的分析（或应用亨泽尔引理的完整形式）可以得出：
  • 如果 \(p^2 \mid D\)，那么解 \(y \equiv 0 \pmod{p}\) 可以提升到模 \(p^k\)，并且对于 \(k \ge 2\)，实际上会有 2 个解（例如，模 \(9\) 时，\(y^2 \equiv 0\) 的解是 \(y \equiv 0, 3, 6 \pmod{9}\)，但经过回代后，原方程的解数需要具体分析，不过对于简化方程本身，解数可能多于1个）。
  • 如果 \(p \mid D\) 但 \(p^2 \nmid D\)，那么解无法提升到模 \(p^2\) 及以上，所以对于 \(k \ge 2\)，方程 \(y^2 \equiv D \pmod{p^k}\) 无解。
  • 情况C的推广（\(D\) 是模 \(p\) 的二次非剩余）：既然模 \(p\) 都无解，那么模 \(p^k\) 也必然无解。
  1. 回代求解 \(x\)：和模奇素数的情况一样，对于每个解出的 \(y\)，线性方程 \(2ax + b \equiv y \pmod{p^k}\) 因为 \(\gcd(2a, p^k)=1\) 而有唯一解。所以，简化方程 \(y^2 \equiv D\) 的解数直接决定了原方程 \(ax^2+bx+c \equiv 0\) 的解数。

结论（模奇素数的幂 \(p^k\)）：解数情况比模 \(p\) 时复杂，但核心仍然依赖于 \(D\) 和 \(p\) 的关系。最常见的情况是 \(p \nmid D\) 且 \(D\) 是二次剩余，此时原方程有 2 个解。

第四步：当模数是任意正整数 \(m\)
根据中国剩余定理，要解模 \(m\) 的同余方程，可以先将 \(m\) 分解为素数的幂次：\(m = p_1^{k_1} p_2^{k_2} \dots p_r^{k_r}\)。
方程 \(ax^2 + bx + c \equiv 0 \pmod{m}\) 有解，当且仅当它对每一个素因子幂 \(p_i^{k_i}\) 都有解。
如果对每个 \(p_i^{k_i}\) 都有解，设解数分别为 \(N_1, N_2, \dots, N_r\)。
那么，模 \(m\) 下的解的总数 \(N\) 就是这些解数的乘积：

\[N = N_1 \times N_2 \times \dots \times N_r \]

因此，求解任意模数 \(m\) 的二次同余方程，其解数问题最终归结为求解模是奇素数幂（以及特殊的 \(p=2\) 的幂，其分析更为复杂，但思路类似）的解数问题。

二次同余方程的解数 我们先从二次同余方程的一般形式开始。一个二次同余方程可以写作： \[ ax^2 + bx + c \equiv 0 \pmod{m} \] 其中 \( a \not\equiv 0 \pmod{m} \)。要确定这个方程在模 \( m \) 下的解的数量，我们需要一个系统的方法。 第一步：化简为首项系数为1的形式 如果 \( \gcd(a, m) = 1 \)，我们可以将方程两边同时乘以 \( a \) 在模 \( m \) 下的逆元（即模逆元），将其化为首项系数为1的形式。但更常用的一种代数技巧是“配方法”。我们对方程进行变换： \[ ax^2 + bx + c \equiv 0 \pmod{m} \] 两边乘以 \( 4a \)（这要求 \( \gcd(2a, m) = 1 \) 才能保证变换是等价的，但这是一个经典步骤）： \[ 4a^2x^2 + 4abx + 4ac \equiv 0 \pmod{m} \] 观察到 \( 4a^2x^2 + 4abx \) 是 \( (2ax + b)^2 \) 的前两项。实际上，我们有： \[ (2ax + b)^2 = 4a^2x^2 + 4abx + b^2 \] 所以，原方程可以改写为： \[ (2ax + b)^2 - b^2 + 4ac \equiv 0 \pmod{m} \] \[ (2ax + b)^2 \equiv b^2 - 4ac \pmod{m} \] 我们令 \( y = 2ax + b \) 和 \( D = b^2 - 4ac \)。于是，二次同余方程被简化为一个更简单的形式： \[ y^2 \equiv D \pmod{m} \] 这个新方程 \( y^2 \equiv D \pmod{m} \) 就是关于 \( y \) 的二次剩余问题。而原方程的解 \( x \) 可以通过解线性同余方程 \( 2ax + b \equiv y \pmod{m} \) 得到。因此，原二次同余方程的解数，取决于简化后的二次剩余方程的解数以及后续线性方程的解的情况。 第二步：当模数 \( m \) 是奇素数 \( p \) 时 这是最基础也是最核心的情况。假设 \( p \) 是一个奇素数（即 \( p > 2 \)），且 \( p \nmid a \)（这保证了我们可以使用上面的配方法）。 简化方程 ：如上所述，方程被简化为 \( y^2 \equiv D \pmod{p} \)，其中 \( D = b^2 - 4ac \) 称为二次同余方程的 判别式 。 分析 \( y^2 \equiv D \pmod{p} \) ：根据二次剩余的知识： 如果 \( p \mid D \)（即 \( D \equiv 0 \pmod{p} \)），则方程 \( y^2 \equiv 0 \pmod{p} \) 有唯一解 \( y \equiv 0 \pmod{p} \)。 如果 \( D \) 是模 \( p \) 的二次剩余（即 \( \left(\frac{D}{p}\right) = 1 \)），并且 \( D \not\equiv 0 \pmod{p} \)，则方程 \( y^2 \equiv D \pmod{p} \) 有两个解，记作 \( y \equiv \pm t \pmod{p} \)。 如果 \( D \) 是模 \( p \) 的二次非剩余（即 \( \left(\frac{D}{p}\right) = -1 \)），则方程 \( y^2 \equiv D \pmod{p} \) 无解。 回代求解 \( x \) ：对于每一个解出的 \( y \)，我们需要解线性同余方程 \( 2ax + b \equiv y \pmod{p} \)。由于 \( p \) 是奇素数且 \( p \nmid a \)，则 \( p \nmid 2a \)，所以 \( \gcd(2a, p) = 1 \)。这个线性同余方程有且仅有一个解。 综合解数 ： 情况A：如果 \( D \equiv 0 \pmod{p} \)，则 \( y \) 有 1 个解。对于这个 \( y \)，线性方程 \( 2ax + b \equiv y \) 有 1 个解。所以原方程有 1 个解 。 情况B：如果 \( \left(\frac{D}{p}\right) = 1 \)，则 \( y \) 有 2 个不同的解。对于每一个 \( y \)，线性方程都有 1 个解。由于 \( y \) 的两个值不同，它们产生的两个 \( x \) 解也必然不同（因为 \( 2a \) 有模逆元，映射是双射）。所以原方程有 2 个解 。 情况C：如果 \( \left(\frac{D}{p}\right) = -1 \)，则 \( y \) 无解。所以原方程有 0 个解 。 结论（模奇素数 \( p \)） ：对于同余方程 \( ax^2 + bx + c \equiv 0 \pmod{p} \)（\( p \nmid a \)），其解的数量完全由判别式 \( D = b^2 - 4ac \) 决定： 1 个解，当且仅当 \( p \mid D \)。 2 个解，当且仅当 \( D \) 是模 \( p \) 的二次剩余。 0 个解，当且仅当 \( D \) 是模 \( p \) 的二次非剩余。 第三步：当模数是素数幂 \( p^k \) 时（\( p \) 为奇素数） 现在我们将情况推广到模数是奇素数的幂次 \( m = p^k \)（\( k \ge 1 \)）。我们仍然假设 \( p \nmid a \)。 简化方程 ：同样的配方法可以将方程化为 \( y^2 \equiv D \pmod{p^k} \)，其中 \( y = 2ax + b \)，\( D = b^2 - 4ac \)。 关键引理（亨泽尔引理） ：亨泽尔引理为解决这类问题提供了强大工具。它告诉我们，对于一个模 \( p \) 有解的多项式方程，其解能否“提升”到模 \( p^k \) 上。 具体到我们的简化方程 \( f(y) = y^2 - D \equiv 0 \pmod{p^k} \)。 假设我们在模 \( p \) 上找到了一个解 \( y_ 1 \)（即 \( y_ 1^2 \equiv D \pmod{p} \)）。 这个解能否提升到模 \( p^k \)，取决于导数 \( f'(y) = 2y \) 在 \( y_ 1 \) 处的值模 \( p \) 的情况。 如果 \( p \nmid f'(y_ 1) \)（即 \( p \nmid 2y_ 1 \)），由于 \( p \) 是奇素数，这等价于 \( p \nmid y_ 1 \)。在这种情况下，亨泽尔引理保证，对于每个 \( k > 1 \)，存在 唯一 的一个解 \( y_ k \) 模 \( p^k \)，使得 \( y_ k \equiv y_ 1 \pmod{p} \)。 如果 \( p \mid f'(y_ 1) \)（即 \( p \mid y_ 1 \)），情况更复杂。此时，如果 \( y_ 1 \) 是模 \( p^2 \) 的解，那么它可以提升到所有更高的幂次；否则，它无法提升。 应用到我们的问题 ： 情况B的推广（\( D \) 是模 \( p \) 的二次剩余，且 \( p \nmid D \)) ：此时模 \( p \) 有两个解 \( y \equiv \pm t \pmod{p} \)。由于 \( D \not\equiv 0 \pmod{p} \)，我们有 \( t \not\equiv 0 \pmod{p} \)，所以 \( p \nmid (\pm t) \)。因此，\( p \nmid f'(\pm t) \)。根据亨泽尔引理，模 \( p \) 的这两个解中的每一个，都能 唯一地 提升到模 \( p^k \) 的一个解。所以，方程 \( y^2 \equiv D \pmod{p^k} \) 恰好有 2 个解 。 情况A的推广（\( p \mid D \)) ：此时模 \( p \) 只有一个解 \( y \equiv 0 \pmod{p} \)。这里 \( f'(0) = 0 \)，所以 \( p \mid f'(0) \)，属于亨泽尔引理的特殊情况。我们需要检查 \( y \equiv 0 \) 是否是模 \( p^2 \) 的解。即检查 \( 0^2 \equiv D \pmod{p^2} \) 是否成立，这要求 \( p^2 \mid D \)。通过更细致的分析（或应用亨泽尔引理的完整形式）可以得出： 如果 \( p^2 \mid D \)，那么解 \( y \equiv 0 \pmod{p} \) 可以提升到模 \( p^k \)，并且对于 \( k \ge 2 \)，实际上会有 2 个解 （例如，模 \( 9 \) 时，\( y^2 \equiv 0 \) 的解是 \( y \equiv 0, 3, 6 \pmod{9} \)，但经过回代后，原方程的解数需要具体分析，不过对于简化方程本身，解数可能多于1个）。 如果 \( p \mid D \) 但 \( p^2 \nmid D \)，那么解无法提升到模 \( p^2 \) 及以上，所以对于 \( k \ge 2 \)，方程 \( y^2 \equiv D \pmod{p^k} \) 无解 。 情况C的推广（\( D \) 是模 \( p \) 的二次非剩余） ：既然模 \( p \) 都无解，那么模 \( p^k \) 也必然无解。 回代求解 \( x \) ：和模奇素数的情况一样，对于每个解出的 \( y \)，线性方程 \( 2ax + b \equiv y \pmod{p^k} \) 因为 \( \gcd(2a, p^k)=1 \) 而有唯一解。所以，简化方程 \( y^2 \equiv D \) 的解数直接决定了原方程 \( ax^2+bx+c \equiv 0 \) 的解数。 结论（模奇素数的幂 \( p^k \)） ：解数情况比模 \( p \) 时复杂，但核心仍然依赖于 \( D \) 和 \( p \) 的关系。最常见的情况是 \( p \nmid D \) 且 \( D \) 是二次剩余，此时原方程有 2 个解 。 第四步：当模数是任意正整数 \( m \) 根据中国剩余定理，要解模 \( m \) 的同余方程，可以先将 \( m \) 分解为素数的幂次：\( m = p_ 1^{k_ 1} p_ 2^{k_ 2} \dots p_ r^{k_ r} \)。 方程 \( ax^2 + bx + c \equiv 0 \pmod{m} \) 有解，当且仅当它对每一个素因子幂 \( p_ i^{k_ i} \) 都有解。 如果对每个 \( p_ i^{k_ i} \) 都有解，设解数分别为 \( N_ 1, N_ 2, \dots, N_ r \)。 那么，模 \( m \) 下的解的总数 \( N \) 就是这些解数的乘积： \[ N = N_ 1 \times N_ 2 \times \dots \times N_ r \] 因此，求解任意模数 \( m \) 的二次同余方程，其解数问题最终归结为求解模是奇素数幂（以及特殊的 \( p=2 \) 的幂，其分析更为复杂，但思路类似）的解数问题。