二次同余方程的解的结构
我们从二次同余方程的一般形式开始。一个二次同余方程可以写为：
\(ax^2 + bx + c \equiv 0 \pmod{m}\)
其中 \(a \not\equiv 0 \pmod{m}\)。
第一步：化简为首项系数为1的形式
如果 \(\gcd(a, m) = 1\)（即 \(a\) 和 \(m\) 互质），我们可以将方程两边同时乘以 \(a\) 在模 \(m\) 下的逆元 \(a^{-1}\)。这样，方程就变为：
\(x^2 + a^{-1}b x + a^{-1}c \equiv 0 \pmod{m}\)。
为了更清晰地研究解的性质，我们通常通过“配方”来简化方程。这与解实数域中的二次方程方法类似。
第二步：通过配方进行变量代换
我们考虑化简后的方程：
\(x^2 + px + q \equiv 0 \pmod{m}\) (其中 \(p = a^{-1}b, q = a^{-1}c\)）。
为了消去一次项，我们进行变量代换：\(y = x + \frac{p}{2}\)。但在模运算中，“除以2”需要特别小心，因为这要求2在模 \(m\) 下有逆元，即 \(\gcd(2, m) = 1\)。我们先假设 \(m\) 是奇数，满足这个条件。
进行代换：
\(x = y - \frac{p}{2}\)（这里 \(\frac{p}{2}\) 表示 \(p\) 乘以2的模逆元）。
将其代入方程：
\((y - p/2)^2 + p(y - p/2) + q \equiv 0 \pmod{m}\)
展开：
\(y^2 - py + (p/2)^2 + py - p^2/2 + q \equiv 0 \pmod{m}\)
可以看到，\(-py\) 和 \(+py\) 相互抵消，整理常数项后，方程简化为：
\(y^2 \equiv D \pmod{m}\)
其中 \(D = (p/2)^2 - q\) 是一个常数。
这个新方程 \(y^2 \equiv D \pmod{m}\) 就是标准的二次剩余问题。如果这个关于 \(y\) 的方程有解，那么原方程的解可以通过逆代换 \(x = y - p/2\) 得到。
第三步：处理模为2的幂的情况
当 \(m\) 是2的幂（\(m = 2^k\)）时，情况更为复杂，因为2在模 \(2^k\) 下没有逆元，无法直接进行上述配方。我们需要直接分析原方程 \(ax^2 + bx + c \equiv 0 \pmod{2^k}\)。
- 模2的情况 (k=1)：模2的剩余类只有0和1。我们只需将x=0和x=1分别代入方程，检查是否同余于0即可。解的情况很简单，但它是研究更高次幂的基础。
- 模4、模8等更高次幂的情况 (k>1)：我们使用“提升法”。基本思想是，如果一个解 \(x_1\) 满足模 \(2^k\)，那么它必然也满足模 \(2^{k-1}\)。因此，我们从模2的解开始，尝试将其“提升”为模4的解，再提升为模8的解，依此类推。在每一步提升中，我们需要解一个线性同余方程来确定如何修正当前解，使其满足更高的模数。这个过程比模奇素数幂要繁琐，因为导数的奇偶性会影响解的数量和提升的可能性。
第四步：利用中国剩余定理处理合数模
当模数 \(m\) 是一个合数时，我们可以将其分解为素数次幂的乘积：\(m = p_1^{k_1} p_2^{k_2} \dots p_r^{k_r}\)。
根据中国剩余定理，解方程 \(ax^2 + bx + c \equiv 0 \pmod{m}\) 等价于解方程组：
\(ax^2 + bx + c \equiv 0 \pmod{p_i^{k_i}}\)，对于 \(i = 1, 2, \dots, r\)。
原方程的解数等于所有模 \(p_i^{k_i}\) 的方程的解数的乘积。
因此，求解合数模的二次同余方程问题，就转化为求解模为奇素数幂 \(p^k\) 和模为2的幂 \(2^k\) 的二次同余方程问题。
第五步：解的数量（模奇素数幂）
对于模奇素数幂 \(p^k\) (k >= 1) 的方程 \(ax^2 + bx + c \equiv 0 \pmod{p^k}\)：
- 模奇素数p (k=1)：这是我们熟悉的情况。通过配方，问题转化为判断 \(D\) 是否是模 \(p\) 的二次剩余（利用勒让德符号）。
- 如果 \(D \equiv 0 \pmod{p}\)，方程有一个解（重根）。
- 如果 \(D\) 是模 \(p\) 的二次剩余且不等于0，方程有两个不同的解。
- 如果 \(D\) 是模 \(p\) 的二次非剩余，方程无解。
- 模奇素数幂 \(p^k\) (k>1)：我们使用“亨泽尔引理”进行解的提升。
- 如果一个解 \(x_0\) 满足模 \(p\) 的方程，并且它满足“非奇异条件”（即导数 \(f'(x_0) = 2ax_0 + b \not\equiv 0 \pmod{p}\)），那么根据亨泽尔引理，存在唯一的解从模 \(p\) 提升到模 \(p^k\)。
- 如果一个解 \(x_0\) 满足模 \(p\) 的方程，但它是“奇异的”（即 \(f'(x_0) \equiv 0 \pmod{p}\)），那么提升情况更复杂：
- 如果 \(f(x_0) \equiv 0 \pmod{p^{k}}\) 已经成立，那么这个解可以提升为 \(p\) 个不同的解模 \(p^{k}\)。
* 否则，它无法提升到更高的模数。
总结
二次同余方程解的结构可以系统地构建如下：
- 化简：通过乘逆元将二次项系数化为1。
- 配方：当模为奇数时，通过变量代换将方程化为标准的二次剩余形式 \(y^2 \equiv D\)。解的存在性由 \(D\) 的二次剩余性质决定。
- 分解模数：利用中国剩余定理，将合数模 \(m\) 的问题分解为模其素数次幂 \(p_i^{k_i}\) 的问题。
- 提升解：对于每个素数次幂 \(p^k\)：
- 从模 \(p\) 的解开始。
- 使用亨泽尔引理（对于奇素数p）或直接计算（对于p=2）将解从模 \(p\) 提升到模 \(p^k\)。
- 组合解：最后，将所有素数次幂的解通过中国剩余定理组合起来，得到模 \(m\) 的解。
这个结构表明，解二次同余方程的核心在于处理模素数幂的情形，而模素数幂的解又由模素数的解通过“提升”而来。解的数量可以是0、1、2，或者在模为合数且存在奇异解的情况下更多。