同余方程

同余方程定义同余方程 对正整数 𝑚m 和一元整系数多项式 𝑓(𝑥) =∑𝑛𝑖=0𝑎𝑖𝑥𝑖f(x)=∑i=0naixi，其中未知数 𝑥 ∈𝐙𝑚x∈Zm，称形如

𝑓(𝑥)≡0(mod𝑚)(1)(1)f(x)≡0(modm) 的方程为关于未知数 𝑥x 的模 𝑚m 的一元 同余方程（Congruence Equation）．

若 𝑎𝑛 ≢0(mod𝑚)an≢0(modm)，则称上式为 𝑛n 次同余方程．

类似可定义同余方程组．

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

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

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

素数幂模同余方程以下假设模数 𝑚 =𝑝𝑒 (𝑝 ∈𝐏, 𝑒 ∈𝐙>1)m=pe (p∈P, e∈Z>1)．

注意到，若 𝑥0x0 是方程

𝑓(𝑥)≡0(mod𝑝𝑒)f(x)≡0(modpe)的解，则 𝑥0x0 是方程

𝑓(𝑥)≡0(mod𝑝𝑒−1)f(x)≡0(modpe−1)的解．这启发我们尝试通过较低的模幂次的解去构造较高的模幂次的解．我们有如下定理：

定理 1（Hensel 引理） 对素数 𝑝p 和整数 𝑒 >1e>1，取整系数多项式 𝑓(𝑥) =∑𝑛𝑖=0𝑎𝑖𝑥𝑖 (𝑝𝑒 ∤𝑎𝑛)f(x)=∑i=0naixi (pe∤an)，令 𝑓′(𝑥) =∑𝑛𝑖=1𝑖𝑎𝑖𝑥𝑖−1f′(x)=∑i=1niaixi−1 为其导数．令 𝑥0x0 为方程

𝑓(𝑥)≡0(mod𝑝𝑒−1)(2)(2)f(x)≡0(modpe−1) 的解，则：

若 𝑓′(𝑥0) ≢0(mod𝑝)f′(x0)≢0(modp)，则存在整数 𝑡t 使得

𝑥=𝑥0+𝑝𝑒−1𝑡(3)(3)x=x0+pe−1t 是方程

𝑓(𝑥)≡0(mod𝑝𝑒)(4)(4)f(x)≡0(modpe) 的解．

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

若 𝑓′(𝑥0) ≡0(mod𝑝)f′(x0)≡0(modp) 且 𝑓(𝑥0) ≢0(mod𝑝𝑒)f(x0)≢0(modpe)，则不能由式 (3)(3) 构造方程 (4)(4) 的解．证明 我们假设式 (3)(3) 是方程 (4)(4) 的解，即

𝑓(𝑥0+𝑝𝑒−1𝑡)≡0(mod𝑝𝑒)f(x0+pe−1t)≡0(modpe) 整理后可得

𝑓(𝑥0)+𝑝𝑒−1𝑡𝑓′(𝑥0)≡0(mod𝑝𝑒)f(x0)+pe−1tf′(x0)≡0(modpe) 于是

𝑡𝑓′(𝑥0)≡−𝑓(𝑥0)𝑝𝑒−1(mod𝑝)(5)(5)tf′(x0)≡−f(x0)pe−1(modp) 若 𝑓′(𝑥0) ≢0(mod𝑝)f′(x0)≢0(modp)，则关于 𝑡t 的方程 (5)(5) 有唯一解 𝑡0t0，代入式 (3)(3) 可验证其为方程 (4)(4) 的解．若 𝑓′(𝑥0) ≡0(mod𝑝)f′(x0)≡0(modp) 且 𝑓(𝑥0) ≡0(mod𝑝𝑒)f(x0)≡0(modpe)，则任意 𝑡t 均能使方程 (5)(5) 成立，代入式 (3)(3) 可验证其均为方程 (4)(4) 的解．若 𝑓′(𝑥0) ≡0(mod𝑝)f′(x0)≡0(modp) 且 𝑓(𝑥0) ≢0(mod𝑝𝑒)f(x0)≢0(modpe)，则方程 (5)(5) 无解，从而不能由式 (3)(3) 构造方程 (4)(4) 的解．进而我们有推论：

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

若 𝑠s 是方程 𝑓(𝑥) ≡0(mod𝑝)f(x)≡0(modp) 的解，且 𝑓′(𝑠) ≢0(mod𝑝)f′(s)≢0(modp)，则存在 𝑥𝑠 ∈𝐙𝑝𝑒xs∈Zpe，𝑥𝑠 ≡𝑠(mod𝑝)xs≡s(modp) 使得 𝑥𝑠xs 是方程 (4)(4) 的解．若方程 𝑓(𝑥) ≡0(mod𝑝)f(x)≡0(modp) 与 𝑓′(𝑥) ≡0(mod𝑝)f′(x)≡0(modp) 无公共解，则方程 (4)(4) 和方程 𝑓(𝑥) ≡0(mod𝑝)f(x)≡0(modp) 的解数相同．从而我们可以将素数幂模同余方程化归到素数模同余方程的情况．

素数模同余方程以下令 𝑝 ∈𝐏p∈P，整系数多项式 𝑓(𝑥) =∑𝑛𝑖=0𝑎𝑖𝑥𝑖f(x)=∑i=0naixi，其中 𝑝 ∤𝑎𝑛p∤an，𝑥 ∈𝐙𝑝x∈Zp．

定理 2 若方程

𝑓(𝑥)≡0(mod𝑝)(6)(6)f(x)≡0(modp) 有 𝑘k 个不同的解 𝑥1,𝑥2,…,𝑥𝑘 (𝑘 ≤𝑛)x1,x2,…,xk (k≤n)，则

𝑓(𝑥)≡𝑔(𝑥)𝑘∏𝑖=1(𝑥−𝑥𝑖)(mod𝑝),f(x)≡g(x)∏i=1k(x−xi)(modp), 其中 deg⁡𝑔 =𝑛 −𝑘deg⁡g=n−k 且 [𝑥𝑛−𝑘]𝑔(𝑥) =𝑎𝑛[xn−k]g(x)=an．

证明 对 𝑘k 应用数学归纳法．

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

由 𝑓(𝑥1) ≡0(mod𝑝)f(x1)≡0(modp) 可知 𝑟 ≡0(mod𝑝)r≡0(modp)，从而 𝑓(𝑥) ≡(𝑥 −𝑥1)𝑔(𝑥)(mod𝑝)f(x)≡(x−x1)g(x)(modp)．

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

(∀𝑖=2,3,…,𝑘), 0≡𝑓(𝑥𝑖)≡(𝑥𝑖−𝑥1)ℎ(𝑥𝑖)(mod𝑝)(∀i=2,3,…,k), 0≡f(xi)≡(xi−x1)h(xi)(modp) 从而 ℎ(𝑥)h(x) 有 𝑘 −1k−1 个不同的解 𝑥2,𝑥3,…,𝑥𝑘x2,x3,…,xk，由归纳假设有

ℎ(𝑥)≡𝑔(𝑥)𝑘∏𝑖=2(𝑥−𝑥𝑖)(mod𝑝)h(x)≡g(x)∏i=2k(x−xi)(modp) 其中 deg⁡𝑔 =𝑛 −𝑘deg⁡g=n−k 且 [𝑥𝑛−𝑘]𝑔(𝑥) =𝑎𝑛[xn−k]g(x)=an．

因此命题得证．

推论 2 对素数 𝑝p，

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

定理 3（Lagrange 定理） 方程 (6)(6) 至多有 𝑛n 个不同解．

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

𝑓(𝑥)≡𝑎𝑛𝑛∏𝑖=1(𝑥−𝑥𝑖)(mod𝑝)f(x)≡an∏i=1n(x−xi)(modp) 令 𝑥 =𝑥𝑛+1x=xn+1，则

0≡𝑓(𝑥𝑛+1)≡𝑎𝑛𝑛∏𝑖=1(𝑥𝑛+1−𝑥𝑖)(mod𝑝)0≡f(xn+1)≡an∏i=1n(xn+1−xi)(modp) 而右侧显然不是 𝑝p 的倍数，因此假设矛盾．

推论 3 若同余方程 ∑𝑛𝑖=0𝑏𝑖𝑥𝑖 ≡0(mod𝑝)∑i=0nbixi≡0(modp) 的解数大于 𝑛n，则

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

定理 4 方程 (6)(6) 若解的个数不为 𝑝p，则必存在满足 deg⁡𝑟 <𝑝deg⁡r

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

𝑓(𝑥)=𝑔(𝑥)(𝑥𝑝−𝑥)+𝑟(𝑥)f(x)=g(x)(xp−x)+r(x) 其中 deg⁡𝑟 <𝑝deg⁡r

由 Fermat 小定理 知对任意整数 𝑥x 有 𝑥𝑝 ≡𝑥(mod𝑝)xp≡x(modp)，从而

若 𝑟(𝑥) ≡0(mod𝑝)r(x)≡0(modp)，则由 推论 2 可知 𝑓(𝑥)f(x) 有 𝑝p 个不同的解．若 𝑟(𝑥) ≢0(mod𝑝)r(x)≢0(modp)，则由 𝑓(𝑥) ≡𝑟(𝑥)(mod𝑝)f(x)≡r(x)(modp) 可知 𝑓(𝑥)f(x) 和 𝑟(𝑥)r(x) 的解集相同．我们可以通过这个定理对同余方程降次．

定理 5 设 𝑛 ≤𝑝n≤p，则方程

𝑥𝑛+𝑛−1∑𝑖=0𝑎𝑖𝑥𝑖≡0(mod𝑝)(7)(7)xn+∑i=0n−1aixi≡0(modp) 有 𝑛n 个解当且仅当存在整系数多项式 𝑞(𝑥)q(x)，𝑟(𝑥) (deg⁡𝑟 <𝑛)r(x) (deg⁡r

𝑥𝑝−𝑥=𝑓(𝑥)𝑞(𝑥)+𝑝𝑟(𝑥).(8)(8)xp−x=f(x)q(x)+pr(x).证明 必要性：由多项式除法知存在整系数多项式 𝑞(𝑥)q(x)，𝑟1(𝑥) (deg⁡𝑟1 <𝑛)r1(x) (deg⁡r1

𝑥𝑝−𝑥=𝑓(𝑥)𝑞(𝑥)+𝑟1(𝑥).xp−x=f(x)q(x)+r1(x). 若方程 (7)(7) 有 𝑛n 个解，则 𝑟1 ≡0(mod𝑝)r1≡0(modp) 也有 𝑛n 个相同的解，进而由 推论 3 可知存在整系数多项式 𝑟(𝑥)r(x) 满足 𝑟1(𝑥) =𝑝𝑟(𝑥)r1(x)=pr(x)，从而命题得证．

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

0≡𝑥𝑝−𝑥≡𝑓(𝑥)𝑞(𝑥)(mod𝑝).0≡xp−x≡f(x)q(x)(modp). 即方程 𝑓(𝑥)𝑞(𝑥) ≡0(mod𝑝)f(x)q(x)≡0(modp) 有 𝑝p 个解．

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

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

因此 𝑠 =𝑛s=n．

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

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

𝑥𝑛≡𝑎(mod𝑝)(9)(9)xn≡a(modp) 有解当且仅当

𝑎𝑝−1𝑛≡1(mod𝑝).ap−1n≡1(modp). 而且，若 (9)(9) 有解，则解数为 𝑛n．

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

证明 必要性：若方程 (9)(9) 有解 𝑥0x0，则

𝑎𝑝−1𝑛≡(𝑥𝑛0)𝑝−1𝑛≡1(mod𝑝)ap−1n≡(x0n)p−1n≡1(modp)充分性：若 𝑎𝑝−1𝑛 ≡1(mod𝑝)ap−1n≡1(modp)，则

𝑥𝑝−𝑥=𝑥(𝑥𝑝−1−1)=𝑥((𝑥𝑛)𝑝−1𝑛−𝑎𝑝−1𝑛+𝑎𝑝−1𝑛−1)=(𝑥𝑛−𝑎)𝑃(𝑥)+𝑥(𝑎𝑝−1𝑛−1)xp−x=x(xp−1−1)=x((xn)p−1n−ap−1n+ap−1n−1)=(xn−a)P(x)+x(ap−1n−1) 其中 𝑃(𝑥)P(x) 是某个整系数多项式，因此由 定理 5 可知方程 (9)(9) 有 𝑛n 个解．

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

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

𝑥𝑛+𝑛−1∑𝑖=0𝑎𝑖𝑥𝑖≡0(mod𝑝)xn+∑i=0n−1aixi≡0(modp)的求法，其中 𝑝p 是素数，𝑛 <𝑝n

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

𝑥𝑛+𝑛−2∑𝑖=0𝑎𝑖𝑥𝑖≡0(mod𝑝)(10)(10)xn+∑i=0n−2aixi≡0(modp)的求法，其中 𝑝p 是素数，𝑛 <𝑝n

若 𝑛 =1n=1，则求法参见 线性同余方程．若 𝑛 =2n=2，则求法参见 二次剩余．若方程 (10)(10) 可化为

𝑥𝑛≡𝑎(mod𝑝),xn≡a(modp), 则求法参见 k 次剩余．

参考资料Congruence Equation -- from Wolfram MathWorldLagrange's theorem (number theory) - Wikipedia潘承洞，潘承彪．初等数论．冯克勤．初等数论及其应用．闵嗣鹤，严士健．初等数论．本页面最近更新：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 协议之条款下提供，附加条款亦可能应用