韓信點兵

「韓信點兵，多多益善」這諺語，相信大家都聽過吧。但你們又知不知道韓信是如何點兵呢？原本當中有一個有關數論的小故事。

相傳漢高組劉邦打下天下之後，害怕韓信造反，所以打算把他殺了，但是，又怕他帶的士兵太多，所以問了一下韓信目前帶了多少兵？韓信感覺氣氛詭異，因此回答：「兵不知數，三三數之剩二，五五數之剩三，七七數之剩二。」（意思即：士兵數目除三的餘數是一，除五的餘數是三，除七的餘數是二。）劉邦平民出身，讀書不多，當然不大懂數學。不過他問過軍師張良，竟然連他也算不出韓信到底帶了多少土兵，劉邦無可奈何，只好放韓信一馬。

韓信畫像 （來源：維基百科）

之後於公元三世紀，中國古代的數學著作《孫子算經》便再提出類似的問題及其算法。

「孫子算經」︰「今有物，不知其數，三三數之，剩二，五五數之，剩三，七七數之，剩二，問物幾何？」
答曰：「二十三」
解曰：「三三數之剩二，置一百四十，五五數之剩三，置六十三，七七數之剩二，置三十，併之，得二百三十三，以二百一十减之，即得。凡三三數之剩一，則置七十，五五數之剩一，則置二十一，七七數之剩一，則置十五，即得。」

用現代的數學語言表示的話，就是：

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

計法是把除三的餘數乘七十，加除五的餘數乘二十一，加除七的餘數乘十五，所以：

x ≡ 2ｘ70+3ｘ21+2ｘ15 ≡ 233 ≡ 23 (mod 105)

為了突顯 70、21、15、105 這些數目，明朝的程大位在《算法統宗》（1592年）中，把它們及解答編成歌訣：

三人同行七十稀，五樹梅花廿一枝， 七子團圓正半月，除百零五便得知。

而在歐洲，直到18世紀，歐拉、拉格朗日等才對一次對一次同餘式問題進行過研究。德國數學家，有「數學王子」之稱的高斯在1801年才明確寫出了一次同餘式的求解定理，西方的數學書著於是就把這定理稱為「中國剩餘定理」。

究竟為什麼韓信用這個方法就可以計到士兵的數量？

中國剩餘定理告訴我們設m1、m2、…、mn是兩兩互質的正整數，而M = m1m2…mn那麼同餘方程組

x ≡ a1 ( mod m1 )

x ≡ a2 ( mod m2 )

…

x ≡ an ( mod mn )

必存在唯一解模M。

以下是存在性的證明，首先對於m1、m2、…、mn，我們要找出相對應的正整數b1、b2、…、bn使得bk可被M / mk整除，且bk ≡ 1 ( mod mk )。由於M / mk與mk互質，所以bk一定存在。

現在我們設y = a1b1 + a2b2 + … + anbn

y ≡ a1b1 + a2b2 + … + anbn ≡ a1(1) + a2(0) + … + an(0) ≡ a1 ( mod m1 ) [因為b1 ≡ 1 ( mod m1 )，而b2、b3、…、bn全都可被m1整除，所以b2 ≡ b3 ≡ … ≡ bn ≡ 0 ( mod m1 )]

同樣道理，y ≡ a2 ( mod m2 )、y ≡ a3 ( mod m3 ) … y ≡ an ( mod mn )。顯然，y是同餘方程組的一個解，而x ≡ y ( mod M )就是同餘方程組的解。

史丹福不在此多花時間談唯一性的證明了，證明並不困難，有興趣的讀者可以自行試試。

明白了這條定理之後，我們就知道了韓信點兵背後的秘密了。70除3時餘1，且可被5及7整除；21除5時1，且可被3及7整除；14除7時1，且可被3及5整除；而105就是3 、5及7相乘的結果。

3、5、7只是一個特殊的例子。其實任何一組兩兩互質的數字做除數，都有類似的神奇特性。我們只需要為每個除數找出相對應的數字，這個數字必須被相對應的除數除時餘一，及被其他的除數整除，就可以了。

如果我們用2、3、5這組數字的話，相對應的數字是15、10、6（大家可以試試自行驗證）。所以如果韓信改叫士兵兩個一組，再三個一組，再五個一組，那他只需要把兩個一組時士兵數目的餘數乘15，三個一組時的餘數乘10，五個一組時的餘數乘6。三個數字加起來，除30的餘數就是答案了。