一道题走了一千年——从物不知数到中国剩余定理

从一个问题开始

《孙子算经》卷下第三十五题：

$$\text{三三数之，賸二；五五数之，賸三；七七数之，賸二。问：物几何？}$$

三个一数剩二个，五个一数剩三个，七个一数剩二个。问总数是多少？

答曰：二十三。

验算：$23 \div 3 = 7 \cdots 2$，$23 \div 5 = 4 \cdots 3$，$23 \div 7 = 3 \cdots 2$。三个条件全中。

第 11 讲讲过这道题，重点放在那三个构造数怎么来的。这一讲要往前推一步：这套办法后来变成了什么？

时间线

最重要的三个节点：

$$\text{公元 4-5 世纪} \quad \text{《孙子算经》成书，给出此题与算法}$$ $$\text{公元 1247 年} \quad \text{秦九韶《数书九章》，推广为一般解法}$$ $$\text{公元 1852 年} \quad \text{高斯《算术探究》，西方独立给出同样的一般解法}$$

从孙子到秦九韶，隔了约八百年；从秦九韶到高斯，隔了六百零五年。而这条理论的现代名字，叫「中国剩余定理」。

示意图

深入理解

一、孙子给的算法：三个数各管一件事

《孙子算经》的术文说：三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十。并之得二百三十三，以二百一十减之，即得。

为什么是这三个数？检查它们被各模数除的余数：

$$140 \div 3 = 46 \cdots 2, \quad 140 \div 5 = 28 \cdots 0, \quad 140 \div 7 = 20 \cdots 0$$ $$63 \div 3 = 21 \cdots 0, \quad 63 \div 5 = 12 \cdots 3, \quad 63 \div 7 = 9 \cdots 0$$ $$30 \div 3 = 10 \cdots 0, \quad 30 \div 5 = 6 \cdots 0, \quad 30 \div 7 = 4 \cdots 2$$

每个数只对同一个模数贡献余数，对其余两个模数的余数都是零。

相加得 $233$，它继承了三个「专责余数」。$233$ 本身就是解，只是太大——减去一个 $210$（$=3 \times 5 \times 7 \times 2$）得到 $23$，余数不变。

这是第一层：一道具体题，用构造法解出。

二、秦九韶做了什么：把「构造」变成「程序」

秦九韶的贡献不是解出新题，是回答了一个更一般的问题：换掉这三个数，这套办法还能不能走？

他的答案写进了《数书九章》，方法叫大衍总数术。

先分清一对常被混淆的名字：

$$\text{大衍总数术} \quad \text{—— 完整解法，从化约到出答案的全过程}$$ $$\text{大衍求一术} \quad \text{—— 其中「求乘率」这一步的子程序}$$

「大衍」取自《周易》「大衍之数五十」，秦九韶借用这个名字，因为他发现《周易》揲蓍法的数学结构正是一组同余关系。他把这套算法放在《数书九章》最前面，视为最重要的创作。

完整解法分五步：

第一步，化问约为定数。 如果给出的模数不是两两互质（比如 4 和 6），要先化成互质的定数。这一步《孙子算经》里没有，因为那道题天然互质。

第二步，求衍母。 把各定数相乘，得衍母。对应《孙子算经》里的 210。

第三步，求乘率。 对每个模数 $m_i$，求一个 $k_i$ 使

$$k_i \cdot \frac{G}{m_i} \equiv 1 \pmod{m_i}$$

这就是「大衍求一术」。 以物不知数为例：

$$k_1 \cdot 35 \equiv 1 \pmod 3 \Rightarrow k_1 = 2 \quad (2 \times 35 = 70 = 23 \times 3 + 1)$$ $$k_2 \cdot 21 \equiv 1 \pmod 5 \Rightarrow k_2 = 1$$ $$k_3 \cdot 15 \equiv 1 \pmod 7 \Rightarrow k_3 = 1$$

第四步，求用数。 乘率乘 $\dfrac{G}{m_i}$，得各用数：$2 \times 35 = 70$、$1 \times 21 = 21$、$1 \times 15 = 15$。这三个数正是《孙子算经》末尾说的「三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五」——原来孙子留下的是通用构件，不是这一题的偶然数字。

第五步，求总数。 各用数乘对应余数，求和，再减去衍母的倍数。以本题为例：

$$2 \times 2 \times 35 + 1 \times 3 \times 21 + 1 \times 2 \times 15 = 140 + 63 + 30 = 233$$ $$233 - 210 = 23$$

这是第二层：从一道题的一套办法，变成任意题的一套程序。

三、它今天在做什么

1852 年，高斯在《算术探究》中给出了同样的一般解法。今天它叫中国剩余定理（Chinese Remainder Theorem），内容是：

$$\text{若模数两两互质，则同余方程组在模 } G \text{ 意义下有唯一解。}$$

听起来是纯数论，但它今天最热闹的应用在密码学和计算机里。

RSA 加速。 RSA 的模数 $n = pq$（$p,q$ 为大素数），解密时先分别在模 $p$ 和模 $q$ 下计算（数字小一半，速度快四倍左右），再用剩余定理合并结果。这个技巧叫「RSA-CRT」，几乎所有高效实现都在用。

秘密共享。 把一个秘密 $s$ 拆成若干份，每份是 $s$ 对某个模数的余数。少于规定人数，信息不足；达到规定人数，用剩余定理即可还原。中国剩余定理直接给出了「多少人能打开」的数学机制。

此外：纠错码、快速傅里叶变换的模数分解、分布式计算的任务分发，都能见到它。

四、一个提醒

《孙子算经》给出了构造数，秦九韶给出了求构造数的程序，高斯给出了抽象表述。三件事不是重复，是每一步都在扩大能处理的问题范围。

今天课堂上一道「三三数之」的小题，和 RSA 里那个加速技巧，用的是同一条定理。这个跨度值得学生体会。

在高中数学体系里的位置

整除与带余除法。 这是最基础的落点：$23 = 3 \times 7 + 2$ 里的「余」，正是同余记号里的东西。

算法的思想。 大衍总数术清晰展示了「化约 → 求母 → 求率 → 求用数 → 求总数」的流水线。它不是一条公式，是一个流程。今天学编程的人最熟悉这种结构。

数学史与民族自信。 中国剩余定理是少有的以中国命名的数论定理。从《孙子算经》到秦九韶到高斯，脉络完整。

思考与拓展

1. 复算物不知数：按五步法走一遍，验证乘率是 $2,1,1$，用数是 $70,21,15$，总数是 23。

2. 化约定数：若模数是 4 和 6，按秦九韶的办法化成互质定数，说明化成什么、衍母是多少。

3. 找一组新题：自己编一道「四四数之剩一，五五数之剩二，六六数之剩三」，用五步法解出来，并用穷举验算。

4. 查 RSA-CRT：了解 RSA 解密是怎么靠中国剩余定理加速的，为什么速度能快数倍。

5. 同余与周期：$23$ 和 $233$ 都是解。它们差多少？为什么差这个数就是周期？周期与模数有什么关系？

一句话总结

从「置一百四十、六十三、三十」到「求乘率」到「中国剩余定理」，一道小题走了两千年，最后走进了 RSA 的实现里。