孙子定理 “韩信点兵法”和中国剩余定理

惠斯

中国古代数学中有几个研究远远领先于世界，西方称为“中国剩余定理”的算法就是其中之一。定理中包含的数学思想，在世界上现代数学的很多分支中都可以找到。

韩信是西汉时期的名将，也是中国历史上著名的军事家。关于他的传说有各种各样，有真有假，其中有一个与数学密切相关。据说有一次韩信率领1500人与楚军交战，楚军后撤，韩军也伤亡了四五百人。韩信引军回营，军士报知储君来了，韩信当即下令全队出战。他先安排了三个人组队，又多了两个人；而且排了5个人，多了3个人；然后7个人排队，还有2个。于是他鼓励士兵们说，我们总共有1073人，但是楚军不到500人，我们当然可以打败楚军。汉军士气大振，真正打败了楚军。这就是所谓的“韩信点兵法”。这个故事里，关于排队的方式有各种说法，但在数学上，都属于数论中的余数问题。这类问题对同余理论的发展起到了重要的推动作用。

中国数学家在余数方面有很多世界领先的研究成果。比如古代数学名著《孙子兵法》中有一个问题:“今有未知之事，三三之数剩二，五五之数剩三，七七之数剩二。问几何？”翻译成数学语言就是:求一个正整数n，n除以3和2，除以5和3，除以7和2。

如何找到满足以上条件的正整数n？《孙子兵法》给出了一个非常有效和巧妙的解决方案。

“剩下三三个数字中的两个，买一百四；五个数字中的剩余三个，买六十三个；七，七剩二，买三十，还有，二百三十三。减去210。三个或三个数字还剩一个的地方，就设七十；如果五个或五个数字还剩一个，则设置为二十一；七，七号左一，然后买十五。如果超过一百六十，就减一百五十。”

这个文言文读起来有点别扭，但是看完下面的内容就不难理解了，暂时不解释了。16世纪数学家程大伟在《孙子兵法·经算》一千多年后，在他的《算法统一》一书中以歌谣的形式给出了这个问题的解答。

三个人同行，

五棵树上的二十一朵梅花，

七个儿子团聚半个月，

除以105。

歌谣的前三句，每一句都给了一组数字，分别是(3，70)、(5，21)、(7，15)。在这三组数中，每组的第一个数是《孙子兵法·经论》题中的三除数3、5、7。后一个数字呢？先看70。这个数是被3除然后被5和7除的最小数。同样，21是最小的数除以5再除以3和7，15是最小的数除以7再除以3和5。看到这里，大概很多人都会被绕口令搞晕。别担心，现在看看下面的数字:

M=2×70+3×21+2×15

我们来检查一下m除以3，5，7的余数。注意m是三个乘积的和。由于70除以3和1，第一个乘积2×70除以3和2。后两个乘积可以被3整除，所以m可以被3整除，余数为2。看m除以5的余数。m可以被5整除，因为第一个和第三个乘积都可以被5整除，第二个乘积可以被5整除。同样可以推导出m除以7，余数为2。综上，m除以3除以2，除以5除以3，再除以7除以2，正好是《孙子兵法·经论》中问题的答案。m的容易计算的值是233。

既然我们已经用歌谣的前三句话给出了问题的答案，那么最后一句“除了一百零五，我们就知道了”的效果如何？难道只是为了编四句话？也不是。虽然上面给出了一个满足三个余数条件的数，但是这样的数是无穷的。这些数有一个特点，就是任意两个数之差是3，5，7的公倍数。当数论问题的解不唯一时，数学家通常对最小解感兴趣。民谣最后一句意思是233除以3，5，7的最小公倍数，余数23就是答案。

《韩信点兵》故事中，要求数大于1000且满足三余数的条件，所以要把105的10倍加到23，答案是1073。

程大伟通过构造三个特殊数70、21、15，解决了以3、5、7为除数的一般余数问题——构造一个除以3 A、除以5 B、除以7 C的数，只需要计算。

N=a×70+b×21+c×15

N必须满足所有余数条件，满足条件的最小数是N的余数除以105。

如果直接应用程大为的歌谣公式，只能用3，5，7的除数来解决余数问题。当除数被其他数代替时，需要在解中做相应的调整。例如，当三个除数分别为3、7和11时，我们必须首先构造一个可被3整除并可被7和11整除的数。列出公倍数77，154，231，...7和11，其中1除以3的最小数是154。其次，求可被7整除，可被3整除，可被11整除的数，最小值为99。最后求能被11整除又能被3和7整除的数，最小值是210。所以余数A除以3，余数B除以7，余数C除以11的个数是

a×154+b×99+c×210

如果想找到满足所有余数条件的最小数，只需要将这个数除以3，7，11的最小公倍数231即可。

在上述算法流程中，只需要更改和调整三个具有特殊余数的数字。当除数为(3，5，7)时，它们为(70，21，15)；当除数为(3，7，11)时，它们是(154，99，210)。不管除数是多少，第一个数的余数是1，0，0，第二个数的余数是0，1，0，第三个数的余数是0，0，1。

熟悉线性代数的同学大概会发现，这和线性空里的标准基础很像。是的！两者在数学思想上是一回事。另外，求解多项式插值问题的拉格朗日插值公式也采用了这种思想。

如果我们清楚地理解这个思想，就很容易理解，如果问题涉及四个、五个甚至更多的余数条件，这个算法仍然适用。比如要求余数除以2，3，5，7就是a，b，c，d的数，我们只需要据此构造4个数。第一个数是3，5，7的公倍数，除以2，余数为1，很容易发现是105。第二个数是2，5，7的公倍数，除以3等于1，等于70。第三个数是2，3，7的公倍数，除以5等于1，等于126。第四个数是2，3，5的公倍数，除以7等于1，等于120。所以

a×105+b×70+c×126+d×120

除以2，3，5，7，余数正好分别是A，B，C，D。

由于余数问题起源于《孙子兵法》，所以上述算法在国内被称为“孙子定理”，而在国外则被称为中国余数定理。美国计算机科学大师Gartner在他的著作《计算机编程艺术》(见第2卷，第286页)中也介绍了这种算法。由于某种原因，当这个定理再次翻译成中文时，通常被称为“中国剩余定理”。但是“余数”这个词在数学术语中是余数的意思，所以更恰当的翻译应该是“中国余数定理”。

“孙子定理”的意义远不止是给出一类余数问题的统一算法。余数问题中，可能有三个、四个甚至更多的除数，余数的值有很多变化。“孙子定理”只需要用特殊余数来求解几个问题的解，就可以完整地表达一般问题的解，也就是用“特殊解”来表达“一般解”。这一思想被广泛应用于现代数学许多重要分支的发展中。

但“孙子定理”在解余数问题时还是留下了一条小尾巴——如何找到“特解”？虽然实际应用中的余数问题通常只涉及三四个余数，而且具体的解很容易找到，但数学家在解决问题时总是追求一般性。他们要解决的不仅仅是三四个除数的余数问题，还有三四十个除数。中国数学家在这一领域也走在世界前列——13世纪，南宋秦在《九章算术》中提出了“大求导法”，系统化了求余数问题特解的方法。

在西方，直到18世纪，欧拉和拉格朗日才开始深入研究同余。之后，高斯给出了一个类似秦九韶的结论，叫做高斯定理。中国数学家的研究成果传入西方时，得到了西方数学界的认可和高度赞扬。

纵观中国古代数学领域领先世界的研究成果，几乎都与生产实践密切相关。比如余数的研究，明显是受日历设计的需求驱动。根据天文数据修改历法，可能需要解多达10个同余公式，远比《孙子兵法》中“物不可知”的问题难。

中国古代数学的辉煌已经证明，中国人的数学能力不亚于任何一个国家。可惜由于各种历史因素，中国数学没能创造出更大的辉煌。

最后，如果你认为你已经理解了《孙子兵法》定理的算法思想，不妨回到本文的开头，看看你能否读懂《孙子兵法》计算经典中的文言文。

推名家观点

反思教育理念

探索教育问题

关注儿童数学教育

特定主题

欧拉数学会

微信号:louwen1050

QQ群:238919865

联系电子邮件:euler_math@qq.com

欧拉数学关注数学教育

长按识别二维码并注意