綜觀人類歷史，或是為了丈量土地、商賈往來，或是為了打發時間，中國、日本、印度、埃及、南美等地區都曾獨自發展出簡單的算術和幾何學。不過攤開現在的數學史，大抵都以埃及、希臘(泰勒斯、畢達哥拉斯、阿基米德等人)的發展為主支，是以歐洲為主體的歷史。文藝復興時期是義大利，其後逐漸向北，十八世紀為法國(及英國的牛頓)，其後德國也在統一前後竄起。直到二十世紀初期，美國、俄國(主要在現代機率論奠基)才逐漸登上舞台。
東亞臉孔正式躍上數學史已是二次大戰時的事情*1，比較有名的大抵是金融數學裡隨機微積分所使用的伊藤引理(Ito's Lemma)(來自日本數學家伊藤清先生)。再過來就已經是相當現代，還在世的人物，諸如在微分幾何學裡舉足輕重的丘成桐先生，或是前幾年在孿生質數問題上取得重大發展的張益唐先生。
但是在他們之前，其實有個數學定理已為歐洲所知，並以尊重世界上最早探討該問題的中國著作為名。今天的伍德說數就要來帶大家談談充滿西方氣息的數學史中，來自東方的一縷微光：中國剩餘定理(Chinese Remainder Theorem；CRT)。
一、由來
中國剩餘定理(Chinese Remainder Theorem)又稱中國餘式定理、中國餘數定理或孫子定理。出處為(推定為)南北朝的數學著作《孫子算經》。當然，這個孫子不是寫《孫子兵法》的那位孫武(時代差了一千年左右)。
當時的問題如下：「有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？」翻成現代的語言，就是「某個數除以三餘二、除以五餘三、除以七餘二，請問某數是多少？」用更專業的術語，稱為「一次同餘方程組」。
中國餘式定理就是用來處理這種只知道某數除以某些數的餘數，進而反推原先有多少數的問題。在中國數學史上，這類問題又被稱為「鬼谷算」，並延伸出「剪管術」、「大衍求一術」(出自北宋秦九韶)等解答方式*2。
說起這本《孫子算經》，除了啟發中國剩餘定理外，著名的雞兔同籠問題(日本的鶴龜算)也出自此書(例題：關了雞和兔子的籠子裡點到10顆頭，30隻腳，請問雞兔各幾隻？)。相信各位在國一的時候應該都用二元一次方程式解過，這裡就不多談。
另外，談到中國餘式定理，現今的科普文章常常將它和韓信點兵相提並論，甚至也有資料說本問題的出處就是劉邦一次巡幸雲夢大澤，問韓信領多少兵，韓信只回了上面的問題，嚇得張良說無法得知其數。當然，張良的回答不能說錯(我們在下個部分詳細來解)，但韓信真有這麼聰明就不會落到被殺頭的命運了。況且，西漢可遠遠在南北朝之前，怎麼可能時光錯置*3。
伍德覺得奇怪，索性去翻了史記，
根本沒有這段故事(「韓信點兵，多多益善」倒是出自史記沒錯)。能查到最早將中國餘式定理和韓信點兵結合在一起的，其實是2006年莫宗堅教授在科學月刊上所寫的半科普半小說的
文章*4，可見以訛傳訛的力量有多強。
二、解答
那麼怎麼解中國剩餘定理的問題呢？相較上面的問題，我們用比較簡單的例子(兩個條件)來談。
「某個數除以三餘二、除以五餘三，請問某數是多少？」
最簡單的方式是從0開始一個一個試，試到最後讀者應該可以驗算出8這個答案(你也可以只試2、5、8等滿足第一個條件的數字)。如果各位同意8是答案的話，23、38、53、...，答案其實相當多。他們的共通點是都差15，而15是3和5的公倍數。原理是因為15/3=5、15/5=3，所以加上15並不會影響餘數。只要a是答案，a+15(和a-15)就也是答案。換句話說，我們只要在0-14裡面找到一個答案，就能把所有答案寫下來了。而中國剩餘定理簡單來說，就是保證我們在0-14裡絕對找得到答案。
同理，「某個數除以五餘三、除以七餘二，請問某數是多少？」
試了下3、8等滿足第一個條件的數字後，應該可以找到一個答案：23。這裡因為題目是除以5和7，循環會是每35一次(5和7的公倍數)。也就是說其他答案包含了58、93、...。同樣地，中國剩餘定理保證我們在0-34裡一定能找到答案。
那麼系統性該怎麼解決這類問題？我們回到例題一，用Mod語言來寫(不熟者請參考
這篇)，若答案為a，我們有：
a=2 (mod 3) 和 a=3 (mod 5)。
我們想找b和c兩個數，使得：
b=1 (mod 3) 和 b=0 (mod 5)；
c=0 (mod 3) 和 c=1 (mod 5) *5
這樣a=2*b+3*c (mod 15)。
試一下各位應該能解出b=10、c=6。因此a=2*10+3*6 (mod 15)=38 (mod 15)=8 (mod 15)。
我們來看原版在孫子算經內的問題：「某個數除以三餘二、除以五餘三、除以七餘二，請問某數是多少？」
有了前面的經驗，我們應該能猜出這裡的解會以105為單位循環(3、5、7的最小公倍數)。一種作法是先解兩個條件，再驗算第三個條件。在上面我們解過前兩個條件：8、23、38、...，所以一個一個驗算後，我們得到一個解：23。配上以105為一循環的條件，其他解便是128、233、...。所以解並不唯一。上面的故事裡張良說算不出來，的確不能說錯。這裡不厭其煩再說一次，中國餘式定理保證我們在0-104裡絕對找的到解。
明朝數學家程大位在著作《算法統宗》裡曾經針對這個問題寫了口訣。
「三人同行七十希，五樹梅花廿一支，七子團圓正半月，除百零五便得知。」
翻成白話，除3的餘數乘以70，除5的餘數乘以21(廿：音同念，20的意思)，除7的餘數乘以15(半月，一個月30天計)，最後除以105(的餘數)就是答案了。我們驗算看看：2*70+3*21+2*15=233，而233除以105的餘數正是23。這個做法的原理其實就是後來我們提到的系統性做法(求基底)，這裡伍德不細談。
三、應用--RSA的加速運算
當今中國剩餘定理最重要的應用，應該是在
RSA加密法中
加速運算(忘記的請看連結)。在加解密的過程中，我們需要計算a^b (mod N)，其中a、b都是很大的數字，而N=pq，是兩個質數的乘積。
我們可以先算a^b (mod p) 和 a^b (mod q)，因為p和q都是質數，兩者都可以使用費馬小定理：a^(p-1)=1 (mod p)來加速運算。接著就能使用中國剩餘定理還原a^b (mod N)了。看起來雖然是繞了遠路，實際上運算速度會加快。
四、結論
中國剩餘定理是少數在十九世紀，就已經為西方所知，出自亞洲的定理。雖然是個老牌定理，但到了現代還是在密碼學有所應用。儘管現代的數學史都以歐洲系統為主(符號系統最方便)，同時期的亞洲其實也有很多有趣的想法。在國際交流越來越容易的現代，研究者們不必也不能再閉門造車，好好學習彼此的優點，激發新的想法，才能加速科學進程。
那麼我是伍德‧瓦懷特，我們下一期伍德說數再見！
*1. 這不是指東亞沒有在研究數學，只不過中國、日本都各自發展出一套和歐洲不同的系統。
*2. 伍德由衷覺得古人在取名上，中二的程度真的不輸現在的人們。
*3. 《孫子算經》只陳述問題本身，並沒有像當今應用題一樣設情境。
*4. 伍德要是考證有錯，請馬上讓我知道。
*5. 學過線性代數的朋友，直接將b和c看成基底(Basis)就對了。事實上原版的中國剩餘定理就是個同構(Isomorphism)定理。當然，這是後見之明，當時的中國是沒有這種概念的。
創作內容
東方微光--談中國剩餘定理
魔都妖探 (1)
