中國餘數定理和韓信點兵

在基礎數論裏有一個中國餘數定理。給定一組正整數兩兩互素，也就是任意兩個數沒有大於一的公因子。現有一個未知數，它除以這個數組裏每個數的餘數是知道的，求解這個未知數。中國餘數定理是對這個問題的解答。

	中國古代最有名的數學書“九章算術”裏有一個問題：求知一個數，它除3餘2，除5餘3，除7餘2.。書上沒有給出這種問題的一般解法，但找出23這個數並不是很難。

	很多科普文章說這個問題的提出源自“韓信點兵”：韓信讓一群士兵分別站成三人一排，五人一排，七人一排。每次站隊時可能會有餘下的士兵。從這三個餘數就能知道這一群士兵有多少人。

	讓我們來仔細看看這個過程，檢查一下韓信點兵裏可能會出現的問題。首先如果兩個數除以三，五，七的餘數是相同的，則兩數之差可以整除三，五，七，因而就能整除這三個數的乘積一百零五。反之如果兩數之差可以整除一百零五則它們除以三，五，七的餘數是同樣的。因而僅僅從三個餘數無法唯一確定未知數。首先必須確定這個未知數在一個差別小於一百零五的範圍，例如從一到一百零五，從兩千三百到兩千四百零四。

	下麵我們假定一個等於一百零五的範圍給定了。任意一個在這個範圍裏的數除三會有三個可能的餘數，除五會有五個可能的餘數，除七會有七個可能的餘數，當然包括零餘數。三個餘數的所有可能剛好是一百零五。因而從三個餘數可以唯一確定未知數。

	那麽怎樣從這三個餘數決定未知數呢？有公式說從70m + 21n + 15p加減一百零五的適當倍數就能得出未知數。這裏m,n,p是未知數除以三，五，七的餘數。還可以列個表把每個數和它的三個餘數列成四個數字一行的表，然後按照餘數的順序重新列表好從三個餘數查出未知數。

	以未知數在一到一百零五為例。如果三個餘數都為零未知數是一百零五。如果三個餘數不都為零未知數是70m + 21n + 15p除以一百零五的餘數。當然如果70m + 21n + 15p是在一到一百零四之間它就是未知數。在m=2,n=3,n=2時， 70m + 21n + 15p=233。然後把233除以105得到餘數23。也可以列表第一行為 0， 0， 1， 15；第二行為 0， 0， 2， 30；一共一百零五行。 查表時則以餘數為序從 2，3，2，23那一行得知未知數為23。

	如果未知數是在兩千三百到兩千四百零四之間，我們得把233加上2100得到2333這個數。查表的話，先得列個表把一百零五種可能的餘數列出，後麵列出有關的未知數。

	那麽韓信在點兵知道三個餘數後能不能一口報出士兵的人數呢？假如他知道人數不超過105，則看一下表他的確就能一口報出。要是用公式算則要費點功夫。要是人數多但在一個差105的範圍內，查表也可以， 當然要多費點功夫。用公式算就更費功夫了。

	無論是查表還是用公式，韓信應該都是能做到的。列個表帶在身邊不是很難的事。至於他如何得到公式我們不清楚。但70，21，15是很特別的數，它們的餘數分別為1，0，0；0，1，0；0，0，1。一旦他知道了公式記住用就行了。

	韓信沒有帶過兵和同時代的古羅馬軍隊作戰。韓信沒法向他們學學更好的點兵法。古羅馬的軍隊列成10人一排以十排作為一個方陣。如果不到一百人，數一下有幾排人後再數餘下的人數。點兵對於古羅馬人是個很簡單的事。

[野性de思維]

有趣！