韩信点兵算法

我国汉代有一位大将，名叫韩信。他每次集合部队，都要求部下报三次数，第一次按1～3报数，第二次按1～5报数，第三次按1～7报数，每次报数后都要求最后一个人报告他报的数是几，这样韩信就知道一***到了多少人。他的这种巧妙算法，人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。 这种问题在《孙子算经》中也有记载：“今有物不知其数：三三数之余二，五五数之余三，七七数之余二，问物几何?” 它的意思就是，有一些物品，如果3个3个的数，最后剩2个；如果5个5个的数，最后剩3个；如果7个7个的数，最后剩2个；求这些物品一***有多少？这个问题人们通常把它叫作“孙子问题”， 西方数学家把它称为“中国剩余定理”。到现在，这个问题已成为世界数学史上闻名的问题。 到了明代，数学家程大位把这个问题的算法编成了四句歌诀： 三人同行七十稀，五树梅花廿一枝； 七子团圆正半月，除百零五便得知。 用现在的话来说就是：一个数用3除，除得的余数乘70；用5除，除得的余数乘21；用7除，除得的余数乘15。最后把这些乘积加起来再减去105的倍数，就知道这个数是多少。 《孙子算经》中这个问题的算法是： 70×2＋21×3＋15×2＝233 233－105－105＝23 所以这些物品最少有23个。 根据上面的算法，韩信点兵时，必须先知道部队的大约人数，否则他也是无法准确算出人数的。你知道这是怎么回事吗？ 这是因为， 被5、7整除，而被3除余1的最小正整数是70。 被3、7整除，而被5除余1的最小正整数是21； 被3、5整除，而被7除余1的最小正整数是15； 所以，这三个数的和15×2＋21×3＋70×2，必然具有被3除余2，被5除余3，被7除余2的性质。 以上解法的道理在于： 被3、5整除，而被7除余1的最小正整数是15； 被3、7整除，而被5除余1的最小正整数是21； 被5、7整除，而被3除余1的最小正整数是70。 因此，被3、5整除，而被7除余2的最小正整数是 15×2＝30； 被3、7整除，而被5除余3的最小正整数是 21×3＝63； 被5、7整除，而被3除余2的最小正整数是 70×2＝140。 于是和数15×2＋21×3＋70×2，必具有被3除余2，被5除余3，被7除余2的性质。但所得结果233（30＋63＋140＝233）不一定是满足上述性质的最小正整数，故从它中减去3、5、7的最小公倍数105的若干倍，直至差小于105为止，即 233－1o5－105＝23。所以23就是被3除余2，被5除余3，被7除余2的最小正整数。 我国古算书中给出的上述四句歌诀，实际上是特殊情况下给出了一次同余式组解的定理。在1247年，秦九韶著《数书九章》，首创“大衍求一术”，给出了一次同余式组的一般求解方法。在欧洲，直到18世纪，欧拉、拉格朗日（lagrange，1736～1813，法国数学家）等，都曾对一次同余式问题进行过研究；德国数学家高斯，在1801年出版的《算术探究》中，才明确地写出了一次同余式组的求解定理。当《孙子算经》中的“物不知数”问题解法于1852年经英国传教士伟烈亚力（wylie alexander，1815～1887）传到欧洲后，1874年德国人马提生（matthiessen，1830～1906）指出孙子的解法符合高斯的求解定理。从而在西方数学著作中就将一次同余式组的求解定理称誉为“中国剩余定理”。