在基礎數論裏有一個中國餘數定理。給定一組正整數兩兩互素,也就是任意兩個數沒有大於一的公因子。現有一個未知數,它除以這個數組裏每個數的餘數是知道的,求解這個未知數。中國餘數定理是對這個問題的解答。
中國古代最有名的數學書“九章算術”裏有一個問題:求知一個數,它除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人一排以十排作為一個方陣。如果不到一百人,數一下有幾排人後再數餘下的人數。點兵對於古羅馬人是個很簡單的事。