二次同余方程的解的公式
我们继续讨论二次同余方程。你已经了解了如何判断解的存在性（通过勒让德符号和二次互反律），现在我们来探讨一个核心问题：如果一个二次同余方程有解，我们能否找到一个直接的公式来计算出它的解？
答案是肯定的，但这个过程需要分情况讨论，并且依赖于我们之前学过的模逆元和二次剩余等概念。
第一步：简化问题——模奇素数幂的方程
一个一般的二次同余方程形式为 \(ax^2 + bx + c \equiv 0 \pmod{m}\)。根据中国剩余定理，求解模 \(m\) 的方程可以转化为求解模 \(m\) 的素数幂因子 \(p^k\) 的方程。因此，我们首先需要解决模数为奇素数 \(p\) 的方程，然后再推广到模奇素数幂 \(p^k\) (k>1) 的情况。最后，再单独处理模 \(2^k\) 的特殊情况。
我们先从最基础、最重要的情形开始：模奇素数 \(p\)。
第二步：求解模奇素数 \(p\) 的方程 \(x^2 \equiv a \pmod{p}\)
这是最简单的情形，其中 \(a\) 是模 \(p\) 的二次剩余，即勒让德符号 \(\left(\frac{a}{p}\right) = 1\)。
- 问题转化：我们的目标是找到所有满足 \(x^2 \equiv a \pmod{p}\) 的整数 \(x\)。
- 关键思路——随机搜索：当 \(p\) 很大时，并没有一个非常快速、确定性的通用公式来直接找到一个解。一个常见的方法是随机尝试。我们随机选择一个数 \(c\) (\(1 \le c \le p-1\))，计算勒让德符号 \(\left(\frac{c^2 - a}{p}\right)\)。如果这个符号等于 -1（即 \(c^2 - a\) 是模 \(p\) 的二次非剩余），那么我们就找到了一个关键的“见证”。
- Tonelli-Shanks 算法的核心思想：假设我们找到了一个 \(c\)，使得 \(c^2 - a\) 是二次非剩余。令 \(d = c^2 - a\)。那么，在某种扩大的数系（模 \(p\) 的二次域）中，\(\sqrt{d}\) 是存在的。利用这个思想，可以构造出解。
- 一个更具体但不那么严格的表述是：解可以由下式给出：
\(x \equiv (c + \sqrt{d})^{(p+1)/2} \pmod{p}\)
- 一个更具体但不那么严格的表述是：解可以由下式给出：
- 这里的 \(\sqrt{d}\) 并不是在整数模 \(p\) 意义下的数，但它指引了一个有效的计算方法。Tonelli-Shanks 算法 就是一个基于这个思想的、高效的计算程序，它通过将 \(p-1\) 分解为 \(Q \cdot 2^S\)（其中 \(Q\) 是奇数），然后进行迭代，最终找到解。
- 解的个数：根据之前的知识，如果 \(a \not\equiv 0 \pmod{p}\) 且是二次剩余，那么方程 \(x^2 \equiv a \pmod{p}\) 恰好有两个解。如果我们找到了一个解 \(x_0\)，那么另一个解就是 \(-x_0\)。
总结（模奇素数）：对于 \(x^2 \equiv a \pmod{p}\)，当解存在时，虽然没有一个像求根公式那样简单的封闭表达式，但存在有效的算法（如 Tonelli-Shanks 算法）可以计算出解。这两个解互为相反数。
第三步：求解模奇素数幂 \(p^k\) 的方程 \(x^2 \equiv a \pmod{p^k}\)
现在我们将问题提升到模 \(p^k\) (k>1) 的情形。这里我们使用一种称为 Hensel 引理 的强大工具。
- Hensel 引理（提升引理）：这个引理告诉我们，如何将一个模 \(p^k\) 的方程的解“提升”为模 \(p^{k+1}\) 的解。
- 应用过程：
- 基础步骤：首先，求解模 \(p\) 的方程 \(x^2 \equiv a \pmod{p}\)。假设我们找到了一个解 \(x_1\)，满足 \(x_1^2 \equiv a \pmod{p}\)。
- 提升步骤：现在我们想找到一个解 \(x_2\)，满足 \(x_2^2 \equiv a \pmod{p^2}\)，并且 \(x_2 \equiv x_1 \pmod{p}\)。我们设 \(x_2 = x_1 + p \cdot t_1\)，其中 \(t_1\) 是待确定的整数。
- 将 \(x_2\) 代入方程：
\((x_1 + p t_1)^2 \equiv a \pmod{p^2}\)
\(x_1^2 + 2 x_1 p t_1 + p^2 t_1^2 \equiv a \pmod{p^2}\)
由于 \(p^2 t_1^2 \equiv 0 \pmod{p^2}\)，我们得到：
\(x_1^2 + 2 x_1 p t_1 \equiv a \pmod{p^2}\) - 因为 \(x_1^2 \equiv a \pmod{p}\)，所以 \(x_1^2 - a\) 能被 \(p\) 整除，记 \(x_1^2 - a = p \cdot M\)。那么上面的同余式变为：
\(p \cdot M + 2 x_1 p t_1 \equiv 0 \pmod{p^2}\)
两边同时除以 \(p\)：
\(M + 2 x_1 t_1 \equiv 0 \pmod{p}\)
\(2 x_1 t_1 \equiv -M \pmod{p}\) - 这是一个关于 \(t_1\) 的线性同余方程。由于 \(p\) 是奇素数，且 \(x_1 \not\equiv 0 \pmod{p}\)（因为 \(a \not\equiv 0 \pmod{p}\)），所以 \(2x_1\) 在模 \(p\) 下有逆元。因此，我们可以解出唯一的 \(t_1 \pmod{p}\)：
\(t_1 \equiv -M \cdot (2x_1)^{-1} \pmod{p}\) - 这样就得到了模 \(p^2\) 的一个解 \(x_2 = x_1 + p \cdot t_1\)。
- 这个提升过程可以重复进行，从模 \(p^2\) 提升到模 \(p^3\)，依此类推，直到模 \(p^k\)。
总结（模奇素数幂）：只要方程在模 \(p\) 下有解，并且 \(a\) 不被 \(p\) 整除（即解不是“奇异的”），那么我们就可以通过 Hensel 引理，将这个解唯一地提升到任意高的素数幂 \(p^k\)。对于每个模 \(p\) 的解，在模 \(p^k\) 下也恰好对应一个解。
第四步：求解一般二次方程 \(ax^2 + bx + c \equiv 0 \pmod{p}\)
现在我们来处理带一次项的一般形式。
-
配方：方法和解实数域中的二次方程类似，我们通过配方来简化。
\(ax^2 + bx + c \equiv 0 \pmod{p}\)
两边乘以 \(4a\) 的模 \(p\) 逆元 \((4a)^{-1}\) 不是必须的，更直接的方法是确保 \(a\) 有逆元。因为 \(p\) 是奇素数且 \(p \nmid a\)，所以 \(a\) 在模 \(p\) 下有逆元。两边乘以 \(4a\)：
\(4a^2x^2 + 4abx + 4ac \equiv 0 \pmod{p}\)
\((2ax)^2 + 2 \cdot (2ax) \cdot b + 4ac \equiv 0 \pmod{p}\)
为了配方，我们需要加上 \(b^2\) 再减去它：
\((2ax)^2 + 2 \cdot (2ax) \cdot b + b^2 - b^2 + 4ac \equiv 0 \pmod{p}\)
\((2ax + b)^2 \equiv b^2 - 4ac \pmod{p}\) -
变量代换：令 \(y = 2ax + b\)，且令 \(D = b^2 - 4ac\)。方程简化为：
\(y^2 \equiv D \pmod{p}\) -
求解：这样我们就回到了第二步中的形式。首先判断 \(D\) 是否是模 \(p\) 的二次剩余（计算 \(\left(\frac{D}{p}\right)\)）。
- 如果 \(\left(\frac{D}{p}\right) = -1\)，无解。
- 如果 \(\left(\frac{D}{p}\right) = 0\)，即 \(D \equiv 0 \pmod{p}\)，则有一个解 \(y \equiv 0 \pmod{p}\)。
- 如果 \(\left(\frac{D}{p}\right) = 1\)，则有两个解 \(y \equiv y_0 \pmod{p}\) 和 \(y \equiv -y_0 \pmod{p}\)。
- 回代：最后，将 \(y\) 的解代回 \(x\) 的表达式：
\(2ax + b \equiv y_0 \pmod{p}\)
\(x \equiv (y_0 - b) \cdot (2a)^{-1} \pmod{p}\)
对另一个解 \(y \equiv -y_0\) 做同样的操作，就得到了原方程的两个解。
这个推导过程给出了一个清晰的“公式化”求解路径：配方 -> 求解简化后的二次剩余方程 -> 回代。