一般性求解步骤
假设我们有如下同余方程组：
- x ≡ a₁ (mod m₁)
- x ≡ a₂ (mod m₂)
- ...
- x ≡ aₙ (mod mₙ)
其中 m₁, m₂, ..., mₙ 两两互质。
步骤1： 计算总模数 M = m₁ × m₂ × ... × mₙ。
步骤2： 对于每个 i，计算 Mᵢ = M / mᵢ。
步骤3： 找到 eᵢ，使得 Mᵢ × eᵢ ≡ 1 (mod mᵢ)。eᵢ 称为 Mᵢ 模 mᵢ 的逆元。
步骤4： 计算解 x = (a₁M₁e₁ + a₂M₂e₂ + ... + aₙMₙeₙ) mod M。
实例演示：韩信点兵
假设问题为：x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)。
1. M = 3 × 5 × 7 = 105。
2. M₁ = 105/3 = 35, M₂ = 105/5 = 21, M₃ = 105/7 = 15。
3. 求逆元：
- 35 × e₁ ≡ 1 (mod 3) → 2 × e₁ ≡ 1 (mod 3) → e₁ = 2
- 21 × e₂ ≡ 1 (mod 5) → 1 × e₂ ≡ 1 (mod 5) → e₂ = 1
- 15 × e₃ ≡ 1 (mod 7) → 1 × e₃ ≡ 1 (mod 7) → e₃ = 1
4. 计算结果：
x = (2×35×2 + 3×21×1 + 2×15×1) mod 105
x = (140 + 63 + 30) mod 105 = 233 mod 105 = 23。
Python 代码示例
def chinese_remainder_theorem(pairs):
"""
pairs: 一个列表，包含 (余数, 模数) 的元组
例如: [(2, 3), (3, 5), (2, 7)]
"""
import functools
def gcd_extended(a, b):
if a == 0:
return b, 0, 1
gcd, x1, y1 = gcd_extended(b % a, a)
x = y1 - (b // a) x1
y = x1
return gcd, x, y
def inverse(a, m):
g, x, _ = gcd_extended(a % m, m)
if g != 1:
raise Exception('Modular inverse does not exist')
return (x % m + m) % m
modulus = functools.reduce(lambda a, b: a b, [p[1] for p in pairs])
result = 0
for remainder, mod in pairs:
Mi = modulus // mod
ei = inverse(Mi, mod)
result += remainder Mi ei
return result % modulus
测试
print(chinese_remainder_theorem([(2, 3), (3, 5), (2, 7)]))
输出: 23