“韩信点兵法”和中国剩余定理.docx
”韩信点兵法和中国剩余定理中国古代数学有几项研究曾经远远领先于世界，被西方称为“中 国剩余定理的算法就是其中之一。定理中蕴含的数学思想，在世界 近代数学的很多分支中都可以找到其身影。韩信是西汉时期的名将，同时也是中国历史上排得上号的著名军 事家。关于他有各种各样或真或假的传说，其中就有一个跟数学有很 密切的关系。据说有一次韩信率领1500人与楚军大战，楚军败退，汉 军也伤亡四五百人。韩信率军回营途中，军士又报告楚军来袭，韩信 马上命令整队迎战。他先按3人一排列队，多出2人；又按5人列队， 多出3人；再按7人列队，多出2人。于是他鼓舞士兵们说，我们一 共有1073人，而楚军不足500人,我们一定能战胜楚军。汉军士气 大振，果然大败楚军。这就是所谓"韩信点兵法。在这个故事中关 于列队方式有各种不同的说法，但在数学上这都属于数论中的余数问 题。这类问题对于同余理论的发展有重要的推动作用。中国数学家在余数问题上有很多世界领先的研究成果。例如古代 数学名著孙子算经里有一个问题："今有物不知其数，三三数之 剩二，五五数之剩三，七七数之剩二。问物几何？"翻译成数学语言 就是：求正整数N ,使N除以3余2 ,除以5余3 ,除以7余2。如何求符合上述条件的正整数N呢？孙子算经给出了一个非 常有效的巧妙解法。"三、三数之剩二，置一百四十；五、五数之剩三,置六十三；七、七数之剩二，置三十，并之，得二百三十三。以二百一十减之，即得。凡三、三数之剩一，则置七十；五、五数之剩一，则置二d；七、七数之剩一，则置十五。一百六以上，一百五减之，即得。这段文言读起来有点拗口，但如果读完本文下面的内容，再回头 看就不难理解了，所以暂时先不解释。孙子算经后的一千多年， 十六世纪的数学家程大位在其所著的算法统宗里以歌谣的方式给 出了这个问题的解法。三人同行七十稀，五树梅花廿一枝， 七子团圆正半月， 除百零五便得之。在歌谣的前三句中，每句给出一组数，分别是(3,70) , (5,21), (7,15)。在这三组数中，每一组的前一个数就是孙子算经的问题中 出现的三个除数3、5、7 ,那么后一个数呢？先来看70 ,这个数是除 以3余1且被5和7整除的最小的数。类似地，21是除以5余1且被 3和7整除的最小的数，15是除以7余1且被3和5整除的最小的 数。看到这里，大概很多人会有被绕口令绕晕的感觉吧。别着急，现 在来看下面这个数：M=2x70+3x21+2xl5我们检验一下M除以3、5、7的余数。注意到M是三个乘积的 和，由于70被3除余1 ,所以第一个乘积2x70被3除余20而后两 个乘积都能被3整除，因此M被3除余2。再来看M除以5的余数。 由于第一和第三个乘积都被5整除，而第二个乘积被5除余3 ,所以 M被5除余3。类似地可以推出M被7除余2。综上所述，M被3除 余2 ,被5除余3 ,被7除余2 ,正好是孙子算经中所提问题的答 案。容易算出M的值是233。既然我们利用歌谣的前三句已经给出了问题的答案，最后一句 "除百零五便得知”有什么作用呢？是不是只为了凑足四句话？非也。 上面虽然给出了满足三个余数条件的一个数，但这样的数是无穷多的。 这些数有一个特点，即任两个数的差都是3、5、7的公倍数。当数论 问题的解不唯一时，数学家通常对最小解比较感兴趣。歌谣的最后一 句话，意思就是用233除以3、5、7的最小公倍数105 ,余数23就 日卷安在"韩信点兵”的故事中要求的是大于1000且满足三个余数条件的数,所以要用23加上105的10倍,答案即为1073。程大位通过构造三个特殊的数70,21,15 ,解决了一般的以3、5、 7为除数的余数问题一为构造被3除余a、被5除余b、被7除余c 的数，只需计算N=ax70+bx21+cxl5N必定满足所有余数条件，而满足条件的最小数则是N除以105 的余数。如果直接套用程大位的歌谣公式，只能限于解决除数为3、5、7 的余数问题。当除数换成其他数时，在解法中需要做相应的调整。例 如，当三个除数分别为3、7、11时，我们首先要构造被3除余1且被 7、11整除的数。列出7和11的公倍数77,154,231,.,其中被3除 余1的最小的数是154O其次求被7除余1且被3、11整除的数，最 小的是990最后求被11除余1且被3、7整除的数，最小的是210o 于是，被3除余a、被7除余b、被U除余c的数就是axl54+bx99+cx210如果要找满足所有余数条件的最小的数，只需再用这个数除以3、 7、11的最小公倍数231即可。在上面的算法流程中，唯一需要变化调整的是三个具有特殊余数 的数。当除数为(3,5,7)时，它们是(70,21,15);当除数为(3,7,11)时， 它们是(154,99,210)。无论除数是什么，第一个数关于三个除数的余 数为L0Q ,第二个数关于三个除数的余数为QL0 ,第三个数关于三个 除数的余数为0,0,1。熟悉线性代数的同学大概会发现，这跟线性空间中的标准基很像。 是的！在数学思想上两者根本就是一回事。此外，求解多项式插值问 题的拉格朗日插值公式用的也是这个思想。如果理解清楚了这个思想，就很容易明白如果问题中涉及四个、 五个甚至更多余数条件，这个算法仍然适用。例如，要求被2,357除 的余数分别为a,b,c,d的数，我们只需相应构造四个数。第一个数是 3,5,7的公倍数且被2除余1 ,容易求得是105o第二个数是2,5,7的 公倍数且被3除余1 ,是70o第三个数是2,3,7的公倍数且被5除余 1 ,是126O第四个数是2,3,5的公倍数且被7除余1 ,是120。所以axl05+bx70+cxl26+dxl20除以2,357的余数恰好分别是a,b,c,do由于余数问题最早出自孙子算经，所以上面的算法在中国被 称为“孙子定理"，而国外称之为Chinese Remainder Theorem。美 国计算机科学的泰斗高德纳在其著作计算机程序设计艺术中也专 门介绍了这个算法（见卷2第286页）。不知什么原因，这个定理重 新被翻译成中文时，通常都被叫做中国剩余定理。然而 remainder这个词在数学术语中本身就是表示余数,所以更恰当的翻 译应当是"中国余数定理。"孙子定理'的重要意义，远远不止是对一类余数问题给出了统 一的算法。在余数问题中除数可能有三个、四个甚至更多，余数的值 也有很多变化。而"孙子定理”只需要求解几个余数很特殊的问题的 解，就能把一般问题的解完全表示出来，即用"特解"表示出"通 解。这样的思想在近代数学很多重要分支的发展中都被广泛使用。不过“孙子定理"在解决余数问题时还是留了个小尾巴如何 求"特解 ？虽然来自实际应用的余数问题通常只涉及三四个余数， 特解很容易找到，但数学家解决问题都追求一般性，他们想解决的不 仅是包含三四个除数的余数问题，也不是三四十个除数，而是任意多 个除数。这方面的研究中国数学家也走在了世界前列十三世纪时 南宋的秦九韶在数书九章里提出了 “大衍求一术"，把余数问题 中特解的求法也系统化了。在西方，直到十八世纪时，欧拉和拉格朗日才开始对同余问题进 行较为深入的研究。其后，高斯对余数问题给出了与秦九韶类似的结 论，被称为"高斯定理。当中国数学家的研究成果被介绍到西方后, 得到了西方数学界的认可和高度评价。纵观中国古代数学中领先于世界的研究成果，几乎都是跟生产实 践有着非常紧密的联系。例如余数问题的研究，就明显地是受到历法 设计的需求推动。根据天文数据来修订历法，可能需要求解多达10个 同余式，远比孙子算经的“物不知其数"问题困难多了。中国古代数学的辉煌，已经足以说明中国人的数学能力不亚于任 何国家，只可惜由于种种历史因素的限制，中国数学未能创造更大的 荣耀。最后，如果你自认为已经理解了 "孙子定理的算法思想，不妨 回到本文的开头，看能否读懂孙子算经的那段文言？
