同余方程

定义

同余方程

对正整数 $m$ 和一元整系数多项式 $f (x) = \sum_{i = 0}^{n} a_{i} x^{i}$ ，其中未知数 $x \in Z_{m}$ ，称形如

\begin{matrix} (1) & f (x) \equiv 0 (\mod m) \end{matrix}

的方程为关于未知数 $x$ 的模 $m$ 的一元 同余方程（Congruence Equation）。

若 $a_{n} ≢ 0 (\mod m)$ ，则称上式为 $n$ 次同余方程。

类似可定义同余方程组。

关于一次同余方程与方程组的相关内容请参见线性同余方程与中国剩余定理。

本文首先研究同余方程的可解性和解集结构，之后会简要介绍高次同余方程的解法。

由中国剩余定理可知，求解关于模合数 $m$ 的同余方程可转化为求解模素数幂次的情况。故以下只介绍素数幂模同余方程和素数模同余方程的相关理论。

素数幂模同余方程

以下假设模数 $m = p^{a} (p \in P, a \in Z_{> 1})$ .

注意到若 $x_{0}$ 是方程

f (x) \equiv 0 (\mod p^{a})

的解，则 $x_{0}$ 是方程

f (x) \equiv 0 (\mod p^{a - 1})

的解，这启发我们尝试通过较低的模幂次的解去构造较高的模幂次的解。我们有如下定理：

定理 1

对素数 $p$ 和整数 $a > 1$ ，取整系数多项式 $f (x) = \sum_{i = 0}^{n} a_{i} x^{i} (p^{a} ∤ a_{n})$ ，令 $f^{'} (x) = \sum_{i = 1}^{n} i a_{i} x^{i - 1}$ 为其导数。令 $x_{0}$ 为方程

\begin{matrix} (2) & f (x) \equiv 0 (\mod p^{a - 1}) \end{matrix}

的解，则：

若 $f^{'} (x_{0}) ≢ 0 (\mod p)$ , 则存在整数 $t$ 使得
$\begin{matrix} (3) & x = x_{0} + p^{a - 1} t \end{matrix}$
是方程
$\begin{matrix} (4) & f (x) \equiv 0 (\mod p^{a}) \end{matrix}$
的解。
若 $f^{'} (x_{0}) \equiv 0 (\mod p)$ 且 $f (x_{0}) \equiv 0 (\mod p^{a})$ , 则对 $t = 0, 1, \dots, p - 1$ ，由式 $(3)$ 确定的 $x$ 均为方程 $(4)$ 的解。
若 $f^{'} (x_{0}) \equiv 0 (\mod p)$ 且 $f (x_{0}) ≢ 0 (\mod p^{a})$ , 则不能由式 $(3)$ 构造方程 $(4)$ 的解。

证明

我们假设式 $(3)$ 是方程 $(4)$ 的解，即

f (x_{0} + p^{a - 1} t) \equiv 0 (\mod p^{a})

整理后可得

f (x_{0}) + p^{a - 1} t f^{'} (x_{0}) \equiv 0 (\mod p^{a})

于是

\begin{matrix} (5) & t f^{'} (x_{0}) \equiv - \frac{f (x_{0})}{p^{a - 1}} (\mod p) \end{matrix}

若 $f^{'} (x_{0}) ≢ 0 (\mod p)$ ，则关于 $t$ 的方程 $(5)$ 有唯一解 $t_{0}$ ，代入式 $(3)$ 可验证其为方程 $(4)$ 的解。
若 $f^{'} (x_{0}) \equiv 0 (\mod p)$ 且 $f (x_{0}) \equiv 0 (\mod p^{a})$ ，则任意 $t$ 均能使方程 $(5)$ 成立，代入式 $(3)$ 可验证其均为方程 $(4)$ 的解。
若 $f^{'} (x_{0}) \equiv 0 (\mod p)$ 且 $f (x_{0}) ≢ 0 (\mod p^{a})$ ，则方程 $(5)$ 无解，从而不能由式 $(3)$ 构造方程 $(4)$ 的解。

进而我们有推论：

推论 1

对定理 1 的 $p$ ， $a$ ， $f (x)$ ， $x_{0}$ ，

若 $s$ 是方程 $f (x) \equiv 0 (\mod p)$ 的解，且 $f^{'} (a) ≢ 0 (\mod p)$ ，则存在 $x_{s} \in Z_{p^{a}}$ ， $x_{s} \equiv s (\mod p)$ 使得 $x_{s}$ 是方程 $(4)$ 的解。
若方程 $f (x) \equiv 0 (\mod p)$ 与 $f^{'} (a) \equiv 0 (\mod p)$ 无公共解，则方程 $(4)$ 和方程 $f (x) \equiv 0 (\mod p)$ 的解数相同。

从而我们可以将素数幂模同余方程化归到素数模同余方程的情况。

素数模同余方程

以下令 $p \in P$ ，整系数多项式 $f (x) = \sum_{i = 0}^{n} a_{i} x^{i}$ ，其中 $p ∤ a_{n}$ ， $x \in Z_{p}$ .

定理 2

若方程

\begin{matrix} (6) & f (x) \equiv 0 (\mod p) \end{matrix}

有 $k$ 个不同的解 $x_{1}, x_{2}, \dots, x_{k} (k \leq n)$ ，则：

f (x) \equiv g (x) \prod_{i = 1}^{k} (x - x_{i}) (\mod p)

其中 $\deg g = n - k$ 且 $[x^{n - k}] g (x) = a_{n}$ .

证明

对 $k$ 应用数学归纳法。

当 $k = 1$ 时，做多项式带余除法，有 $f (x) = (x - x_{1}) g (x) + r$ ，其中 $r \in Z$ .

由 $f (x_{1}) \equiv 0 (\mod p)$ 可知 $r \equiv 0 (\mod p)$ ，从而 $f (x) \equiv (x - x_{1}) g (x) (\mod p)$ .
假设命题对 $k - 1$ ( $k > 1$ ) 时的情况成立，现在设 $f (x)$ 有 $k$ 个不同的解 $x_{1}, x_{2}, \dots, x_{k}$ , 则 $f (x) \equiv (x - x_{1}) h (x) (\mod p)$ , 进而有
$(\forall i = 2, 3, \dots, k), 0 \equiv f (x_{i}) \equiv (x_{i} - x_{1}) h (x_{i}) (\mod p)$
从而 $h (x)$ 有 $k - 1$ 个不同的解 $x_{2}, x_{3}, \dots, x_{k}$ , 由归纳假设有
$h (x) \equiv g (x) \prod_{i = 2}^{k} (x - x_{i}) (\mod p)$
其中 $\deg g = n - k$ 且 $[x^{n - k}] g (x) = a_{n}$ .

因此命题得证。

推论 2

对素数 $p$ ，

$(\forall x \in Z), x^{p - 1} - 1 \equiv \prod_{i = 1}^{p - 1} (x - i) (\mod p)$
（Wilson 定理） $(p - 1)! \equiv - 1 (\mod p)$

定理 3（Lagrange 定理）

方程 $(6)$ 至多有 $n$ 个不同解。

证明

假设 $f (x)$ 有 $n + 1$ 个不同解 $x_{1}, x_{2}, \dots, x_{n + 1}$ ，则由定理 2，对 $x_{1}, x_{2}, \dots, x_{n}$ 有

f (x) \equiv a_{n} \prod_{i = 1}^{n} (x - x_{i}) (\mod p)

令 $x = x_{n + 1}$ , 则

0 \equiv f (x_{n + 1}) \equiv a_{n} \prod_{i = 1}^{n} (x_{n + 1} - x_{i}) (\mod p)

而右侧显然不是 $p$ 的倍数，因此假设矛盾。

推论 3

若同余方程 $\sum_{i = 0}^{n} b_{i} x^{i} \equiv 0 (\mod p)$ 的解数大于 $n$ ，则

(\forall i = 0, 1, \dots, n), p ∣ b_{i}

定理 4

方程 $(6)$ 若解的个数不为 $p$ ，则必存在满足 $\deg r

本页面最近更新：2025/3/6 13:28:22，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, aofall, c-forrest, CCXXXI, CoelacanthusHex, Great-designer, iamtwz, Marcythm, Persdre, shuzhouliu, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用