韓信是西漢時期的名將，同時也是中國歷史上排得上號的著名軍事家。關于他有各種各樣或真或假的傳說，其中就有一個跟數(shù)學有很密切的關系。據(jù)說有一次韓信率領1500人與楚軍大戰(zhàn)，楚軍敗退，漢軍也傷亡四五百人。韓信率軍回營途中，軍士又報告楚軍來襲，韓信馬上命令整隊迎戰(zhàn)。他先按3人一排列隊，多出2人；又按5人列隊，多出3人；再按7人列隊，多出2人。于是他鼓舞士兵們說，我們一共有1073人，而楚軍不足500人，我們一定能戰(zhàn)勝楚軍。漢軍士氣大振，果然大敗楚軍。這就是所謂“韓信點兵法”。在這個故事中關于列隊方式有各種不同的說法，但在數(shù)學上這都屬于數(shù)論中的余數(shù)問題。這類問題對于同余理論的發(fā)展有重要的推動作用。
中國數(shù)學家在余數(shù)問題上有很多世界領先的研究成果。例如古代數(shù)學名著《孫子算經(jīng)》里有一個問題：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二。問物幾何？”翻譯成數(shù)學語言就是：求正整數(shù)N，使N除以3余2，除以5余3，除以7余2。
如何求符合上述條件的正整數(shù)N呢？《孫子算經(jīng)》給出了一個非常有效的巧妙解法。
“三、三數(shù)之剩二，置一百四十；五、五數(shù)之剩三，置六十三；七、七數(shù)之剩二，置三十，并之，得二百三十三。以二百一十減之，即得。凡三、三數(shù)之剩一，則置七十；五、五數(shù)之剩一，則置二十一；七、七數(shù)之剩一，則置十五。一百六以上，一百五減之，即得?！?/p>
這段文言讀起來有點拗口，但如果讀完本文下面的內容，再回頭看就不難理解了，所以暫時先不解釋。《孫子算經(jīng)》后的一千多年，十六世紀的數(shù)學家程大位在其所著的《算法統(tǒng)宗》里以歌謠的方式給出了這個問題的解法。
三人同行七十稀，
五樹梅花廿一枝，
七子團圓正半月，
除百零五便得之。
在歌謠的前三句中，每句給出一組數(shù)，分別是(3,70)，(5,21)，(7,15)。在這三組數(shù)中，每一組的前一個數(shù)就是《孫子算經(jīng)》的問題中出現(xiàn)的三個除數(shù)3、5、7，那么后一個數(shù)呢？先來看70，這個數(shù)是除以3余1且被5和7整除的最小的數(shù)。類似地，21是除以5余1且被3和7整除的最小的數(shù)，15是除以7余1且被3和5整除的最小的數(shù)。看到這里，大概很多人會有被繞口令繞暈的感覺吧。別著急，現(xiàn)在來看下面這個數(shù)：
M=2×70+3×21+2×15
我們檢驗一下M除以3、5、7的余數(shù)。注意到M是三個乘積的和，由于70被3除余1，所以第一個乘積2×70被3除余2。而后兩個乘積都能被3整除，因此M被3除余2。再來看M除以5的余數(shù)。由于第一和第三個乘積都被5整除，而第二個乘積被5除余3，所以M被5除余3。類似地可以推出M被7除余2。綜上所述，M被3除余2，被5除余3，被7除余2，正好是《孫子算經(jīng)》中所提問題的答案。容易算出M的值是233。
既然我們利用歌謠的前三句已經(jīng)給出了問題的答案，最后一句“除百零五便得知”有什么作用呢？是不是只為了湊足四句話？非也。上面雖然給出了滿足三個余數(shù)條件的一個數(shù)，但這樣的數(shù)是無窮多的。這些數(shù)有一個特點，即任兩個數(shù)的差都是3、5、7的公倍數(shù)。當數(shù)論問題的解不唯一時，數(shù)學家通常對最小解比較感興趣。歌謠的最后一句話，意思就是用233除以3、5、7的最小公倍數(shù)105，余數(shù)23就是答案。
在“韓信點兵”的故事中要求的是大于1000且滿足三個余數(shù)條件的數(shù)，所以要用23加上105的10倍，答案即為1073。
程大位通過構造三個特殊的數(shù)70,21,15，解決了一般的以3、5、7為除數(shù)的余數(shù)問題——為構造被3除余a、被5除余b、被7除余c的數(shù)，只需計算
N=a×70+b×21+c×15
N必定滿足所有余數(shù)條件，而滿足條件的最小數(shù)則是N除以105的余數(shù)。
如果直接套用程大位的歌謠公式，只能限于解決除數(shù)為3、5、7的余數(shù)問題。當除數(shù)換成其他數(shù)時，在解法中需要做相應的調整。例如，當三個除數(shù)分別為3、7、11時，我們首先要構造被3除余1且被7、11整除的數(shù)。列出7和11的公倍數(shù)77,154,231,...，其中被3除余1的最小的數(shù)是154。其次求被7除余1且被3、11整除的數(shù)，最小的是99。最后求被11除余1且被3、7整除的數(shù)，最小的是210。于是，被3除余a、被7除余b、被11除余c的數(shù)就是
a×154+b×99+c×210
如果要找滿足所有余數(shù)條件的最小的數(shù)，只需再用這個數(shù)除以3、7、11的最小公倍數(shù)231即可。
在上面的算法流程中，唯一需要變化調整的是三個具有特殊余數(shù)的數(shù)。當除數(shù)為(3,5,7)時，它們是(70,21,15)；當除數(shù)為(3,7,11)時，它們是(154,99,210)。無論除數(shù)是什么，第一個數(shù)關于三個除數(shù)的余數(shù)為1,0,0，第二個數(shù)關于三個除數(shù)的余數(shù)為0,1,0，第三個數(shù)關于三個除數(shù)的余數(shù)為0,0,1。
熟悉線性代數(shù)的同學大概會發(fā)現(xiàn)，這跟線性空間中的標準基很像。是的！在數(shù)學思想上兩者根本就是一回事。此外，求解多項式插值問題的拉格朗日插值公式用的也是這個思想。
如果理解清楚了這個思想，就很容易明白如果問題中涉及四個、五個甚至更多余數(shù)條件，這個算法仍然適用。例如，要求被2,3,5,7除的余數(shù)分別為a,b,c,d的數(shù)，我們只需相應構造四個數(shù)。第一個數(shù)是3,5,7的公倍數(shù)且被2除余1，容易求得是105。第二個數(shù)是2,5,7的公倍數(shù)且被3除余1，是70。第三個數(shù)是2,3,7的公倍數(shù)且被5除余1，是126。第四個數(shù)是2,3,5的公倍數(shù)且被7除余1，是120。所以
a×105+b×70+c×126+d×120
除以2,3,5,7的余數(shù)恰好分別是a,b,c,d。
由于余數(shù)問題最早出自《孫子算經(jīng)》，所以上面的算法在中國被稱為“孫子定理”，而國外稱之為Chinese Remainder Theorem。美國計算機科學的泰斗高德納在其著作《計算機程序設計藝術》中也專門介紹了這個算法（見卷2第286頁）。不知什么原因，這個定理重新被翻譯成中文時，通常都被叫做“中國剩余定理”。然而remainder這個詞在數(shù)學術語中本身就是表示余數(shù)，所以更恰當?shù)姆g應當是“中國余數(shù)定理”。
“孫子定理”的重要意義，遠遠不止是對一類余數(shù)問題給出了統(tǒng)一的算法。在余數(shù)問題中除數(shù)可能有三個、四個甚至更多，余數(shù)的值也有很多變化。而“孫子定理”只需要求解幾個余數(shù)很特殊的問題的解，就能把一般問題的解完全表示出來，即用“特解”表示出“通解”。這樣的思想在近代數(shù)學很多重要分支的發(fā)展中都被廣泛使用。
不過“孫子定理”在解決余數(shù)問題時還是留了個小尾巴——如何求“特解”？雖然來自實際應用的余數(shù)問題通常只涉及三四個余數(shù)，特解很容易找到，但數(shù)學家解決問題都追求一般性，他們想解決的不僅是包含三四個除數(shù)的余數(shù)問題，也不是三四十個除數(shù)，而是任意多個除數(shù)。這方面的研究中國數(shù)學家也走在了世界前列——十三世紀時南宋的秦九韶在《數(shù)書九章》里提出了“大衍求一術”，把余數(shù)問題中特解的求法也系統(tǒng)化了。
在西方，直到十八世紀時，歐拉和拉格朗日才開始對同余問題進行較為深入的研究。其后，高斯對余數(shù)問題給出了與秦九韶類似的結論，被稱為“高斯定理”。當中國數(shù)學家的研究成果被介紹到西方后，得到了西方數(shù)學界的認可和高度評價。
縱觀中國古代數(shù)學中領先于世界的研究成果，幾乎都是跟生產(chǎn)實踐有著非常緊密的聯(lián)系。例如余數(shù)問題的研究，就明顯地是受到歷法設計的需求推動。根據(jù)天文數(shù)據(jù)來修訂歷法，可能需要求解多達10個同余式，遠比《孫子算經(jīng)》的“物不知其數(shù)”問題困難多了。
中國古代數(shù)學的輝煌，已經(jīng)足以說明中國人的數(shù)學能力不亞于任何國家，只可惜由于種種歷史因素的限制，中國數(shù)學未能創(chuàng)造更大的榮耀。
最后，如果你自認為已經(jīng)理解了“孫子定理”的算法思想，不妨回到本文的開頭，看能否讀懂《孫子算經(jīng)》的那段文言？
