作者 | 林開亮
在最近推出的兩篇文章
①微積分之前奏1：高階等差數列的求和
②算命是胡扯，猜姓卻不然
中，我們都提到了中國剩餘定理，雖然我曾在
從射鵰到九章——在天大理學院物理系的通俗報告
介紹過，但有點浮光掠影，我們想在此詳細介紹一下。
我們期待，本文作為好玩的數學開創的頭一個專欄——一周一定理——的開篇，能夠打響第一炮。本專欄的開創，學習和借鑑了下述網頁（感謝上海交通大學數學系吳耀琨教授向我們推薦）
有興趣的讀者，可以先瀏覽這個主頁上的各個定理。歡迎各位讀者為本專欄供稿，投稿郵箱在這裡來，一起交流數學。
好了，現在我們直奔主題。
中國剩餘定理：設正整數m1，m2，…，mn兩兩互素，則下述同餘方程組
（其中r1，r2，…，rn給定的整數）的整數解恰好是模
M=m1m2…mn
的一個剩餘類。事實上，方程 (*) 的通解為
x=r1M1x1+…+rnMnxn+kM，k∈Z (#)
其中Mi=M/mi，而xi是同餘方程
Mixi≡1(mod mi) (*i)
的一個特解，因而可以用求一術得出。
簡單地說，中國剩餘定理將一個同餘方程組（*）的求解，歸結為多個一次同餘方程（*i)的求解，而後者可以用求一術來求解。那麼，什麼是求一術呢？我們表述成一個算法的形式：
求解方程
的整數解的求一術：
首先寫出矩陣
然後對第一行兩個元素輾轉相除，並將對應的操作應用於第二行，直至第一行某個元素變成0（停止信號），此時觀察第一行的另一個元素：若它恰好是1（正常信號），則它下方的那個數就是（♣）的一個特解；否則，（♣）無整數解。此外，若已得到（♣）的一個特解，比方說，，那麼，（♣）的通解為
注：我們不打算證明求一術，它本質上就是解線性方程組的矩陣變換方法。我們指出，在中國古代還未出現0時，通常是用輾轉相減（即「更相減損術」），所以最後終止的信號是，出現的等數（即最大公因子）為1，這就是求一術名稱的來由（對此，請參見許光午和李寶[4]）。另一方面，注意到方程（♣）本質上是在求逆，所以，也許一個更恰當的稱謂是求逆術。由此可以理解，為什麼在下述網頁中，作者用了逆的記號來表述結果：
好了，現在我們來實戰吧。首先，我們解釋上述網頁中的例子，即我們要求解同餘方程組
為求解這個方程組，我們來求解兩個更簡單的方程組
與
先看（1），注意到（1）的第二個方程相當於說，x是5的倍數，因此我們可以令
從而代入（1）的第一個方程，就把（1）整個轉化為一次同餘方程
在這個特殊情況，我們可以直接看出（1*）的一個特解為
類似的，我們來求解方程組(2), 注意到它的第一個方程相當於說
從而（2）可化為線性方程
容易觀察到，（2*）的一個特解為
（註：當然你也可以取x2=4，就像上述網頁中那樣）
因此，根據中國剩餘定理，原方程組(0）的通解為
最經典的一個例子，即金庸曾在《射鵰英雄傳》原著中引用的「鬼谷算題」：
我們留給有興趣的讀者自行研究，其求解步驟，可以參考從射鵰到九章——在天大理學院物理系的通俗報告。
而在94版的射鵰電視劇中，這個題目被編劇稍微改了改（參見下述連結最後部分），你能算出來嗎，你猜神算子瑛姑能算出來嗎？
延伸閱讀：
[1] 華羅庚，從孫子的「神奇妙算」談起，數學小叢書，北京，科學出版社。
[2] 蔡聰明，談韓信點兵問題，《科學月刊》第29卷第9期。電子版可見數學知識網頁：http://episte.math.ntu.edu.tw/
[3] 項武義，從韓信點兵和勾股弦說起一一漫談基礎數學的古今中外，《數學傳播》，電子版http://web.math.sinica.edu.tw/math_media/d211/21101.pdf（建議在谷歌瀏覽器打開網頁版，並開啟翻譯功能。近日我們會推出該文的簡體版）
[4] 許光午，李寶，大衍求一術的算法意義與分析
https://arxiv.org/ftp/arxiv/papers/1610/1610.01175.pdf
好玩的數學以數學學習為主題，以傳播數學文化為己任，以激發學習者學習數學的興趣為目標，分享有用的數學知識、有趣的數學故事、傳奇的數學人物等，為你展現一個有趣、好玩、豐富多彩的數學世界。