郑涛（Tao Steven Zheng）著

【问题】

以下是一个著名的数论问题，来自《孙子算经》（活在公元 3 - 5 世纪）。这道题有涉及到模算术（modular arithmetic）、模逆（modular inverse）、两两互素（coprime）、中国剩余定理（Chinese remainder theorem）等数论概念。

【原文】

今有物，不知其数。三、三数之，剩二；五、五数之，剩三；七、七数之，剩二。问：物几何？

【今译】

假设有些物，不知其数量。三个三个去数，剩下 2 个；五个五个去数，剩下 3 个；七个七个去数，剩下 2 个。问：物的数量是多少？

（求最小正整数解）

【题解】

这个问题是一个具有无穷多解的不定方程组。根据题意，得

注：同余式 表示 除以 剩余 ，亦即 为整数。称 为模数（modulus）， 为余数（remainder）。

因为 3、5、7 都是两两互素（coprime 或 relatively prime）模数，我们只用计算模数（modulus）的乘积：

中国剩余定理（Chinese remainder theorem）的解规定

对于这个问题

和

其中

  表示每个余数的模逆（modular inverse）。利用秦九韶 (1202 年- 1261 年) 的大衍求一术可以系统地求解模逆; 不过，这个问题涉及的数字很小，可以通过猜测和检查得到。

计算

对于这个问题，233确实是一个解，但这不是最小正整数解。

最小正整数解为 23。

《孙子算经》的答案与解法

【原文】

答曰：二十三。

术曰：“三、三数之，剩二”，置一百四十；“五、五数之，剩三”，置六十三；“七、七数之，剩二”，置三十。并之，得二百三十三。以二百一十减之，即得。凡三、三数之，剩一，则置七十；五，五数之，剩一，则置二十一；七、七数之，剩一，则置十五。一百六以上，以一百五减之，即得。

【今译】

答案：23。

解法：“三个三个去数，剩下2个”布置 140。“五个五个去数，剩下 3 个” 布置 63。“七个七个去数，剩下 2 个”布置 30。把这些数并起来得到 233。然后减去 210 得到答案。当三个三个去数，布置 70，得到1的余数。当五个五个去数，布置 21，得到 1 的余数。当七个七个去数，布置 15 得到 1 的余数。当结果是 106 以上，以 105 减去得到答案。