二次同余方程
二次同余方程是数论中的一个核心概念，它研究的是形如 \(ax^2 + bx + c \equiv 0 \pmod{m}\) 的方程。我们将从最基础的形式开始，逐步深入。
- 基本定义与化简
一个一般的二次同余方程写作：
\[ ax^2 + bx + c \equiv 0 \pmod{m} \]
其中 \(a, b, c\) 是整数，\(m\) 是正整数（模数），并且 \(a \not\equiv 0 \pmod{m}\)。
我们的首要目标是化简这个方程。由于您已经了解模运算和同余，我们知道可以对方程进行类似代数方程的变形，但每一步都要考虑模 \(m\) 的意义。
- 情况一：模数 \(m\) 与系数 \(a\) 互质（即 \(\gcd(a, m) = 1\)）
这是最简单也是最关键的情况。因为 \(a\) 在模 \(m\) 下有逆元（您已学过模逆元），我们可以将方程两边同时乘以 \(a\) 的模逆元 \(a^{-1}\)，将二次项系数化为 1：
\[ x^2 + a^{-1}bx + a^{-1}c \equiv 0 \pmod{m} \]
为了更清晰地求解，我们通常采用“配方法”。这与求解实数域中的二次方程类似。具体步骤如下：
- 将方程两边乘以 \(4a\)（因为 \(\gcd(a, m)=1\)，所以 \(\gcd(4a, m)=1\) 或存在公共因子，但为确保通用性，我们更常用的是当 \(m\) 为奇素数时，若 \(\gcd(a, m)=1\)，则 \(\gcd(2a, m)=1\)。这里我们考虑 \(m\) 为奇素数的标准情况）。一个更通用的配方法思路是直接配方：
\[ ax^2 + bx + c \equiv 0 \pmod{m} \]
- 将常数项 \(c\) 移到右边：
\[ ax^2 + bx \equiv -c \pmod{m} \]
- 为了配方，我们希望二次项系数为1。两边乘以 \(a\) 的逆元 \(a^{-1}\)：
\[ x^2 + a^{-1}bx \equiv -a^{-1}c \pmod{m} \]
- 现在，对 \(x\) 的一次项系数 \(a^{-1}b\) 进行配方：取它的一半，然后平方。即，计算 \(d = (a^{-1}b \cdot 2^{-1})^2 \pmod{m}\)。这里 \(2^{-1}\) 是 2 在模 \(m\) 下的逆元（要求 \(m\) 是奇素数，从而 \(\gcd(2, m)=1\)）。
- 两边同时加上这个值 \(d\)：
\[ x^2 + a^{-1}bx + d \equiv -a^{-1}c + d \pmod{m} \]
- 左边现在是一个完全平方式：\((x + a^{-1}b \cdot 2^{-1})^2\)。
- 令 \(y = x + a^{-1}b \cdot 2^{-1} \pmod{m}\)，以及 \(k = -a^{-1}c + d \pmod{m}\)。于是，原方程被简化为一个极其简洁的形式：
\[ y^2 \equiv k \pmod{m} \]
- 核心问题：模数为奇素数时的平方同余
如上所述，当模数 \(m\) 是一个奇素数 \(p\)，并且 \(\gcd(a, p)=1\) 时，求解一般的二次同余方程最终归结为求解形如：
\[ x^2 \equiv a \pmod{p} \]
的方程，其中 \(p\) 是奇素数，且 \(p \nmid a\)（即 \(a \not\equiv 0 \pmod{p}\)）。
这正是您已经学过的 **二次剩余** 问题！
- 如果方程 \(x^2 \equiv a \pmod{p}\) 有解，我们称 \(a\) 是模 \(p\) 的二次剩余。
- 如果无解，则称 \(a\) 是模 \(p\) 的二次非剩余。
您已经了解勒让德符号 \(\left(\frac{a}{p}\right)\) 可以用来快速判断解的存在性：
\[ \left(\frac{a}{p}\right) = \begin{cases} 1 & \text{如果 } a \text{ 是模 } p \text{ 的二次剩余} \\ -1 & \text{如果 } a \text{ 是模 } p \text{ 的二次非剩余} \\ 0 & \text{如果 } p \mid a \end{cases} \]
因此，对于化简后的方程 \(y^2 \equiv k \pmod{p}\)，我们首先计算勒让德符号 \(\left(\frac{k}{p}\right)\)。
- 如果 \(\left(\frac{k}{p}\right) = -1\)，则方程无解，从而原二次同余方程也无解。
- 如果 \(\left(\frac{k}{p}\right) = 1\)，则方程有两个解（在模 \(p\) 的意义下）。假设我们通过某种算法（如Tonelli–Shanks算法，或对小的 \(p\) 直接尝试）找到了一个解 \(y_0\)，那么另一个解就是 \(-y_0\)，即 \(p - y_0\)。
- 最后，通过关系 \(x = y - a^{-1}b \cdot 2^{-1} \pmod{p}\)，我们可以从 \(y\) 的解得到原变量 \(x\) 的解。
- 模数为素数幂的情况
当模数 \(m\) 不是素数，而是一个素数幂 \(p^e\)（\(p\) 为奇素数，\(e \ge 1\)）时，情况变得复杂一些，但我们有一个强有力的工具：Hensel 引理。
Hensel 引理可以看作是在模 \(p\)-进数下的“牛顿迭代法”。它允许我们将模 \(p\) 的解“提升”到模 \(p^e\) 的解。
- 基本思想：假设我们想求解 \(f(x) \equiv 0 \pmod{p^e}\)，其中 \(f(x)\) 是一个多项式（比如我们的二次多项式）。
- 步骤：
- 基础解：首先求解模 \(p\) 下的方程 \(f(x) \equiv 0 \pmod{p}\)。设 \(x_1\) 是它的一个解。
- 迭代提升：如果这个解满足某种“非奇异”条件（对于二次方程，通常要求 \(f'(x_1) \not\equiv 0 \pmod{p}\)，即导数在解处模 \(p\) 不为零），那么存在唯一的解 \(x_e\) 模 \(p^e\)，使得 \(x_e \equiv x_1 \pmod{p}\)，并且 \(f(x_e) \equiv 0 \pmod{p^e}\)。
- 具体提升方法：从一个解 \(x_k\) 满足 \(f(x_k) \equiv 0 \pmod{p^k}\)，我们寻找形如 \(x_{k+1} = x_k + t p^k\) 的解，代入方程并利用泰勒展开，可以解出 \(t\)，从而得到模 \(p^{k+1}\) 的解。
对于二次同余方程，如果模 \(p\) 有解，并且解满足非奇异条件，那么我们可以逐步将其提升到模 \(p^e\) 的解。
- 一般合数模的情况
当模数 \(m\) 是一个任意的合数时，我们可以利用中国剩余定理（虽然您列表中未出现，但它是解决同余方程的基础工具）将其分解。
- 将 \(m\) 分解为其素数幂的乘积：\(m = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}\)。
- 原方程 \(ax^2 + bx + c \equiv 0 \pmod{m}\) 等价于方程组：
\[ \begin{cases} ax^2 + bx + c \equiv 0 \pmod{p_1^{e_1}} \\ ax^2 + bx + c \equiv 0 \pmod{p_2^{e_2}} \\ \vdots \\ ax^2 + bx + c \equiv 0 \pmod{p_k^{e_k}} \end{cases} \]
- 对每一个形如 \(ax^2 + bx + c \equiv 0 \pmod{p_i^{e_i}}\) 的方程，我们使用前面第1至3步的方法（可能涉及化简、判断二次剩余、使用Hensel引理）来求解。
- 如果每个素数幂模的方程都有解，那么原方程的解的个数就是每个素数幂模方程解个数的乘积。然后，我们可以利用中国剩余定理将这些来自不同模数的解组合起来，得到模 \(m\) 的解。
总结一下，求解二次同余方程是一个系统性的过程：从化简方程开始，核心是处理模奇素数时的二次剩余问题，然后利用Hensel引理扩展到素数幂，最后通过中国剩余定理处理一般的合数模。