南北朝 · 公元5世纪
《孙子算经》成书。提出“物不知数”问题，给出具体解法和口诀，但未阐述一般性原理。
孙子定理的由来与深远影响
从《孙子算经》的“物不知数”到现代密码学的基石，探索中国剩余定理跨越千年的数学智慧。
孙子定理的由来：物不知数之谜
孙子定理（Sun Tzu's Theorem），在现代数学中更常被称为中国剩余定理（Chinese Remainder Theorem, CRT）。它的起源并非来自某位特定的“孙子”本人的独立著作，而是源于中国古代数学经典《孙子算经》。
《孙子算经》约成书于公元4世纪至5世纪之间（南北朝时期），作者佚名。在该书卷下“第26题”中，记载了一个著名的数学问题，即“物不知数”问题。这一问题的提出，标志着中国数学在同余理论领域的早期探索达到了新的高度。
「物不知数」原文解析
原文如下：
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”
翻译：有一堆物品，不知道具体数量。如果三个三个地数，最后剩下2个；如果五个五个地数，最后剩下3个；如果七个七个地数，最后剩下2个。请问这堆物品最少有多少个？
数学表达：设物品数量为 ，则满足以下同余方程组：
答案：《孙子算经》给出的答案是“二十三”。即 。验证：，，。完全符合。
解题口诀：“三人同行七十稀”
《孙子算经》不仅给出了答案，还提供了一个通用的解题算法，并配以口诀流传至今。这个口诀揭示了孙子定理的核心计算逻辑：
- 三三同行七十稀：用除以3的余数乘以70。
- 五树梅花十五枝：用除以5的余数乘以15。
- 七十古稀须仔细：用除以7的余数乘以21（注：原文口诀为“五树梅花十五枝，七十古稀须仔细，子除一百零五算”，实际乘数为70, 21, 15，此处需注意原文口诀对应关系，通常解释为：3的余数乘70，5的余数乘21，7的余数乘15。让我们修正一下标准解释：
标准解法：
1. 70是5和7的公倍数，且除以3余1。
2. 21是3和7的公倍数，且除以5余1。
3. 15是3和5的公倍数，且除以7余1。 - 子除一百零五算：将上述乘积相加后，除以3、5、7的最小公倍数105，所得余数即为答案。
在本例中：。 。 故答案为23。
历史沿革：从孙子到秦九韶
虽然《孙子算经》提出了问题，但真正将这一理论系统化、一般化，并给出完整算法证明的，是南宋数学家秦九韶。
唐朝 · 公元7世纪
张丘建在《算经》中进一步探讨了此类问题，并给出了更复杂的案例，推动了同余理论的发展。
南宋 · 公元1247年
秦九韶著《数书九章》。提出“大衍求一术”，系统解决了模数不互质及一般同余方程组的求解问题，确立了完整的算法体系。
西方 · 公元19世纪
德国数学家高斯在《算术研究》（1801年）中正式发表了中国剩余定理，西方称之为“Gauss's Theorem”。然而，秦九韶的“大衍求一术”比高斯早了500多年。
算法解析：大衍求一术与模逆元
为了更深入地理解孙子定理的由来及其数学本质，我们需要从现代数论的角度重新审视“大衍求一术”。这不仅是古代算法，更是现代模逆元计算的先驱。
核心数学原理
假设模数 两两互质。对于任意余数 ，同余方程组： 在模 下有唯一解。
孙子定理的由来关键在于构造一组“基”： 令 。 我们需要找到 关于模 的乘法逆元 ，即满足： 这个 就是秦九韶“大衍求一术”中求解的核心——“求一”。
最终解为：
“大衍求一术”操作步骤
秦九韶的算法步骤如下，以模数3, 5, 7为例：
- 定衍数：确定模数3, 5, 7。
- 求乘率：
- 对于3，衍数为 。求35模3的逆元。，。需调整。实际上，，我们需要 ，即 。但《孙子算经》用70，即 ，。
- 对于5，衍数为 。，逆元为1。乘数为21。
- 对于7，衍数为 。，逆元为1。乘数为15。
- 累加求和：。
- 取模：。
大衍求一术的精髓在于使用“辗转相除法”（欧几里得算法）的变体来高效求解逆元 ，这在当时是极具创新性的。
Python 实现示例
现代计算机求解中国剩余定理非常简便：
def chinese_remainder_theorem(pairs):
"""
pairs: 列表，元素为 (remainder, modulus)
例如: [(2, 3), (3, 5), (2, 7)]
"""
# 计算所有模数的乘积 M
M = 1
for _, m in pairs:
M = m
x = 0
for a_i, m_i in pairs:
M_i = M // m_i
# 求 M_i 模 m_i 的逆元 y_i
# 这里使用扩展欧几里得算法或 pow(M_i, -1, m_i) (Python 3.8+)
y_i = pow(M_i, -1, m_i)
x += a_i M_i y_i
return x % M
测试
result = chinese_remainder_theorem([(2, 3), (3, 5), (2, 7)])
print(f"最小正整数解: {result}") # 输出 23
现代应用：从密码学到信号处理
孙子定理的由来虽然古老，但其应用却极其前沿。在现代科技中，中国剩余定理（CRT）扮演着不可或缺的角色。
🔐 RSA 密码算法加速
在RSA解密过程中，需要计算 。利用中国剩余定理，可以将模数 分解为 和 （），分别在模 和模 下进行模幂运算，最后合并结果。这将计算复杂度降低了约4倍，极大提高了解密速度。
📡 错误校正编码
在通信领域，Reed-Solomon编码等纠错码利用同余理论来检测和纠正数据传输中的错误。当数据包丢失或损坏时，可以通过多个不同模数的余数信息，利用孙子定理重构原始数据。
🧮 大整数运算优化
在处理超大整数（如密码学中的千位大数）时，直接运算效率极低。通过中国剩余定理，可以将大整数映射到多个小模数域中进行并行运算，最后通过CRT合并结果，显著提升计算效率。
🌐 秘密共享方案
在信息安全中，Shamir秘密共享方案结合了拉格朗日插值法和中国剩余定理的思想，将一个秘密分割成多个份额，只有达到一定数量的份额才能重构秘密，确保了信息的安全性。
常见问答 (FAQ)
孙子定理的由来是什么？
孙子定理的由来可追溯至南北朝时期的《孙子算经》。书中“物不知数”问题首次记载了求解同余方程组的方法，即“三三数之剩二，五五数之剩三，七七数之剩二”。这是该定理最早的文献来源。
为什么叫中国剩余定理？
因为该定理最早由中国古代数学家在《孙子算经》中提出，后经秦九韶等人完善。19世纪西方数学家高斯等人独立发现并证明了类似结论，但时间晚于中国。为了尊重历史，国际数学界将其命名为“Chinese Remainder Theorem”。
秦九韶的“大衍求一术”是什么？
“大衍求一术”是秦九韶在《数书九章》中提出的一种求解一次同余方程组的通用算法。其核心是寻找模逆元（即“求一”），通过辗转相除法高效计算，解决了模数不互质等复杂情况，是世界数学史上的重大成就。
孙子定理在现代有什么用？
主要应用于计算机科学和网络安全。例如，在RSA加密算法中，利用中国剩余定理可以加速解密过程；在编码理论和信号处理中，用于错误检测和纠正。