韓 信 點 兵

韓信點兵是一個有趣的游戲，如果你隨便拿一把棋子（數(shù)目在100粒左右），先3粒3粒數(shù)，不滿3粒的記下余數(shù)；再5粒5粒數(shù)，不滿5粒的記下余數(shù)；最后7粒7粒地數(shù)，也把余數(shù)記下來。然后根據(jù)每次的余數(shù)，就可以知道你原來拿的棋子總共有多少。
如：3個一數(shù)余1粒，5個一數(shù)余2粒，7個一數(shù)余2粒，那么原有棋子是多少呢？
    它的算法很簡單，而且在我國古代就有。宋朝周密叫它“鬼谷算”或“隔墻算”；楊輝叫它“剪管術(shù)”；而“韓信點兵”是較通行的名稱。至于它的算法，在《孫子算經(jīng)》上早有說明，后來在宋朝經(jīng)過數(shù)學家秦九韶的推廣，又發(fā)現(xiàn)了一種算法，叫“大衍一術(shù)”。這就是外國人所稱的“中國剩余定理”，是數(shù)學史上極有名的問題。
那么到底怎樣來計算呢？
A×70＋b×21＋c×15－105
其中a、b、c分別為3個、5個、7個一數(shù)的余數(shù)。如果得出數(shù)還是比105大，就再減去105，一直到得數(shù)比105小為止。
因此你可以很容易地知道，前面問題的答案了
1×70＋2×21＋2×15－105＝37（粒）。
那么“韓信點兵”里為什么要3個一數(shù)，5個一數(shù)，7個一數(shù)呢？周其它的數(shù)可以嗎？我們先研究一下“韓信點兵”的解法

“70a＋21b＋15c－105”。
我們先來看一下70、21、15、105這4個數(shù)和3、5、7之間的關(guān)系：
（1）70＝2×5×7，70＝3×23＋1，所以70是5和7的一個公倍數(shù)，它被

3除后余數(shù)是1.
（2）同理，21是3與7的一個公倍數(shù)，它被5除后余數(shù)是1.
（3）15是3與5的一個公倍數(shù)，它被7除后余數(shù)是1.
（4）105＝3×5×7，是3、5、7的最小公倍數(shù)。
根據(jù)上面的這些關(guān)系，“70a＋21b＋15c－105”確實是所求的得數(shù)。

所以，70a＋21b＋15c－105被3除的余數(shù)是1。據(jù)同樣的道理，這個數(shù)被5除后的余數(shù)是2，被7除后余數(shù)是2.
那么，“韓信點兵”里為什么要用3、5、7這三個數(shù)呢？

我們知道，3、5、7中任意兩個數(shù)的最大公約數(shù)都是1，也就是說是兩兩互素。

于是就可以找到這樣一個數(shù)，是3、5、7其中兩個數(shù)的公倍數(shù)，而被另一個數(shù)除后余數(shù)是1，類似70、21、15。這也就是“韓信點兵”中的三個數(shù)的要求。

那么不是兩兩互素的數(shù)，是不是就一定找不到類似70、21、15的數(shù)呢？

如4、6、7這三個數(shù)，4與6不是互素，它們的最大公約數(shù)是2，而6與7的任何一個公倍數(shù)都是偶數(shù)，被偶數(shù)4除后的余數(shù)也一定是偶數(shù)，而不可能是1，所以是找到與70、21、15相當?shù)娜齻€數(shù)的。因此在“韓信點兵”里就不能用。
我們也可以不用3、5、7這三個數(shù)，而換成其它兩兩互素的數(shù)，如2、3、11.這時的計算式是“33a＋22b＋12c－66”。不信的話，你可以用上文中的例子試一試，看是不是37粒。

中國剩余定理（Chinese Remainder Theorem）在近代抽象代數(shù)學中占有一席非常重要的地位。 我國漢代有一位大將，名叫韓信。他每次集合部隊，都要求部下報三次數(shù)，第一次按1～3報數(shù)，第二次按1～5報數(shù)，第三次按1～7報數(shù)，每次報數(shù)后都要求最后一個人報告他報的數(shù)是幾，這樣韓信就知道一共到了多少人。他的這種巧妙算法，人們稱為“鬼谷算”、 “隔墻算”、“秦王暗點兵”等。到了明代，數(shù)學家程大位把這個問題的算法編成了四句歌訣：
三人同行七十稀，
五樹梅花廿一枝，
七子團圓正半月，
除百零五便得知。
這就是韓信點兵的計算方法，它的意思是：凡是用3個一數(shù)剩下的余數(shù)，將它用70去乘（因為70是5與7的倍數(shù)，而又是以3去除余1的數(shù)）；5個一數(shù)剩下的余數(shù)，將它用21去乘（因為21是3與7的倍數(shù)，又是以5去除余1的數(shù)）；7個一數(shù)剩下的余數(shù)，將它用15去乘（因為15是3與5的倍數(shù)，又是以7去除余 1的數(shù)），將這些數(shù)加起來，若超過105，就減掉105，如果剩下來的數(shù)目還是比105大，就再減去105，直到得數(shù)比105小為止。這樣，所得的數(shù)就是原來的數(shù)了。