中国余数定理：从“物不知数”到“大衍求一术”

metoo

余数定理对于一般人来说，可能有些陌生，但提起韩信点兵法，知道的人就多了，小学奥数题中也会碰到这样的题。中国余数定理是老祖宗的研究成果，曾经领先世界一千多年，是国际数学界命名的唯一冠以“中国”的数学定理。以下试从非专业角度作一解读。

* * * * * * * * * *

1801年，意大利天文学家皮亚齐发现了一颗小行星，命名为谷神星，但因耽误了观测，失去了这颗星的轨迹。数学家高斯通过以前的观测数据，计算出谷神星的运行轨迹，成功地找到了谷神星。高斯的计算依据的是他刚刚发表在《算术研究》一书中的同余理论。

此时的高斯并不知道，1400年之前，在地球的另一边，已经有人提出同余问题，并推导出解决同余问题的定理，只是没有给它命名。这就是“物不知数”问题，记载在中国南北朝时期的数学专著《孙子算经》中。

19世纪中叶，英国传教士把《孙子算经》中“物不知数”问题的解法带回欧洲。西方数学界发现，中国一千多年前的解法与高斯得出的同余定理相合，因而将其定名为“中国余数定理”（旧译“中国剩余定理”）。由于定理最早的提出者是孙子，又称之为“孙子定理”。

“物不知数”问题出自《孙子算经》下卷26题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：‘二十三’”。

这道题的意思是，一堆东西，比如苹果，3个3个一数剩下2个，5个5个一数剩下3个，7个7个一数剩下2个，问这堆苹果有多少个？

这个问题看起来不复杂，但《孙子算经》给出了一个有些烧脑的解法：

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

上面的解法是说，根据本题给出的三个条件分别得到140、63和30三个数，三数相加等于233，再减去210，最终得到23这个答案。

这些数是怎么得来的，没讲，让人觉得很玄妙。中国古代师傅教徒弟，道理经常不说透，让徒弟自己悟出来。这时是公元5世纪。

到了13世纪，南宋数学家秦九韶把《孙子算经》中的这个问题拿出来重新研究，把这类问题的解法研究透了，并定名为“大衍求一术”，写入《数书九章》的数学专著中。

当时有好事者将大衍求一术求解“物不知数”问题的方法简化成四句诗：

三人同行七十稀，

五树梅花廿一支，

七子团圆正半月，

除百零五使得知。

下面试作解读。

《孔子算经》中说的“物不知数”，就是未知数，在本题中相当于被除数；三三一数，五五一数，七七一数，这里的3、5、7相当于除数，剩几就是余几，即余数。这里的已知条件是余数和除数，求被除数。

回到那首诗，它实际上是除数为3、5、7，余数为任意数的“物不知数”题的通解口诀（下称“四句诀”）。中国古代数学家发现，一个数分别被多个数相除，已知它们的余数，这个数一定是一个更大的除数的余数。此题中更大的除数，就是四句诀最后一句中的“百零五”，即3、5、7的最小公倍数105。前三句中的“七十”、“廿一”、“半月”，即70、21、15，是三除数中每两个除数的公倍数。计算求解时，三个数先分别与除数3、5、7（“三人”、“五树”、“七子”）的余数相乘，然后再相加。在“物不知数”的例题中，余数分别为2、3、2，计算过程如下：x=2×70+3×21+2×15=233

得数233是符合题意的其中一个数。因为它又是除数105的余数，所以233还要减去两次105，得到23。23是符合条件的最小正整数解。

这里出现一个疑问：四句诀中给出的21和15分别是3与7的乘积和3与5的乘积，而70却不是5与7的乘积35，而是35的2倍。此处的不一致，是因为这里的“70”隐含了运算中的一个数--乘率，实际应表述为“35×2”，乘率为2。也就是说，对于一个数除以任意三个数的余数题，大衍求一术的通解公式可以这样表述（设三除数为a、b、c）：

x=除a的余数×b和c的积×乘率1+除b的余数×a和c的积×乘率2+除c的余数×a和b的积×乘率3。

以上公式可以看作是三个部分相加，每个部分由3个除数之一的余数乘以另两个除数的乘积，再乘以乘率组成。此公式可扩展适用于有更多除数的余数题。

大衍求一术最重要的贡献就是乘率的计算法。前面提到，四句诀中的“70”包含了乘率“2”，这个数是怎么得来的？

这个乘率要依b和c的积35除以3的余数而定。35除以3，余2。这时要找到一个数，乘以余数2后，满足除以3余1，这个数就是乘率。2乘以余数2等于4，4除以3余1，满足条件，乘率就是2。而a和c的积是21，21除以5余数是1；a和b的积是15，15除以7余数也是1。由于余数为1，乘率也为1，计算中忽略不计，后两个的乘率在四句诀中没有留下痕迹。

“物不知数”题在小学奥数题中经常出现。常见的题型有韩信点兵法，也是已知几个几个一排余几，求总数。但小学奥数题的解法均不用大衍求一的解法。像《孙子算经》中的这道题，奥数的解法简单多了：5个5个一数余3，最小的数是5+3=8，8同时满足除以3余2，但不满足除以7余2。8加上15（3×7的积）是符合前两个条件的第二小的数，得到23，23同时满足除以7余2的第三个条件。假如23不符合第三个条件，则23还要再加上15，继续在满足前两个条件的数的范围里去找符合第三个条件的数。这种解法叫逐步满足法。

遇到再复杂一点儿的题，奥数解法中有不定方程解法，上题列方程（a、b、c为三除数的商）如下：

3a+2=5b+3=7c+2

a、b、c最小的一组正整数解为：

a=7

b=4

c=3

将a=7代入3a+2，得到23。

看起来，奥数的解法简单，大衍求一的解法繁琐，为什么呢？

这是因为，奥数只是挑选出不用大衍求一术就能解的题，而大衍求一术针对的是天文历法方面的计算，数字很大，除数多达10个以上，一般无法简单地用逐步满足法或方程解法得到结果。大衍求一术是求解同余问题的通解法。

下面这道题，就只有用大衍求一的方法去解。

今有数不知总，以5累减之剩3，以715累减之剩538，以247累减之剩174，以391累减之剩109，以187累减之也剩109，问总数若干。（得数：5200018）[清]黄宗宪：《求一术通解》

上题中的除数（“累减之”的意思是“除”），其中之一化简后转化成除以143余108。由于数字较大，无法直接看出108乘以几（乘率）满足除以143余1，此时就需要用大衍求一术中的辗转相除法：将143与108相除，108与相除后的余数再相除，前面的余数与后面的余数再相除，直到最后得到1时再反推出等式1=108×49-143×37，此式等同于108×49÷143=37……1，符合余1的条件，因此得出乘率为49。有了乘率，代入前面提到的大衍求一术的计算公式就可以计算出结果了。

这个解题过程就是在“求一”。

前文中提到的人物：

孙子是南北朝时期的人，生平事迹未见记载，和《孙子兵法》的作者同名，时代不同。

宋人秦九韶研究数学是业余爱好。他年轻时通过科举考试出仕，长期担任地方官，《数书九章》一书是他在为父守孝期间完成的。

瑞士出生的数学家高斯一生心无旁骛，潜心于数学研究，成果斐然。他24岁时用数学方法找到谷神星，30岁被德国哥廷根大学看中，聘请为教授和天文台台长，直到去世。

注：本文中的“除数”，在同余理论中称为“模”（mod)。同余符号为“≡”。比如前文中的23除以3余2，用同余概念表达为：23和2对于模3同余，意思是23和2除以3，余数相同(均为2)，记作：23≡2 (mod 3)。