中國剩餘定理

中國剩餘定理 (Chinese Remainder Theorem)
國立臺灣師範大學數學系洪萬生教授/國立臺灣師範大學數學系洪萬生教授責任編輯

「中國剩餘定理」是指中國古代用以求解《孫子算經》「物不知數題」的一種方法：

今有物不知其數，三三數之賸二，五五數之賸三，七七數之賸二，問物幾何？

答曰：二十三。

術曰：三三數之賸二，置一百四十；五五數之賸三，置六十三；七七數之賸二，置三十。并之得二百三十三。以二百一十減之，即得。凡三三數之賸一，則置七十，五五數之賸一，則置二十一，七七數之賸一，則置十五。一百六以上，以一百五減之，即得。

在上述的「術曰」（解法）中，\(70\) 是個可被 \(5\)、\(7\) 整除、但除以 \(3\) 餘數為 \(1\) 的數；\(21\) 是個可被 \(3\)、\(7\) 整除、但除以 \(5\) 餘數為 \(1\) 的數；\(15\) 是個可被 \(3\)、\(5\) 整除、但除以 \(7\) 餘數為 \(1\)的數。

至於 \(140\)、\(63\)、\(30\) 則由其各自的餘數所決定。可見，這一方法（「術曰」）涉及「求一」，所以在中國古代被稱為「求一術」。

在現代數論 (number theory) 中，這一方法當然連結到十九世紀高斯所創造的同餘 (congruence) 理論。事實上，一旦掌握了同餘理論，不僅求一術相關問題，其他一些初等算術中的可除性判別法則 － 譬如一個自然數可以被 \(13\) 整除的充要條件為何等等，當然也變得十分淺顯易解。

數學理論結構誠然必須擺在學習的第一順位。目前，學生學習的一個通病，顯然是升學競爭所造成的知識之徹底零碎化，其實，這也是一百多年前，德國偉大數學家克萊因 (Felix Klein, 1849-1925) 所批判的煩瑣章句之學，而其代價則是知識的系統性理解之欠缺。為了導正這種流弊，我們認為在教學過程中，教師應盡力協助學生培養系統性或結構性的理解。

當然，我們也承認在高級中學的數學課程中，有些知識或方法不是那麼容易形成一個系統或結構，不過，適當地組織一些單元，似乎還是可以「風雅地」介紹有一點結構意義的內容。這樣子說，並不表示現行教科書缺乏結構，只是在課堂上徒然增加許多解題活動，而無從利用論證來引進結構，顯然導致學生領略不到知識學習的核心價值與意義。

「求一術」始見於《孫子算經》，不過，將它集大成的南宋數學家秦九韶，在他的《數學九章》中，卻完全不曾提及。到了明代，雖然算學家將物不知數題的「術曰」編成歌訣以廣流傳，似乎也收到了普及的效果，譬如明代程大位《算法統宗》(1592) 中，就有所謂的「孫子歌」：「三人同行七十稀，五樹梅花廿一支，七子團圓正半月，除百令五便得知。」

不過，此一方法真正有進一步發展的時期，則是要等到清中葉之後。乾隆時編輯《四庫全書》，編者從《永樂大典》中抄出《數學九章》，四庫版再經過李銳校訂後，張敦仁、駱騰鳳、時曰醇以及黃宗憲等，都有所發明。

我們先提及當時有關求一術起源的一些看法，然後，再回來簡介秦九韶的大衍求一術。張敦仁《求一算術》(1803) 序稱：「筭數之學，自九章而後，述作滋多，其最善者則有二術。一曰立天元一，一曰求一。盡方圓之變，莫善於立天元一，窮奇偶之情，莫善於求一。求一之術出於《孫子筭經》物不知數之問。」可見，當時數學家對於求一術的重視。

此外，左潛為黃宗憲《求一通解》作序時，也指出：「近日精算諸家，後先接踵，精思妙理，鑿險通幽其因仍舊術而絕無增變者，為大衍一術已耳。」這是因為他認為「《孫子筭經》物不知數一題，以三、五、七立算，在大衍題尚為淺顯，經中有術無草，殆未深求至理，原非有意故秘機緘。」至於論及秦九韶著述《數書九章》時，則認為他「始立約分求等、求乘率諸法，數雖繁瑣，理實精深，後之攻是術者，皆未能洞悉其源，是以於所以然之理，具未能切近言之也。」顯然這些評論都針對了傳統中算的「徒法而缺理」之不足。

回到中國南宋時期，秦九韶 (1202-1261) 在他的著作《數書九章》(1247) 中，將此問題推廣到任意的模數（非兩兩互質）及餘數。至於此求解的方法，就稱為「大衍總數術」，是先將模數化為兩兩互質，再用「大衍求一術」去求解，對相關的理論和算法，作了集大成的工作。

事實上，「物不知數題」經由秦九韶的一般化，的確是高斯1801年所發表的相關定理之先聲，因此，西方國家稱此類型的問題為「中國剩餘定理」(Chinese Remainder Theorem)，的確合乎情理。

至於孫子與秦九韶的貢獻，則多虧了傳教士偉烈亞力 (Alexander Wylie) 1856年在 North China Herald（《北華捷報》）所發表的論文 “Jottings on the Science of the Chinese Arithmetic”（中國算術論叢）。本論文先翻譯成德文，再翻譯成法文，在歐洲學術界流傳甚廣，因此，此一定理最後冠上形容詞「中國的」(Chinese)，並且出現在歐美一般的數論或代數教科書上，才顯得相當水到渠成。

現在，且讓我們說明中國剩餘定理如何與秦九韶的「求一」有關了。中國剩餘定理當然涉及下列一次同餘式的聯立解：

\(N\equiv R_i\pmod{m_i},~i=1,2,3,…,n\)，且當 \(i\ne j\)，\(m_i,m_j\) 互質。

如令 \(\displaystyle M=\coprod^n_{i=1}m_i\) (乘積)，

則存在有 \(K_i\)，使得 \(\displaystyle K_i\frac{M}{m_i}\equiv 1\pmod{ m_i},~i=1,2,3,…,n\)，

於是 \(\displaystyle N\equiv \sum_{i=1}^nK_i\frac{M}{m_i}R_i\pmod{M}\)  即為所求。

這裡解法的關鍵，當然就在於如何轉換成為「求一」的問題了。

至於如何求一呢？請看秦九韶的「大衍求一術」：

大衍求一術云：置奇右上，定居右下，立天元一於左上。先以右上除右下，所得商數與左上一相生，入左下。然後乃以右行上下，以少除多，遞互除之，所得商數隨即遞互累乘，歸左行上下。須使右上末後奇一而止，乃驗左上所得，以為乘率。

試以 \(K\cdot 20\equiv\pmod{27}\) 為例：

得到 \(K=23\)。

事實上，秦九韶對於「物不知數」題的延拓，還涉及非整數的模數，這是目前所謂的「中國剩餘定理」的版本之所缺，值得我們注意。

參考書目

1. 洪萬生 (2009).〈求一術的出路：同餘理論有何教學價值與意義？〉，《數學快遞》第二期：1-8。
2. 楊瓊茹 (2009).〈求一與占卜〉，收入洪萬生等著，《當數學遇見文化》（台北：三民書局），頁72-83。
3. 楊瓊茹 (2009).〈翦管術 vs. 天算頌〉，收入洪萬生等著，《當數學遇見文化》（台北：三民書局），頁151-160 。
4. 郭書春主編 (2010).《中國科學技術史：數學卷》，北京：科學出版社。