同余方程

定义

同余方程

对正整数 $m$ 和一元整系数多项式 $f(x)=\sum _{i=0}^n{a}_i{x}^i$，其中未知数 $x\in {\mathbf{Z}}_m$，称形如

$$\begin{array}{}\text{(1)}& f(x)\equiv 0(\mathrm{mod}m)\end{array}$$

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

若 $a_n\not\equiv 0(\mathrm{mod}m)$，则称上式为 $n$ 次同余方程。

类似可定义同余方程组。

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

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

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

素数幂模同余方程

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

注意到若 $x_0$ 是方程

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

的解，则 $x_0$ 是方程

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

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

定理 1

对素数 $p$ 和整数 $a>1$，取整系数多项式 $f(x)=\sum _{i=0}^n{a}_i{x}^i(p^a\nmid a_n)$，令 $f^{\prime }(x)=\sum _{i=1}^{n}i{a}_i{x}^{i-1}$ 为其导数。令 $x_0$ 为方程

$$\begin{array}{}\text{(2)}& f(x)\equiv 0(\mathrm{mod}{p}^{a-1})\end{array}$$

的解，则：

1. 若 $f^{\prime }(x_0)\not\equiv 0(\mathrm{mod}p)$, 则存在整数 $t$ 使得

   $$\begin{array}{}\text{(3)}& x=x_0+p^{a-1}t\end{array}$$

   是方程

   $$\begin{array}{}\text{(4)}& f(x)\equiv 0(\mathrm{mod}{p}^a)\end{array}$$

   的解。

2. 若 $f^{\prime }(x_0)\equiv 0(\mathrm{mod}p)$ 且 $f(x_0)\equiv 0(\mathrm{mod}{p}^a)$, 则对 $t=0,1,\dots ,p-1$，由式 $(3)$ 确定的 $x$ 均为方程 $(4)$ 的解。

3. 若 $f^{\prime }(x_0)\equiv 0(\mathrm{mod}p)$ 且 $f(x_0)\not\equiv 0(\mathrm{mod}{p}^a)$, 则不能由式 $(3)$ 构造方程 $(4)$ 的解。

证明

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

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

整理后可得

$$f(x_0)+p^{a-1}t{f}^{\prime }(x_0)\equiv 0(\mathrm{mod}{p}^a)$$

于是

$$\begin{array}{}\text{(5)}& t{f}^{\prime }(x_0)\equiv -\frac{f(x_0)}{p^{a-1}}(\mathrm{mod}p)\end{array}$$

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

进而我们有推论：

推论 1

对 定理 1 的 $p$，$a$，$f(x)$，$x_0$，

1. 若 $s$ 是方程 $f(x)\equiv 0(\mathrm{mod}p)$ 的解，且 $f^{\prime }(a)\not\equiv 0(\mathrm{mod}p)$，则存在 $x_s\in {\mathbf{Z}}_{p^a}$，$x_s\equiv s(\mathrm{mod}p)$ 使得 $x_s$ 是方程 $(4)$ 的解。
2. 若方程 $f(x)\equiv 0(\mathrm{mod}p)$ 与 $f^{\prime }(a)\equiv 0(\mathrm{mod}p)$ 无公共解，则方程 $(4)$ 和方程 $f(x)\equiv 0(\mathrm{mod}p)$ 的解数相同。

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

素数模同余方程

以下令 $p\in \mathbf{P}$，整系数多项式 $f(x)=\sum _{i=0}^n{a}_i{x}^i$，其中 $p\nmid a_n$，$x\in {\mathbf{Z}}_p$.

定理 2

若方程

$$\begin{array}{}\text{(6)}& f(x)\equiv 0(\mathrm{mod}p)\end{array}$$

有 $k$ 个不同的解 $x_1,x_2,\dots ,x_k(k\le n)$，则：

$$f(x)\equiv g(x)\prod _{i=1}^k(x-x_i)(\mathrm{mod}p)$$

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

推论 2

对素数 $p$，

• $(\mathrm{\forall }x\in \mathbf{Z}),x^{p-1}-1\equiv \prod _{i=1}^{p-1}(x-i)(\mathrm{mod}p)$
• （Wilson 定理）$(p-1)!\equiv -1(\mathrm{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)(\mathrm{mod}p)$$

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

$$0\equiv f(x_{n+1})\equiv a_n\prod _{i=1}^n(x_{n+1}-x_i)(\mathrm{mod}p)$$

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

推论 3

若同余方程 $\sum _{i=0}^n{b}_i{x}^i\equiv 0(\mathrm{mod}p)$ 的解数大于 $n$，则

$$(\mathrm{\forall }i=0,1,\dots ,n),p\mid b_i$$

定理 4

方程 $(6)$ 若解的个数不为 $p$，则必存在满足 $\mathrm{deg}r<p$ 的整系数多项式 $r(x)$ 使得 $f(x)\equiv 0(\mathrm{mod}p)$ 和 $r(x)\equiv 0(\mathrm{mod}p)$ 的解集相同。

证明

不妨设 $n\ge p$，对 $f(x)$ 做多项式带余除法

$$f(x)=g(x)(x^p-x)+r(x)$$

其中 $\mathrm{deg}r<p$.

由 Fermat 小定理 知对任意整数 $x$ 有 $x^p\equiv x(\mathrm{mod}p)$，从而

• 若 $r(x)\equiv 0(\mathrm{mod}p)$，则由 推论 2 可知 $f(x)$ 有 $p$ 个不同的解。
• 若 $r(x)\not\equiv 0(\mathrm{mod}p)$，则由 $f(x)\equiv r(x)(\mathrm{mod}p)$ 可知 $f(x)$ 和 $r(x)$ 的解集相同。

我们可以通过这个定理对同余方程降次。

定理 5

设 $n\le p$，则方程

$$\begin{array}{}\text{(7)}& x^n+\sum _{i=0}^{n-1}{a}_i{x}^i\equiv 0(\mathrm{mod}p)\end{array}$$

有 $n$ 个解当且仅当存在整系数多项式 $q(x)$，$r(x)(\mathrm{deg}r<n)$ 使得

$$\begin{array}{}\text{(8)}& x^p-x=f(x)q(x)+pr(x)\end{array}$$

对于非首 1 多项式，由于 ${\mathbf{Z}}_p$ 是域，故可以将其化为首 1 多项式，从而适用该定理。

定理 6

设 $n\nmid p-1$，$p\nmid a$, 则方程

$$\begin{array}{}\text{(9)}& x^n\equiv a(\mathrm{mod}p)\end{array}$$

有解当且仅当

$$a^{\frac{p-1}{n}}\equiv 1(\mathrm{mod}p)$$

且若 $(9)$ 有解，则解数为 $n$.

高次同余方程（组）的求解方法

首先我们可以借助 中国剩余定理 将求解 同余方程组 转为求解 同余方程，以及将求解模 合数 $m$ 的同余方程转化为求解模 素数幂次 的同余方程。之后我们借助 定理 1 将求解模 素数幂次 的同余方程转化为求解模 素数 的同余方程。

结合模素数同余方程的若干定理，我们只需考虑方程

$$x^n+\sum _{i=0}^{n-1}{a}_i{x}^i\equiv 0(\mathrm{mod}p)$$

的求法，其中 $p$ 是素数，$n<p$.

我们可以通过将 $x$ 代换为 $x-{\displaystyle \frac{a_{n-1}}{n}}$ 来消去 $x^{n-1}$ 项，从而我们只需考虑方程

$$\begin{array}{}\text{(10)}& x^n+\sum _{i=0}^{n-2}{a}_i{x}^i\equiv 0(\mathrm{mod}p)\end{array}$$

的求法，其中 $p$ 是素数，$n<p$.

• 若 $n=1$，则求法参见 线性同余方程。
• 若 $n=2$，则求法参见 二次剩余。

• 若方程 $(10)$ 可化为

  $$x^n\equiv a(\mathrm{mod}p)$$

  则求法参见 k 次剩余。

参考资料

1. Congruence Equation -- from Wolfram MathWorld
2. Lagrange's theorem (number theory) - Wikipedia
3. 潘承洞，潘承彪。初等数论。
4. 冯克勤。初等数论及其应用。
5. 闵嗣鹤，严士健。初等数论。

本页面最近更新：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 协议之条款下提供，附加条款亦可能应用