跳转至

# 同余方程

## 定义

同余方程

对正整数 𝑚 m 和一元整系数多项式 𝑓(𝑥) =∑𝑛 𝑖=0 𝑎 𝑖 𝑥 𝑖 f(x)=∑i=0 n a i x i，其中未知数 𝑥 ∈𝐙 𝑚 x∈Z m，称形如

𝑓(𝑥)≡0(m o d 𝑚)(1)(1)f(x)≡0(mod m)

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

若 𝑎 𝑛 ≢0(m o d 𝑚)a n≢0(mod m)，则称上式为 𝑛 n 次同余方程．

类似可定义同余方程组．

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

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

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

## 素数幂模同余方程

以下假设模数 𝑚 =𝑝 𝑒 (𝑝 ∈𝐏, 𝑒 ∈𝐙>1)m=p e (p∈P, e∈Z>1)．

注意到，若 𝑥 0 x 0 是方程

𝑓(𝑥)≡0(m o d 𝑝 𝑒)f(x)≡0(mod p e)

的解，则 𝑥 0 x 0 是方程

𝑓(𝑥)≡0(m o d 𝑝 𝑒−1)f(x)≡0(mod p e−1)

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

定理 1（Hensel 引理）

对素数 𝑝 p 和整数 𝑒 >1 e>1，取整系数多项式 𝑓(𝑥) =∑𝑛 𝑖=0 𝑎 𝑖 𝑥 𝑖 (𝑝 𝑒 ∤𝑎 𝑛)f(x)=∑i=0 n a i x i (p e∤a n)，令 𝑓′(𝑥) =∑𝑛 𝑖=1 𝑖 𝑎 𝑖 𝑥 𝑖−1 f′(x)=∑i=1 n i a i x i−1 为其导数．令 𝑥 0 x 0 为方程

𝑓(𝑥)≡0(m o d 𝑝 𝑒−1)(2)(2)f(x)≡0(mod p e−1)

的解，则：

1. 若 𝑓′(𝑥 0) ≢0(m o d 𝑝)f′(x 0)≢0(mod p)，则存在整数 𝑡 t 使得

   𝑥=𝑥 0+𝑝 𝑒−1 𝑡(3)(3)x=x 0+p e−1 t

   是方程

   𝑓(𝑥)≡0(m o d 𝑝 𝑒)(4)(4)f(x)≡0(mod p e)

   的解．

2. 若 𝑓′(𝑥 0) ≡0(m o d 𝑝)f′(x 0)≡0(mod p) 且 𝑓(𝑥 0) ≡0(m o d 𝑝 𝑒)f(x 0)≡0(mod p e)，则对 𝑡 =0,1,…,𝑝 −1 t=0,1,…,p−1，由式 (3)(3) 确定的 𝑥 x 均为方程 (4)(4) 的解．

3. 若 𝑓′(𝑥 0) ≡0(m o d 𝑝)f′(x 0)≡0(mod p) 且 𝑓(𝑥 0) ≢0(m o d 𝑝 𝑒)f(x 0)≢0(mod p e)，则不能由式 (3)(3) 构造方程 (4)(4) 的解．

证明

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

𝑓(𝑥 0+𝑝 𝑒−1 𝑡)≡0(m o d 𝑝 𝑒)f(x 0+p e−1 t)≡0(mod p e)

整理后可得

𝑓(𝑥 0)+𝑝 𝑒−1 𝑡 𝑓′(𝑥 0)≡0(m o d 𝑝 𝑒)f(x 0)+p e−1 t f′(x 0)≡0(mod p e)

于是

𝑡 𝑓′(𝑥 0)≡−𝑓(𝑥 0)𝑝 𝑒−1(m o d 𝑝)(5)(5)t f′(x 0)≡−f(x 0)p e−1(mod p)

1. 若 𝑓′(𝑥 0) ≢0(m o d 𝑝)f′(x 0)≢0(mod p)，则关于 𝑡 t 的方程 (5)(5) 有唯一解 𝑡 0 t 0，代入式 (3)(3) 可验证其为方程 (4)(4) 的解．
2. 若 𝑓′(𝑥 0) ≡0(m o d 𝑝)f′(x 0)≡0(mod p) 且 𝑓(𝑥 0) ≡0(m o d 𝑝 𝑒)f(x 0)≡0(mod p e)，则任意 𝑡 t 均能使方程 (5)(5) 成立，代入式 (3)(3) 可验证其均为方程 (4)(4) 的解．
3. 若 𝑓′(𝑥 0) ≡0(m o d 𝑝)f′(x 0)≡0(mod p) 且 𝑓(𝑥 0) ≢0(m o d 𝑝 𝑒)f(x 0)≢0(mod p e)，则方程 (5)(5) 无解，从而不能由式 (3)(3) 构造方程 (4)(4) 的解．

进而我们有推论：

推论 1

对 定理 1 的 𝑝 p，𝑒 e，𝑓(𝑥)f(x)，𝑥 0 x 0，

1. 若 𝑠 s 是方程 𝑓(𝑥) ≡0(m o d 𝑝)f(x)≡0(mod p) 的解，且 𝑓′(𝑠) ≢0(m o d 𝑝)f′(s)≢0(mod p)，则存在 𝑥 𝑠 ∈𝐙 𝑝 𝑒 x s∈Z p e，𝑥 𝑠 ≡𝑠(m o d 𝑝)x s≡s(mod p) 使得 𝑥 𝑠 x s 是方程 (4)(4) 的解．
2. 若方程 𝑓(𝑥) ≡0(m o d 𝑝)f(x)≡0(mod p) 与 𝑓′(𝑥) ≡0(m o d 𝑝)f′(x)≡0(mod p) 无公共解，则方程 (4)(4) 和方程 𝑓(𝑥) ≡0(m o d 𝑝)f(x)≡0(mod p) 的解数相同．

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

## 素数模同余方程

以下令 𝑝 ∈𝐏 p∈P，整系数多项式 𝑓(𝑥) =∑𝑛 𝑖=0 𝑎 𝑖 𝑥 𝑖 f(x)=∑i=0 n a i x i，其中 𝑝 ∤𝑎 𝑛 p∤a n，𝑥 ∈𝐙 𝑝 x∈Z p．

定理 2

若方程

𝑓(𝑥)≡0(m o d 𝑝)(6)(6)f(x)≡0(mod p)

有 𝑘 k 个不同的解 𝑥 1,𝑥 2,…,𝑥 𝑘 (𝑘 ≤𝑛)x 1,x 2,…,x k (k≤n)，则

𝑓(𝑥)≡𝑔(𝑥)𝑘∏𝑖=1(𝑥−𝑥 𝑖)(m o d 𝑝),f(x)≡g(x)∏i=1 k(x−x i)(mod p),

其中 d e g⁡𝑔 =𝑛 −𝑘 deg⁡g=n−k 且 [𝑥 𝑛−𝑘]𝑔(𝑥) =𝑎 𝑛[x n−k]g(x)=a n．

证明

对 𝑘 k 应用数学归纳法．

- 当 𝑘 =1 k=1 时，做多项式带余除法，有 𝑓(𝑥) =(𝑥 −𝑥 1)𝑔(𝑥) +𝑟 f(x)=(x−x 1)g(x)+r，其中 𝑟 ∈𝐙 r∈Z．

  由 𝑓(𝑥 1) ≡0(m o d 𝑝)f(x 1)≡0(mod p) 可知 𝑟 ≡0(m o d 𝑝)r≡0(mod p)，从而 𝑓(𝑥) ≡(𝑥 −𝑥 1)𝑔(𝑥)(m o d 𝑝)f(x)≡(x−x 1)g(x)(mod p)．

- 假设命题对 𝑘 −1 k−1(𝑘 >1 k>1) 时的情况成立，现在设 𝑓(𝑥)f(x) 有 𝑘 k 个不同的解 𝑥 1,𝑥 2,…,𝑥 𝑘 x 1,x 2,…,x k，则 𝑓(𝑥) ≡(𝑥 −𝑥 1)ℎ(𝑥)(m o d 𝑝)f(x)≡(x−x 1)h(x)(mod p)，进而有

  (∀𝑖=2,3,…,𝑘), 0≡𝑓(𝑥 𝑖)≡(𝑥 𝑖−𝑥 1)ℎ(𝑥 𝑖)(m o d 𝑝)(∀i=2,3,…,k), 0≡f(x i)≡(x i−x 1)h(x i)(mod p)

  从而 ℎ(𝑥)h(x) 有 𝑘 −1 k−1 个不同的解 𝑥 2,𝑥 3,…,𝑥 𝑘 x 2,x 3,…,x k，由归纳假设有

  ℎ(𝑥)≡𝑔(𝑥)𝑘∏𝑖=2(𝑥−𝑥 𝑖)(m o d 𝑝)h(x)≡g(x)∏i=2 k(x−x i)(mod p)

  其中 d e g⁡𝑔 =𝑛 −𝑘 deg⁡g=n−k 且 [𝑥 𝑛−𝑘]𝑔(𝑥) =𝑎 𝑛[x n−k]g(x)=a n．

  因此命题得证．

推论 2

对素数 𝑝 p，

- (∀𝑥 ∈𝐙), 𝑥 𝑝−1 −1 ≡∏𝑝−1 𝑖=1(𝑥 −𝑖)(m o d 𝑝)(∀x∈Z), x p−1−1≡∏i=1 p−1(x−i)(mod p)．
- （Wilson 定理）(𝑝 −1)! ≡ −1(m o d 𝑝)(p−1)!≡−1(mod p)．

定理 3（Lagrange 定理）

方程 (6)(6) 至多有 𝑛 n 个不同解．

证明

假设 𝑓(𝑥)f(x) 有 𝑛 +1 n+1 个不同解 𝑥 1,𝑥 2,…,𝑥 𝑛+1 x 1,x 2,…,x n+1，则由 定理 2，对 𝑥 1,𝑥 2,…,𝑥 𝑛 x 1,x 2,…,x n 有

𝑓(𝑥)≡𝑎 𝑛 𝑛∏𝑖=1(𝑥−𝑥 𝑖)(m o d 𝑝)f(x)≡a n∏i=1 n(x−x i)(mod p)

令 𝑥 =𝑥 𝑛+1 x=x n+1，则

0≡𝑓(𝑥 𝑛+1)≡𝑎 𝑛 𝑛∏𝑖=1(𝑥 𝑛+1−𝑥 𝑖)(m o d 𝑝)0≡f(x n+1)≡a n∏i=1 n(x n+1−x i)(mod p)

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

推论 3

若同余方程 ∑𝑛 𝑖=0 𝑏 𝑖 𝑥 𝑖 ≡0(m o d 𝑝)∑i=0 n b i x i≡0(mod p) 的解数大于 𝑛 n，则

(∀𝑖=0,1,…,𝑛), 𝑝∣𝑏 𝑖.(∀i=0,1,…,n), p∣b i.

定理 4

方程 (6)(6) 若解的个数不为 𝑝 p，则必存在满足 d e g⁡𝑟 <𝑝 deg⁡r<p 的整系数多项式 𝑟(𝑥)r(x) 使得 𝑓(𝑥) ≡0(m o d 𝑝)f(x)≡0(mod p) 和 𝑟(𝑥) ≡0(m o d 𝑝)r(x)≡0(mod p) 的解集相同．

证明

不妨设 𝑛 ≥𝑝 n≥p，对 𝑓(𝑥)f(x) 做多项式带余除法

𝑓(𝑥)=𝑔(𝑥)(𝑥 𝑝−𝑥)+𝑟(𝑥)f(x)=g(x)(x p−x)+r(x)

其中 d e g⁡𝑟 <𝑝 deg⁡r<p．

由 Fermat 小定理 知对任意整数 𝑥 x 有 𝑥 𝑝 ≡𝑥(m o d 𝑝)x p≡x(mod p)，从而

- 若 𝑟(𝑥) ≡0(m o d 𝑝)r(x)≡0(mod p)，则由 推论 2 可知 𝑓(𝑥)f(x) 有 𝑝 p 个不同的解．
- 若 𝑟(𝑥) ≢0(m o d 𝑝)r(x)≢0(mod p)，则由 𝑓(𝑥) ≡𝑟(𝑥)(m o d 𝑝)f(x)≡r(x)(mod p) 可知 𝑓(𝑥)f(x) 和 𝑟(𝑥)r(x) 的解集相同．

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

定理 5

设 𝑛 ≤𝑝 n≤p，则方程

𝑥 𝑛+𝑛−1∑𝑖=0 𝑎 𝑖 𝑥 𝑖≡0(m o d 𝑝)(7)(7)x n+∑i=0 n−1 a i x i≡0(mod p)

有 𝑛 n 个解当且仅当存在整系数多项式 𝑞(𝑥)q(x)，𝑟(𝑥) (d e g⁡𝑟 <𝑛)r(x) (deg⁡r<n) 使得

𝑥 𝑝−𝑥=𝑓(𝑥)𝑞(𝑥)+𝑝 𝑟(𝑥).(8)(8)x p−x=f(x)q(x)+p r(x).
证明

- 必要性：由多项式除法知存在整系数多项式 𝑞(𝑥)q(x)，𝑟 1(𝑥) (d e g⁡𝑟 1 <𝑛)r 1(x) (deg⁡r 1<n) 使得

  𝑥 𝑝−𝑥=𝑓(𝑥)𝑞(𝑥)+𝑟 1(𝑥).x p−x=f(x)q(x)+r 1(x).

  若方程 (7)(7) 有 𝑛 n 个解，则 𝑟 1 ≡0(m o d 𝑝)r 1≡0(mod p) 也有 𝑛 n 个相同的解，进而由 推论 3 可知存在整系数多项式 𝑟(𝑥)r(x) 满足 𝑟 1(𝑥) =𝑝 𝑟(𝑥)r 1(x)=p r(x)，从而命题得证．

- 充分性：若式 (8)(8) 成立，则由 Fermat 小定理 可知，对任意整数 𝑥 x,

  0≡𝑥 𝑝−𝑥≡𝑓(𝑥)𝑞(𝑥)(m o d 𝑝).0≡x p−x≡f(x)q(x)(mod p).

  即方程 𝑓(𝑥)𝑞(𝑥) ≡0(m o d 𝑝)f(x)q(x)≡0(mod p) 有 𝑝 p 个解．

  设方程 (7)(7) 的解数为 𝑠 s，则由 Lagrange 定理 可知 𝑠 ≤𝑛 s≤n．

  又由于 d e g⁡𝑞 =𝑝 −𝑛 deg⁡q=p−n，则由 Lagrange 定理 可知 𝑞(𝑥) ≡0(m o d 𝑝)q(x)≡0(mod p) 的解数不超过 𝑝 −𝑛 p−n，而方程 𝑓(𝑥)𝑞(𝑥) ≡0(m o d 𝑝)f(x)q(x)≡0(mod p) 的解集是 𝑓(𝑥) ≡0(m o d 𝑝)f(x)≡0(mod p) 解集和 𝑞(𝑥) ≡0(m o d 𝑝)q(x)≡0(mod p) 解集的并集，故 𝑠 +(𝑝 −𝑛) ≥𝑝 s+(p−n)≥p，有 𝑠 ≥𝑛 s≥n．

  因此 𝑠 =𝑛 s=n．

对于非首一多项式，由于 𝐙 𝑝 Z p 是域，故可以将其化为首一多项式，从而适用该定理．

定理 6

设 𝑛 ∣𝑝 −1 n∣p−1，𝑝 ∤𝑎 p∤a，则方程

𝑥 𝑛≡𝑎(m o d 𝑝)(9)(9)x n≡a(mod p)

有解当且仅当

𝑎 𝑝−1 𝑛≡1(m o d 𝑝).a p−1 n≡1(mod p).

而且，若 (9)(9) 有解，则解数为 𝑛 n．

Note

方程 (9)(9) 解集的具体结构可参见 k 次剩余．

证明

- 必要性：若方程 (9)(9) 有解 𝑥 0 x 0，则

  𝑎 𝑝−1 𝑛≡(𝑥 𝑛 0)𝑝−1 𝑛≡1(m o d 𝑝)a p−1 n≡(x 0 n)p−1 n≡1(mod p)

- 充分性：若 𝑎 𝑝−1 𝑛 ≡1(m o d 𝑝)a p−1 n≡1(mod p)，则

  𝑥 𝑝−𝑥=𝑥(𝑥 𝑝−1−1)=𝑥((𝑥 𝑛)𝑝−1 𝑛−𝑎 𝑝−1 𝑛+𝑎 𝑝−1 𝑛−1)=(𝑥 𝑛−𝑎)𝑃(𝑥)+𝑥(𝑎 𝑝−1 𝑛−1)x p−x=x(x p−1−1)=x((x n)p−1 n−a p−1 n+a p−1 n−1)=(x n−a)P(x)+x(a p−1 n−1)

  其中 𝑃(𝑥)P(x) 是某个整系数多项式，因此由 定理 5 可知方程 (9)(9) 有 𝑛 n 个解．

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

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

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

𝑥 𝑛+𝑛−1∑𝑖=0 𝑎 𝑖 𝑥 𝑖≡0(m o d 𝑝)x n+∑i=0 n−1 a i x i≡0(mod p)

的求法，其中 𝑝 p 是素数，𝑛 <𝑝 n<p．

我们可以通过将 𝑥 x 代换为 𝑥 −𝑎 𝑛−1 𝑛 x−a n−1 n 来消去 𝑥 𝑛−1 x n−1 项，从而我们只需考虑方程

𝑥 𝑛+𝑛−2∑𝑖=0 𝑎 𝑖 𝑥 𝑖≡0(m o d 𝑝)(1 0)(10)x n+∑i=0 n−2 a i x i≡0(mod p)

的求法，其中 𝑝 p 是素数，𝑛 <𝑝 n<p．

- 若 𝑛 =1 n=1，则求法参见 线性同余方程．
- 若 𝑛 =2 n=2，则求法参见 二次剩余．

- 若方程 (1 0)(10) 可化为

  𝑥 𝑛≡𝑎(m o d 𝑝),x n≡a(mod p),

  则求法参见 k 次剩余．

## 参考资料

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

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