同余方程计算器
同余方程计算器:输入 2–5 个 x ≡ rᵢ (mod mᵢ),用中国剩余定理(孙子定理)求最小非负解和通解,模不互质时逐个合并并判断是否无解;还能求模逆元、解线性同余方程 a·x ≡ b (mod m),全程大整数精确计算并给出步骤。
余数可以是负数或大于模,会先化到 [0, m) 再计算;所有整数最多 18 位。
通解:x = 8 + 15·k(k 为整数)
| 方程 | rᵢ | mᵢ | Mᵢ | tᵢ | rᵢ·Mᵢ·tᵢ |
|---|---|---|---|---|---|
| 第 1 个 | 2 | 3 | 5 | 2 | 20 |
| 第 2 个 | 3 | 5 | 3 | 2 | 18 |
求和 38,38 mod 15 = 8。
怎么用
- 选择计算类型:在顶部切换「同余方程组」「模逆元」「线性同余方程」三种模式,各模式的输入互不影响,切回来时原来填的数还在。
- 把题目写成同余式再填数:同余方程组按 x ≡ rᵢ (mod mᵢ) 逐个填余数 rᵢ 和模 mᵢ,默认 2 个方程,点「添加方程」最多到 5 个。例如「三三数之剩二」就填 r₁ = 2、m₁ = 3。余数可以是负数或大于模,工具会先化到 [0, m)。
- 读取最小非负解与通解:方程组有解时给出最小非负解 x₀、模 M(各模的最小公倍数)和通解 x = x₀ + M·k;模两两互质时附中国剩余定理构造表,否则附逐个合并步骤;无解时指出是第几个方程产生矛盾。
- 求逆元或解 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 个 | 2 | 3 | 35 | 2(35×2 = 70 ≡ 1) | 140 |
| 第 2 个 | 3 | 5 | 21 | 1(21 ≡ 1) | 63 |
| 第 3 个 | 2 | 7 | 15 | 1(15 ≡ 1) | 30 |
求和 140 + 63 + 30 = 233,233 mod 105 = 23,通解 x = 23 + 105k。
模不互质:逐个合并
从 x ≡ A (mod M)(初值取第 1 个方程)开始,并入 x ≡ r (mod m):
- 算
g = gcd(M, m)、d = r − A;g 不整除 d 则方程组无解。 - 否则
t = (d/g) · (M/g)⁻¹ mod (m/g)(m/g = 1 时 t = 0)。 - 更新
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 + 9 | 2 | 9 |
| 17 = 1 × 9 + 8 | 1 | 8 |
| 9 = 1 × 8 + 1 | 1 | 1 |
回代: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 个。