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

”韩信点兵法〃和中国剩余定理中国古代数学有几项研究曾经远远领先于世界，被西方称为“中国剩余定理〃的算法就是其中之一。定理中蕴含的数学思想，在世界近代数学的很多分支中都可以找到其身影。韩信是西汉时期的名将，同时也是中国历史上排得上号的著名军事家。关于他有各种各样或真或假的传说，其中就有一个跟数学有很密切的关系。据说有一次韩信率领1500人与楚军大战，楚军败退，汉军也伤亡四五百人。韩信率军回营途中，军士又报告楚军来袭，韩信马上命令整队迎战。他先按3人一排列队，多出2人；又按5人列队，多出3人；再按7人列队，多出2人。于是他鼓舞士兵们说，我们一共有1073人，而楚军不足500人,我们一定能战胜楚军。汉军士气大振，果然大败楚军。这就是所谓"韩信点兵法〃。在这个故事中关于列队方式有各种不同的说法，但在数学上这都属于数论中的余数问题。这类问题对于同余理论的发展有重要的推动作用。中国数学家在余数问题上有很多世界领先的研究成果。例如古代数学名著《孙子算经》里有一个问题："今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？"翻译成数学语言就是：求正整数N,使N除以3余2,除以5余3,除以7余2。如何求符合上述条件的正整数N呢？《孙子算经》给出了一个非常有效的巧妙解法。"三、三数之剩二，置一百四十；五、五数之剩三,

置六十三；七、七数之剩二，置三十，并之，得二百三十三。以二百一十减之，即得。凡三、三数之剩一，则置七十；五、五数之剩一，则置二d十；五、五数之剩一，则置二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由于余数问题最早出自《孙子算经》，所以上面的算法在中国被称为“孙子定理"，而国外称之为ChineseRemainderTheorem。美国计算机科学的泰斗高德纳在其著作《计算机程序设计艺术》中也专门介绍了这个算法（见卷2第286页）。不知什么原因，这个定理重新被翻译成中文时，通常都被叫做〃中国剩余定理〃。然而remainder这个词在数学术语中本身就是表示余数,所以更恰当的翻译应当是"中国余数定理〃。"孙子定理'’的重要意义，远远不止是对一类余数问题给出了统一的算法。在余数问题中除数可能有三个、四个甚至更多，余数的值也有很多变化。而"孙子定理”只需要求解几个余数很特殊的问题的解，就能把一般问题的解完全表示出来，即用"特解"表示出"通解〃。这样的思想在近代数学很多重要分支的发展中都被广泛使用。不过“孙子定理"在解决余数问题时还是留了个小尾巴——如何求"特解〃？虽然来自实际应用的余数问题通常只涉及三四个余数，特解很容易找到，但数学家解决问题都追求一般性，他们想解决的不仅是包含三四个除数的余数问题，也不是三四十个除数，而是任意多个除数。这方面的研究中国数学家也走在了世界前列——十三世纪时南宋的秦九韶在《数书九章》里提出了“大衍求一术"，把余数问题中特解的求法也系统化了。在西方，直到十八世纪时，欧拉和拉格朗日才开始对同余问题进行较为深入的研究。其后，高斯对余数问题给出了与秦九韶类似的结论，被称为"高斯定理〃。当中国数学家的研究成果被介绍到西方后,得到了西方数学界的认可和高度评价。纵观中国古代数学中领先于世界的研究成果，几乎都是跟生产实践有着非常紧密的联系。例如余数问题的研究，就明显地是受到历法设计的需求推动。根据天文