中国剩余定理（Chinese Remainder Theorem，简称CRT），又称孙子定理，是中国古代数学中最辉煌的成就之一。它最早见于南北朝时期（公元5世纪左右）的数学著作《孙子算经》卷下第二十六题。原文记载了一个著名的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”
这个问题本质上是一个一元线性同余方程组的求解问题。虽然《孙子算经》给出了具体的解法口诀：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知”，但直到南宋数学家秦九韶在《数书九章》中才系统地提出了“大衍求一术”，完整解决了模数不一定互质的一般情况，这比西方数学家高斯在《算术研究》（1801年）中发表类似理论早了1500多年。
若整数 n 除以正整数 m，所得余数为 r，则称 n 与 m 模 r 同余，记作 n ≡ r (mod m)。中国剩余定理正是基于同余运算的性质。
因为它关注的是除法后的余数（Remainder）。通过已知的余数信息，反推原始的数值。这在信息论和密码学中有着极其重要的地位。
为了更清晰地理解中国剩余定理通解，我们需要将其形式化。假设我们有如下同余方程组：
x ≡ a₁ (mod m₁)x ≡ a₂ (mod m₂)...x ≡ aₖ (mod mₖ)
其中 m₁, m₂, ..., mₖ 是两两互质的正整数（即 gcd(mᵢ, mⱼ) = 1，当 i ≠ j 时）。中国剩余定理保证该方程组在模 M = m₁m₂...mₖ 下有唯一解。
M = m₁ × m₂ × ... × mₖ。i（从1到k），计算 Mᵢ = M / mᵢ。这意味着 Mᵢ 是除了 mᵢ 以外所有模数的乘积。yᵢ，使得 Mᵢ × yᵢ ≡ 1 (mod mᵢ)。yᵢ 称为 Mᵢ 模 mᵢ 的模逆元。由于 Mᵢ 与 mᵢ 互质，根据欧拉定理，模逆元一定存在。通常使用扩展欧几里得算法来求解。x₀ = Σ (aᵢ × Mᵢ × yᵢ)，求和从 i=1 到 k。x = x₀ (mod M)。x = (x₀ mod M + M) mod M。如果模数 mᵢ 不两两互质，则标准的中国剩余定理不再直接适用。此时需要使用扩展中国剩余定理（ExCRT），通过两两合并方程的方式，将方程组化为标准形式后再求解。
让我们通过一个具体的例子来演示中国剩余定理通解的计算过程。
问题：求一个数 x，满足 x ≡ 2 (mod 3)，x ≡ 3 (mod 5)，x ≡ 2 (mod 7)。
模数为 3, 5, 7。它们两两互质。
M = 3 × 5 × 7 = 105
M₁ = 105 / 3 = 35
M₂ = 105 / 5 = 21
M₃ = 105 / 7 = 15
我们需要找到 y₁ 使得 35 × y₁ ≡ 1 (mod 3)。
因为 35 ≡ 2 (mod 3)，即 2y₁ ≡ 1 (mod 3)，解得 y₁ = 2（因为 2×2=4≡1）。
同理，21 × y₂ ≡ 1 (mod 5) → 1 × y₂ ≡ 1 → y₂ = 1。
同理，15 × y₃ ≡ 1 (mod 7) → 1 × y₃ ≡ 1 → y₃ = 1。
x₀ = (a₁M₁y₁ + a₂M₂y₂ + a₃M₃y₃)
x₀ = (2×35×2 + 3×21×1 + 2×15×1)
x₀ = (140 + 63 + 30) = 233
最终解：x = 233 mod 105 = 23。
验证：23除以3余2，除以5余3，除以7余2。正确！
若方程组为 x ≡ 2 (mod 4)，x ≡ 3 (mod 6)。这里 gcd(4,6)=2≠1，不能直接用标准CRT。
解法：
1. 展开为不定方程：x = 4k + 2，x = 6j + 3。
2. 联立：4k + 2 = 6j + 3 → 4k - 6j = 1。
3. 观察左边 4k-6j 必为偶数，右边为奇数 1，无整数解。故该方程组无解。
注：若方程组有解，则可通过合并模数为 lcm(m1, m2) 的方式逐步化简。
在计算机科学中，中国剩余定理常用于大数运算加速。以下是使用 Python 实现的中国剩余定理通解算法，包含扩展欧几里得算法求解模逆元。
def extended_gcd(a, b):
"""扩展欧几里得算法，返回 (gcd, x, y) 使得 ax + by = gcd"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) x1
y = x1
return gcd, x, y
def inverse(a, m):
"""求 a 模 m 的逆元"""
gcd, x, _ = extended_gcd(a % m, m)
if gcd != 1:
raise ValueError("Modular inverse does not exist")
return (x % m + m) % m
def chinese_remainder_theorem(remainders, moduli):
"""
中国剩余定理求解
:param remainders: 余数列表 [a1, a2, ..., ak]
:param moduli: 模数列表 [m1, m2, ..., mk]，需两两互质
:return: 最小非负整数解 x
"""
# 1. 计算总模数 M
M = 1
for m in moduli:
M = m
# 2. 计算解
x = 0
for i in range(len(moduli)):
ai = remainders[i]
mi = moduli[i]
# Mi = M / mi
Mi = M // mi
# yi = Mi^(-1) mod mi
yi = inverse(Mi, mi)
# 累加
x += ai Mi yi
# 3. 取模得到最小非负解
return x % M
测试示例
remainders = [2, 3, 2]
moduli = [3, 5, 7]
result = chinese_remainder_theorem(remainders, moduli)
print(f"解为: {result}") # 输出: 23
| 步骤 | 操作 | 时间复杂度 |
|---|---|---|
| 计算 M | k 次乘法 | O(k log M) |
| 计算 Mi | k 次除法 | O(k log M) |
| 计算逆元 yi | 扩展欧几里得算法 | O(k log² mᵢ) |
| 求和 x | k 次大数乘法与加法 | O(k log² M) |
| 总计 | - | O(k log² M) |
中国剩余定理不仅仅是数论中的一个优美定理，它在现代科技中有着广泛的应用。
在 RSA 算法中，私钥解密涉及大数模幂运算 c^d mod n。如果 n = p × q，利用中国剩余定理，可以将计算分解为：
m₁ = c^(d mod (p-1)) mod pm₂ = c^(d mod (q-1)) mod q
最后通过 CRT 合并 m₁ 和 m₂ 得到 m。由于 p 和 q 约为 n 的平方根，这种分解可以将运算速度提高约 4 倍。
在云存储和 RAID 阵列中，中国剩余定理被用于数据分片和恢复。通过将数据编码为多项式系数，并在不同节点存储多项式的值，即使部分节点丢失，也能通过 CRT 或插值法恢复原始数据。
在处理超大整数乘法时，可以将大整数映射到一组小模数域中分别计算，最后用 CRT 合并结果。这种方法避免了大数除法的复杂性，提高了并行计算效率。
虽然中国剩余定理看似高深，但其思想渗透在日常生活中。例如：
中国剩余定理的通解公式为 x = (Σ(ai Mi yi)) mod M。其中 M 是所有模数 mi 的乘积，Mi = M / mi，yi 是 Mi 关于模 mi 的模逆元。
是的，标准的中国剩余定理要求模数两两互质。如果模数不互质，则需要使用扩展中国剩余定理（ExCRT），通过合并方程来求解。具体来说，若 gcd(m1, m2) = d，则需检查 a1 ≡ a2 (mod d) 是否成立，若成立则可合并。
在RSA算法中，中国剩余定理被用于加速解密和签名过程（CRT-RSA）。它将大数模幂运算分解为两个较小规模的运算，显著提高了计算效率。此外，它也被用于 Shamir 秘密共享方案中。
计算模逆元通常使用扩展欧几里得算法。例如，求 3 模 7 的逆元，即解 3x + 7y = 1。通过辗转相除：
7 = 2×3 + 1
1 = 7 - 2×3
所以 -2×3 ≡ 1 (mod 7)，即 x = -2 ≡ 5 (mod 7)。故 3 模 7 的逆元是 5。
在模 M = m1m2...mk 的意义下，解是唯一的。也就是说，所有解构成一个同余类 x ≡ x0 (mod M)。如果在整数范围内，则有无穷多解，形式为 x0 + kM（k 为整数）。
中国剩余定理不仅是中国古代数学智慧的结晶，也是现代计算机科学和数论的重要基石。从《孙子算经》中的“物不知数”到如今的 RSA 加密算法，这一理论跨越千年，依然焕发着强大的生命力。掌握中国剩余定理通解的方法，不仅能帮助我们解决复杂的同余方程问题，更能深入理解现代信息安全的底层逻辑。
希望本文能为您提供清晰的解题思路和丰富的背景知识。如果您对其他数论问题感兴趣，欢迎继续探索我们的其他内容。