同余方程计算器

同余方程计算器:输入 2–5 个 x ≡ rᵢ (mod mᵢ),用中国剩余定理(孙子定理)求最小非负解和通解,模不互质时逐个合并并判断是否无解;还能求模逆元、解线性同余方程 a·x ≡ b (mod m),全程大整数精确计算并给出步骤。

第 1 个方程:x ≡ r₁ (mod m₁)
第 2 个方程:x ≡ r₂ (mod m₂)

余数可以是负数或大于模,会先化到 [0, m) 再计算;所有整数最多 18 位。

最小非负解 x₀
8
模 M(各模的最小公倍数)M = 15
模的关系两两互质

通解:x = 8 + 15·k(k 为整数)

中国剩余定理构造表(Mᵢ = M / mᵢ,tᵢ = Mᵢ⁻¹ mod mᵢ)
方程rᵢmᵢMᵢtᵢrᵢ·Mᵢ·tᵢ
第 1 个235220
第 2 个353218

求和 38,38 mod 15 = 8。

怎么用

  1. 选择计算类型:在顶部切换「同余方程组」「模逆元」「线性同余方程」三种模式,各模式的输入互不影响,切回来时原来填的数还在。
  2. 把题目写成同余式再填数:同余方程组按 x ≡ rᵢ (mod mᵢ) 逐个填余数 rᵢ 和模 mᵢ,默认 2 个方程,点「添加方程」最多到 5 个。例如「三三数之剩二」就填 r₁ = 2、m₁ = 3。余数可以是负数或大于模,工具会先化到 [0, m)。
  3. 读取最小非负解与通解:方程组有解时给出最小非负解 x₀、模 M(各模的最小公倍数)和通解 x = x₀ + M·k;模两两互质时附中国剩余定理构造表,否则附逐个合并步骤;无解时指出是第几个方程产生矛盾。
  4. 求逆元或解 ax ≡ b (mod m):模逆元模式填 a 和 m,给出 a⁻¹ mod m、扩展欧几里得表和校验行;线性同余模式填 a、b、m,给出 g = gcd(a, m)、解的个数、通解和 [0, m) 内的全部解(超过 20 个只列前 20 个)。

核心要点

同余方程组 x ≡ rᵢ (mod mᵢ) 的解是模 M = lcm(mᵢ) 的一个余数类;模两两互质时用中国剩余定理构造,否则逐个合并,合并中出现 gcd 不整除就无解。

  • 物不知数:x≡2(mod 3)、x≡3(mod 5)、x≡2(mod 7) 的最小解是 23,通解 23 + 105k。
  • 模不互质:x≡2(mod 4)、x≡4(mod 6) 合并得 x ≡ 10 (mod 12);x≡1(mod 4)、x≡2(mod 6) 无解。
  • 模逆元:17⁻¹ mod 43 = 38,仅当 gcd(a, m) = 1 时存在。
  • 线性同余:6x≡4 (mod 10) 有 g = 2 个解:4 和 9。
  • 易漏特例:a 是 m 的倍数时 m/g = 1,不用求逆元——b 也是 m 的倍数则模 m 下每个数都是解(如 0·x≡0 (mod 7) 有 0–6 共 7 个解),否则无解。

原理与公式

同余:若 m 整除 a − b,就记作 a ≡ b (mod m),即 a、b 除以 m 的余数相同。中国剩余定理(又称孙子定理)说:模 m₁, m₂, …, mₖ 两两互质时,同余方程组 x ≡ rᵢ (mod mᵢ) 在模 M = m₁m₂…mₖ 下有且只有一个解。

两两互质:构造公式

令 Mᵢ = M / mᵢ,tᵢ = Mᵢ⁻¹ mod mᵢ(Mᵢ 在模 mᵢ 下的逆元),则

x₀ = (r₁M₁t₁ + r₂M₂t₂ + … + rₖMₖtₖ) mod M

以「物不知数」x≡2(mod 3)、x≡3(mod 5)、x≡2(mod 7) 为例,M = 105:

方程rᵢmᵢMᵢ = 105/mᵢtᵢ = Mᵢ⁻¹ mod mᵢrᵢ·Mᵢ·tᵢ
第 1 个23352(35×2 = 70 ≡ 1)140
第 2 个35211(21 ≡ 1)63
第 3 个27151(15 ≡ 1)30

求和 140 + 63 + 30 = 233,233 mod 105 = 23,通解 x = 23 + 105k。

模不互质:逐个合并

从 x ≡ A (mod M)(初值取第 1 个方程)开始,并入 x ≡ r (mod m):

  1. 算 g = gcd(M, m)、d = r − A;g 不整除 d 则方程组无解。
  2. 否则 t = (d/g) · (M/g)⁻¹ mod (m/g)(m/g = 1 时 t = 0)。
  3. 更新 A ← A + M·t,M ← lcm(M, m),再把 A 化到 [0, M)。

例:x≡2(mod 4)、x≡4(mod 6)。g = 2,d = 2 可整除;(4/2)⁻¹ mod 3 = 2⁻¹ mod 3 = 2,t = 1×2 mod 3 = 2,A = 2 + 4×2 = 10,M = 12,解为 x ≡ 10 (mod 12)。 这个方法对互质的模同样适用,本工具用它作为主算法,互质时再用构造公式交叉核对。

模逆元:扩展欧几里得算法

对 m 和 a 辗转相除直到余数为 1,再倒推写成 a·s + m·t = 1,逆元 a⁻¹ ≡ s (mod m)。以 17⁻¹ mod 43 为例:

辗转相除商余数
43 = 2 × 17 + 929
17 = 1 × 9 + 818
9 = 1 × 8 + 111

回代:1 = 9 − 8 = 9 − (17 − 9) = 2×9 − 17 = 2×(43 − 2×17) − 17 = 2×43 − 5×17,所以 s = −5, 逆元 = −5 mod 43 = 38;校验 17×38 = 646 = 15×43 + 1。

线性同余方程 a·x ≡ b (mod m)

令 g = gcd(a, m):g 不整除 b 时无解;否则模 m 下恰有 g 个解 x₀ + k·m/g(k = 0, 1, …, g−1),其中 x₀ = (b/g)·(a/g)⁻¹ mod (m/g)。例:6x≡4 (mod 10) → 3x≡2 (mod 5) → x₀ = 2×2 mod 5 = 4,解为 4、9。

怎么把应用题列成同余式

「一筐鸡蛋,3 个 3 个数剩 2 个,5 个 5 个数剩 3 个,7 个 7 个数剩 2 个」——每句「k 个 k 个数剩 r 个」就是一个 x ≡ r (mod k);「刚好数完」就是余数 0。

精度:全程用整数(BigInt)运算,没有任何舍入;每个整数最多 18 位,5 个 18 位模的最小公倍数可达 90 位,也会完整显示。

常见问题

中国剩余定理怎么算?“物不知数”的答案 23 是怎么来的?
《孙子算经》里的题目是:一个数除以 3 余 2、除以 5 余 3、除以 7 余 2,求这个数,写成同余方程组就是 x≡2(mod 3)、x≡3(mod 5)、x≡2(mod 7)。三个模两两互质,先算 M = 3×5×7 = 105,再对每个方程算 Mᵢ = M/mᵢ(35、21、15)和它在 mᵢ 下的逆元 tᵢ(2、1、1),最后求和 2×35×2 + 3×21×1 + 2×15×1 = 233,233 mod 105 = 23。所以最小正整数解是 23,全部解为 23 + 105k。
模不互质的同余方程组怎么解?什么情况下无解?
模不互质时不能直接套中国剩余定理的构造公式,要两个两个合并:设当前已得 x ≡ A (mod M),并入 x ≡ r (mod m) 时先算 g = gcd(M, m)。只有 g 整除 r − A 才有解,这时解出一个 t,得到新的 x ≡ A + M·t (mod lcm(M, m));g 不整除 r − A 就无解。例如 x≡2(mod 4)、x≡4(mod 6):g = 2 整除 2,合并得 x ≡ 10 (mod 12);而 x≡1(mod 4)、x≡2(mod 6) 中 g = 2 不整除 1,无解。同一个模配不同余数(如 x≡1、x≡2 (mod 5))也一定无解。这种两两合并的做法在算法竞赛里常叫扩展中国剩余定理(EXCRT),它对模互质的情况同样适用。
模逆元怎么求?什么情况下不存在逆元?
a 在模 m 下的逆元是满足 a·y ≡ 1 (mod m) 的 y,常用扩展欧几里得算法求:对 m 和 a 辗转相除,再把余数 1 倒推回去写成 a·s + m·t = 1,s mod m 就是逆元。以 17⁻¹ mod 43 为例:43 = 2×17 + 9,17 = 1×9 + 8,9 = 1×8 + 1,回代得 1 = 2×43 − 5×17,所以逆元是 −5 mod 43 = 38,验算 17×38 = 646 = 15×43 + 1。逆元只在 gcd(a, m) = 1 时存在,例如 6 在模 9 下没有逆元(gcd = 3)。m 是质数时也可以用费马小定理 a^(m−2) mod m 求。
线性同余方程 ax≡b (mod m) 怎么解,有几个解?
先算 g = gcd(a, m)。g 不整除 b 时无解;g 整除 b 时,在 0 到 m−1 范围内恰好有 g 个解,它们相差 m/g。做法是两边同除以 g 得到 (a/g)·x ≡ b/g (mod m/g),再乘以 a/g 的逆元求出 x₀。例如 6x≡4 (mod 10):g = 2 整除 4,化为 3x≡2 (mod 5),3 的逆元是 2,x₀ = 4,所以模 10 下有 2 个解 4 和 9,通解写作 x ≡ 4 (mod 5)。a 和 m 互质时 g = 1,解唯一,就是 b 乘以 a 的逆元。
同余方程组的通解为什么是 x₀ + M·k?M 怎么取?
如果 x₀ 满足每个 x ≡ rᵢ (mod mᵢ),那么再加上所有模的公倍数仍然满足,而能同时被每个 mᵢ 整除的最小正数就是它们的最小公倍数,所以 M 取 lcm(m₁, …, mₖ),通解是 x = x₀ + M·k(k 为任意整数),解在模 M 下唯一。模两两互质时最小公倍数正好等于乘积,例如物不知数的 M = 105;模不互质时 M 比乘积小,例如 x≡2(mod 4)、x≡4(mod 6) 的 M 是 12 而不是 24。
余数应用题怎么列同余方程组?在 100 到 200 之间的数怎么找?
把每句「除以 k 余 r」或「k 个 k 个数剩 r 个」写成 x ≡ r (mod k),先求出通解 x₀ + M·k,再把 k 取 0、1、2… 逐个代入,落在指定范围里的就是答案。例如一个数除以 4 余 1、除以 5 余 2、除以 6 余 3,求 100 到 200 之间的这个数:模 4 和 6 不互质,合并后得 x ≡ 57 (mod 60),通解 57 + 60k,范围内是 117 和 177 两个数。这道题还有个巧算:每个余数都比除数小 3,所以 x + 3 是 4、5、6 的公倍数,即 x = 60k − 3,结果相同。
线性同余方程 ax≡b (mod m) 中 a 是 m 的倍数时怎么解?
a 是 m 的倍数时,a·x 除以 m 永远余 0,此时 g = gcd(a, m) = m、m/g = 1,约化后的方程没有可求的逆元,不能套 x₀ = (b/g)·(a/g)⁻¹ 的公式,要直接看 b:b 也是 m 的倍数时,0 到 m−1 的每个整数都是解,共 m 个,可取 x₀ = 0;b 不是 m 的倍数时无解。例如 0·x ≡ 0 (mod 7) 的解是 0、1、2、…、6 共 7 个,18x ≡ 9 (mod 9) 的解是 0 到 8 共 9 个,而 12x ≡ 5 (mod 12) 无解。本工具在解超过 20 个时只列出前 20 个。

来源与更新

本工具依据初等数论的通用定义与算法(整理日期 2026-11-11):

  • 《孙子算经》卷下「物不知数」题——中国剩余定理(孙子定理)的出处。
  • 潘承洞、潘承彪《初等数论》(北京大学出版社)同余式、一次同余方程与中国剩余定理章节。
  • 人教 A 版高中数学选修「初等数论初步」同余与一次同余方程组内容。
  • Wolfram MathWorld Chinese Remainder Theorem 与 Modular Inverse。

本工具为纯数学计算,不含税率、利率等会随政策变化的参数。内容经本站编辑整理与核对,仅供学习与参考。

最近更新:2026-11-11

本工具按初等数论的通用定义做整数同余计算,结果为精确整数值,供学习、竞赛练习与编程参考。