一元二次同余方程

我们借助二次剩余的概念对二次同余方程做一个完整的刻画。

定义

设$a,b,c$是整数，$a,m$非零，那么称下面的关于$x$的同余方程为二次同余方程：

$$a x^2 + b x + c \equiv 0 \pmod{m}$$

其中，这个方程由四个参数$a,b,c,m$确定，$m$提供了求解的域。

模为素数的情形

当$m=p$为素数时，形如上式的方程总可以化为下面的形式

$$x^2 \equiv d \pmod{p}$$

这是因为，在域$\Z_{p}$中除零元外元素（$\overline{a} \ne \overline{0}$）存在逆元，于是

$$\begin{align} \overline{a} x^2 + \overline{b} x + \overline{c} & = \overline{0} \\ \overline{a} \big(2 \overline{x} + \overline{a}^{-1} \overline{b} \big)^2 + 4 \overline{c} - \overline{b}^2 (\overline{a}^{-1})^2 & = \overline{0} \\ \big( 2 \overline{x} + \overline{a}^{-1} \overline{b} \big)^2 & = (\overline{a}^{-1})^2 ( \overline{b}^2 - 4 \overline{a} \overline{c} ). \end{align}$$

令$\overline{y} = 2 \overline{x} + \overline{a}^{-1} \overline{b}, \overline{d} = (\overline{a}^{-1})^2 ( \overline{b}^2 - 4 \overline{a} \overline{c} )$，于是原方程化为了$\overline{y}^2 = \overline{d}.$因此，仅需解出形如$y^2 \equiv d \pmod{p}$的方程，一般的模为素数的二次同余方程就可解了。

这种方程的求解，就是二次剩余中 Legendre 符号的直接应用，仅需计算$1 + \left(\dfrac{d}{p}\right)$即可知道这个方程有多少个解，在有解时很容易求出它的解。

模为素数的幂次的情形

定理：

1. 设$p$为奇素数，$(a, p) = 1$，则同余方程$x^2 \equiv a \pmod{p^k}$有解的充要条件是$\left(\dfrac{a}{p}\right) = 1$，且在有解时解为$x \equiv \pm b \pmod{p^k};$
2. 设$a$为奇数，$k \geqslant 3$，则同余方程$x^2 \equiv a \pmod{2^k}$有解的充要条件是$a \equiv 1 \pmod{8}$，且在有解时解为$x \equiv \pm b, \pm b + 2^{k-1} \pmod{2^k}.$

证明是构造性的，我们不打算赘述。我们使用一种$p$进制展开的方法求解这类方程$x^2 \equiv a \pmod{p^k}$。

设$x \equiv x_0 + x_1 p + x_2 p^2 + \cdots + x_{k-1} p^{k-1} \pmod{p^k}, 0 \leqslant x_i \leqslant p-1$，我们先求解$x^2 \equiv a \pmod{p}$，即$(x_0 + x_1 p + x_2 p^2 + \cdots + x_{k-1} p^{k-1})^2 \equiv a \pmod{p}$，即$x_0^2 \equiv a \pmod{p}$，求出一个符合要求的$x_0$代入$x$，再解$x^2 \equiv a \pmod{p^2}$，求出一个$x_1$，这样一直继续下去就可以求出一个$x$，再根据定理即可求出所有的$x$。

模为任意非零数的情形

有了上面的准备，我们考察一般情形$a x^2 + b x + c \equiv 0 \pmod{m}$，假设$m = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$它可以写成如下多个同余方程的联立

$$\begin{cases} a x^2 + b x + c \equiv 0 \pmod{p_1^{k_1}} \\ a x^2 + b x + c \equiv 0 \pmod{p_2^{k_2}} \\ \cdots \\ a x^2 + b x + c \equiv 0 \pmod{p_r^{k_r}} \end{cases}$$

解出每个方程，再由中国剩余定理找到所有解即可。

上下节

• 上一节：Jacobi 符号
• 下一节：不定方程