从《孙子算经》的“物不知数”到现代密码学的基石，全方位解读中国剩余定理（Chinese Remainder Theorem）的数学魅力与应用价值。
中国剩余定理，又称孙子定理，是数论中的一个重要定理。它主要解决了一类特殊的同余方程组问题：给定一组两两互质的正整数（模数），以及它们对应的余数，如何求出一个最小的正整数，使得该数除以这些模数的余数分别等于给定的余数。
这一理论不仅是中国古代数学智慧的结晶，更是现代计算机科学、密码学（如 RSA 算法）、并行计算等领域不可或缺的工具。其核心在于将一个大数问题分解为多个小模数下的子问题，最后通过特定算法合并结果。
涉及同余方程组、模运算、逆元等数论基础概念。若模数两两互质，则解存在且唯一（在模所有模数乘积的意义下）。
源于公元 4-5 世纪的《孙子算经》，比欧洲高斯（Gauss）提出同类定理早了约 1100 年，被誉为世界数学史上的瑰宝。
广泛应用于RSA 公钥加密加速解密、大整数乘法优化、分布式系统数据一致性校验等场景。
在中国古代数学典籍《孙子算经》卷下第二十六题中，记载了一个著名的数学问题：
「今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？」
这个问题翻译成现代语言就是：有一个数，除以 3 余 2，除以 5 余 3，除以 7 余 2，求这个数最小是多少？
首次提出了上述“物不知数”问题的解法：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”这是世界上最早的系统性解法记录。
伟烈亚力将《孙子算经》中的解法介绍给西方，西方数学界开始关注这一东方智慧。
美国数学家莫德尔（Mordell）正式将其命名为Chinese Remainder Theorem（中国剩余定理），确立了其在世界数学史上的地位。
针对经典的“物不知数”问题，古人给出了精妙的口诀，而现代数学则将其抽象为通用的CRT 公式。
口诀云：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”
这里的数字含义如下：
对于余数分别为 的情况，解 为：
x = (r₁ × 70 + r₂ × 21 + r₃ × 15) mod 105
代入原题：。
x = (2×70 + 3×21 + 2×15) mod 105 = (140 + 63 + 30) mod 105 = 233 mod 105 = 23
故最小正整数解为 23。
设同余方程组为：
| 方程 | 含义 |
|---|---|
| 除以 余 | |
| 除以 余 | |
| ... | |
| 除以 余 |
其中要求 两两互质。
令 ，并令 。
我们需要找到 ，使得 。这里的 即为 在模 下的乘法逆元。
最终解为：
x = (sum_{i=1}^{n} a_i cdot M_i cdot y_i) pmod M如果模数 不两两互质，中国剩余定理的解是否依然存在？答案是：不一定。
当且仅当对于任意 ，都有 时，方程组才有解。此时，解在模 下唯一。
这种情况通常需要通过扩展欧几里得算法（Extended Euclidean Algorithm）逐步合并两个方程来求解。
在实际编程中，我们通常使用扩展欧几里得算法来求逆元，进而实现 CRT。以下是完整的 Python 代码示例，可直接用于解决各类同余方程组问题。
本代码实现了通用的 CRT 求解器，支持模数互质和不互质两种情况（自动检测）。
def extended_gcd(a, b):
"""扩展欧几里得算法，返回 (gcd, x, y) 使得 ax + by = gcd"""
if a == 0:
return b, 0, 1
else:
g, y, x = extended_gcd(b % a, a)
return g, x - (b // a) y, y
def modinv(a, m):
"""求 a 在模 m 下的乘法逆元"""
g, x, _ = extended_gcd(a, m)
if g != 1:
raise Exception('Modular inverse does not exist')
return x % m
def chinese_remainder_theorem(n_list, a_list):
"""
中国剩余定理求解
n_list: 模数列表 [m1, m2, ...]
a_list: 余数列表 [r1, r2, ...]
返回：最小非负整数解 x
"""
M = 1
for n in n_list:
M = n
result = 0
for i in range(len(n_list)):
mi = n_list[i]
ai = a_list[i]
Mi = M // mi
yi = modinv(Mi, mi)
result += ai Mi yi
return result % M
测试用例：物不知数问题
if __name__ == "__main__":
mods = [3, 5, 7]
remainders = [2, 3, 2]
solution = chinese_remainder_theorem(mods, remainders)
print(f"最小解为：{solution}") # 输出 23
中国剩余定理不仅仅是纸面上的数学游戏，它在现代科技中扮演着关键角色。
在 RSA 算法中，私钥解密过程涉及大数幂取模运算。利用 CRT，可以将一次大模数运算分解为两次小模数运算，速度可提升约 4 倍。这是现代互联网安全通信的基础。
在超级计算机或 GPU 集群中，处理超大整数乘法时，可将大数映射到多个较小的模数域中进行并行计算，最后通过 CRT 合并结果。这极大地提高了计算效率。
在 Reed-Solomon 码等纠错码中，CRT 用于数据的重构。即使部分数据包丢失，只要收到足够数量的包，即可通过 CRT 原理还原原始信息。
在某些特定的密码攻击场景中（如低指数攻击），攻击者可以利用 CRT 将多个密文组合，恢复出明文。理解 CRT 有助于构建更安全的加密方案。
在模 的意义下，解是唯一的。也就是说，如果你找到了一个解 ，那么 （ 为任意整数）也都是解。通常我们寻找的是最小的正整数解。
标准的 CRT 要求模数两两互质。如果模数不互质，需要检查相容性条件（即任意两个方程的余数在它们的最大公约数下同余）。如果满足条件，可以通过合并方程的方式转化为互质情况求解；否则无解。
RSA 的模数 非常大。直接计算 非常耗时。利用 CRT，可以分别计算 和 ，这两个运算速度快得多，最后再合并，整体效率提升显著。
不是。23 是最小的正整数解。实际上，任何形如 （）的数都是该问题的解。但在实际应用中（如物品数量），通常指最小正整数解。