2009年8月8日

韓信點兵

作者/游森棚

根據這幾年我看到的經驗,不少中學老師都希望在專業上持續成長,但卻常卡在一個兩難的迷惑中: 大學的數學太過抽象,和實地教學兜不起來。因此我在服務的系上,每年辦一次「高中教師數學成長工作坊」,選定高中數學常見的問題,說說其背後的高等數學。上個月我選定的問題是韓信點兵,老師們反應熱烈,在此跟讀者分享。

台灣的學生都知道,只要數學課出現韓信,他就在點兵,而且多半點成兩種結果:「餘數相等」或「不足數相等」。不過,一旦既非「餘數相等」也非「不足數相等」,那就頭大了。我以前碰到這種問題都直接放棄,因為我只會從兵的總數n = 0, 1, 2, 3, 4,...慢慢賭運氣,除此以外無計可施。究竟要怎麼求n?又怎麼知道一定算得出n?

這令人頭大的問題大有來頭。流傳已久的《孫子算經》裡就有:今有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?翻成白話文就是:韓信點兵,三個三個一數餘二人,五個五個數餘三人,七個七個數餘二人,請問兵有幾人?歷代不少數學家研究過,直到南宋秦九韶的「大衍求一術」,給了個非常聰明的解法:假設兵的總數是n,則

n = a × 2 + b × 3 + c × 2 + 105k 。其中

(1)a 是一個整數,它是5, 7 的倍數,且除以3 餘1;

(2)b 是一個整數,它是3, 7 的倍數,且除以5 餘1;

(3)c 是一個整數,它是3, 5 的倍數,且除以7 餘1;

(4)k 是任意整數。

a, b, c是多少待會兒再說。我們先看看,把上式的n 除以3 時發生什麼事? n 除以3 餘2——因為a除以3餘1,故a×2除以3 餘2;而b, c, 105 都是3 的倍數,故後面三項都是3的倍數。同理, n 除以5 餘3;而n 除以7 餘2 。所以, n 就是我們要的答案。

這真是非常,非常聰明的想法,我每看到一次就驚歎一次。讀者一定要細細品味。

但是a, b, c 還不知道啊,我們可以用試的。a 必須是5, 7 的倍數,且除以3 餘1 。稍微試一下可取a=70。同理,取b=21,c=15 。所以

n = 70 × 2 + 21 × 3 + 15 × 2 + 105k =233 + 105k ,

因此兵最少有233 - 105 × 2 = 23 人。

如果讀者理解上面的說明,就可以發現這個方法不管餘數是多少都可用。關鍵根本不是餘數,而是70, 21, 15 這三個數。也就是說,「三三數之剩r1 ,五五數之剩r2 ,七七數之剩r3」的解就是「x = 70 × r1 + 21 × r2 + 15 × r3+105k」,代入r1, r2, r3就解決了所有的問題。明朝程大位在《算法統宗》中給了一首詩來背解法(好像補習班口訣):三人同行七十稀,五樹梅花廿一支,七子團圓正半月,除百零五便得知。詩說,除以3 的那個部分放「70」,然後5 的部分放「21」,而7 的部分放「15」,最後扣掉105(的倍數)。

如果以上方法要說有什麼不盡人意之處,就是a, b, c = 70, 21, 15 都是「試出來的」。這很不科學,萬一試不出來呢?不會的,因為有輾轉相除法作擔保!科學的作法如下:

因為3 和5 × 7 = 35 互質,所以利用輾轉相除法,一定找得到整數x, y使得3x+35y=1(用輾轉相除法,將3 和35 所得的公因數1反著操作回去,就可以把1寫成3和35的加加減減)——那個35y就是我們要的a(除以3餘1 ,且是5, 7 的倍數)!此例中有3 × 12 + 35×(-1)= 1 ,可調整成3 ×(-23)+ 35 × 2=1所以取a=70。同理,讀者可以試試看,由5 和3 × 7 = 21 互質可得b = 21 ,由7 和15互質可得c=15。這就是那首詩中三個關鍵數的由來。

所以3, 5, 7互質是重要的——最大公因數是1,才能保證上述的算法管用。另一方面,如果n1, n2 都是解,那n1 與n2 分別除以3, 5, 7餘數皆相同。因此n1 - n2 是3, 5, 7 的倍數,即n1 - n2 = 105k 。

綜合上述的說明,我們其實已經證明了赫赫有名的中國餘數定理(Chinese remaindertheorem):假設m1, m2, m3 兩兩互質,若韓信點兵m1, m2, m3個一數,餘數分別是r1, r2, r3,則不管餘數r1, r2, r3 是多少,都一定求得出兵的人數。而且如果n 是解,則n + km1m2m3 也都是解。

故事似乎已經告一段落,但數學的發展奠基於更本質的理解。回到原來除以3, 5, 7的問題。既然任給餘數r1, r2, r3 都找得出一個0 ≦n ≦ 104 的答案,中國餘數定理換句話可以這樣說:把除以3, 5, 7的餘數寫成一個坐標(r1,r2, r3)。則{(0, 0, 0)(, 1, 1, 1),...(, 2, 4, 6)}這105個坐標,剛好跟{0, 1, 2,..., 104}這105個數一一對應。【更進一步的內容,請參閱第476期科學月刊】

回本期目錄

沒有留言: