面对复杂的同余方程组，如何快速找到那个唯一的“最小正整数解”？中国剩余定理（Chinese Remainder Theorem, CRT）给出了完美的答案。本文将带您穿越时空，从古老的《孙子算经》出发，深入剖析其数学本质，并揭示其在现代计算机科学和密码学中的核心地位。
在日常生活中，我们常遇到需要同时满足多个条件的情况。例如，一个数除以 3 余 2，除以 5 余 3，除以 7 余 2，这个数是多少？这类问题在数学上被称为一次同余方程组。中国剩余定理正是解决此类问题的通用公式。
设 是两两互质的正整数，令 。则对于任意整数 ，同余方程组：
在模 的意义下有唯一解。
简单来说，只要各个除数（模数）之间没有共同的因子（除了 1），我们就一定能找到一个数，它同时满足所有的余数条件，而且这个解在模所有除数乘积的范围内是唯一的。
中国剩余定理最早见于公元 4 世纪的中国古代数学著作《孙子算经》卷下第二十六题。这道题目被后世称为“物不知数”问题，其原文如下：
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”
翻译成现代语言就是：有一堆物品，不知道具体数量。如果每 3 个一数，剩下 2 个；每 5 个一数，剩下 3 个；每 7 个一数，剩下 2 个。请问这堆物品最少有多少个？
《孙子算经》给出的解法非常精妙，并附有著名的口诀：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”
让我们代入题目数据验证一下：
答案是 23。验证：，，。完全符合！
《孙子算经》成书，记载“物不知数”问题，标志着中国剩余定理的雏形出现。
秦九韶在《数书九章》中系统总结了“大衍求一术”，将该方法推广到模数不互质的情况（广义中国剩余定理），并给出了完整的算法流程。
欧洲数学家高斯（Gauss）在《算术研究》中独立提出了类似的同余理论，西方学界开始广泛接受这一理论。
英国汉学家李约瑟等学者将中国古代数学成就介绍到西方，正式命名为“Chinese Remainder Theorem”。
虽然古人有口诀，但在处理更复杂、模数更多的情况时，我们需要一套通用的现代算法逻辑。以下是求解中国剩余定理的标准步骤：
首先检查所有模数 是否两两互质。如果不是，需要使用扩展中国剩余定理（ECRT）。假设已满足条件，将方程组写成标准形式：
x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂) ... x ≡ aₙ (mod mₙ)
确保每个余数 都在 范围内。
将所有模数相乘，得到总模数 ：
对于每一个方程 ：
寻找逆元通常使用扩展欧几里得算法（Extended Euclidean Algorithm）。
将所有部分相加：
最后对 取模，得到最小正整数解：
为了让大家彻底理解中国剩余定理怎么理解，我们通过一个具体的例子进行全流程推演。
求解 ：
| 方程 | 含义 |
|---|---|
| 除以 3 余 2 | |
| 除以 5 余 3 | |
| 除以 7 余 2 |
结论：该方程组的最小正整数解为 23。
很多读者在学习中国剩余定理后，会好奇它在现代社会有什么用？事实上，它是现代密码学的基石之一。
在 RSA 解密中，需要计算 ，其中 。直接计算大指数模幂非常耗时。利用 CRT，可以分别计算 和 ，这两个运算速度快得多，最后再用 CRT 合并结果。这使得解密速度提升约 4 倍。
在大规模数据处理中，CRT 可用于将一个大整数运算分解到多个处理器上并行执行。每个处理器处理一部分模数，最后通过 CRT 合并结果，极大提高了计算效率。
在通信领域，CRT 被用于构造 Reed-Solomon 码等纠错码。通过将信息编码为同余方程组的余数，即使部分数据在传输中丢失，也能通过剩余的余数重构出原始信息。
某些伪随机数生成器利用 CRT 的性质，将多个周期较短但性质好的线性同余发生器组合成一个周期极长的生成器。
如果模数 不互质（例如 ），标准的 CRT 不再适用。此时需要使用扩展中国剩余定理。
如果有解，可以将两个方程合并为一个等价的新方程，其模数为 ，然后继续与其他方程合并，直到求出最终解。
理解了原理，如何用代码实现呢？下面是一个基于 Python 的简洁实现，使用了扩展欧几里得算法来求逆元。
用于求解 ，进而求出逆元。
def extended_gcd(a, b):
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):
g, x, y = extended_gcd(a, m)
if g != 1:
raise Exception('Modular inverse does not exist')
else:
return x % mdef chinese_remainder_theorem(n_list, a_list):
"""
n_list: 模数列表 [m1, m2, ...]
a_list: 余数列表 [a1, a2, ...]
返回：最小正整数解
"""
# 1. 计算总模数 M
M = 1
for n in n_list:
M = n
result = 0
# 2. 遍历每个方程
for i in range(len(n_list)):
m_i = n_list[i]
a_i = a_list[i]
# 计算 M_i = M / m_i
M_i = M // m_i
# 计算逆元 t_i
t_i = modinv(M_i, m_i)
# 累加
result += a_i M_i t_i
# 3. 取模得到最终解
return result % M
测试用例
if __name__ == "__main__":
mods = [3, 5, 7]
remainders = [2, 3, 2]
solution = chinese_remainder_theorem(mods, remainders)
print(f"最小解为: {solution}") # 输出 23从《孙子算经》的“物不知数”到现代互联网安全的基石，中国剩余定理展现了数学跨越千年的生命力。它不仅是一个优美的数学定理，更是连接古代智慧与现代科技的桥梁。希望本文能帮助您彻底理解中国剩余定理，并在实际学习和应用中游刃有余。