中國剩餘定理

中國剩餘定理，又稱孫子定理或中國餘數定理，是數論中的一個關於一元線性同餘方程組的定理，說明了一元線性同餘方程組有解的準則以及求解方法。該定理在中國古代也被稱為「韓信點兵」、「求一術」（宋 沈括）、「鬼谷算」（宋 周密）、「隔牆算」（宋 周密）、「剪管術」（宋 楊輝）、「秦王暗點兵」、「物不知數」等。

物不知數

一元線性同餘方程組問題最早可見於中國南北朝時期（公元5世紀）的數學著作《孫子算經》卷下第二十六題，叫做「物不知數」問題，原文如下：

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

即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。《孫子算經》中首次提到了同餘方程組問題，以及以上具體問題的解法，因此在中文數學文獻中也會將中國剩餘定理稱為孫子定理。孫子沒正式證明，但後來印度數學家及天文學家阿耶波多給出具體過程，徹底解決了此定理的任何給定實例。

最初對「物不知數」問題作出完整系統解答的是宋朝數學家秦九韶，載於1247年《數書九章》卷一、二《大衍類》中，從而使這一問題變為定理。明朝數學家程大位在《算法統宗》中將解法編成易於上口的《孫子歌訣》：

三人同行七十稀，五樹梅花廿一支，七子團圓正半月，除百零五便得知

這個歌訣給出了模數為3、5、7時候的同餘方程的秦九韶解法。意思是：將除以3得到的餘數乘以70，將除以5得到的餘數乘以21，將除以7得到的餘數乘以15，全部加起來後再減去105或者105的整數倍，得到的數就是答案（除以105得到的餘數則為最小答案）。比如說在以上的物不知數問題裡面，使用以上的方法計算就得到

$70\times 2+21\times 3+15\times 2=233=2\times 105+23.$

因此按歌訣求出的結果就是23。

《數書九章》最初由偉烈亞力在19世紀初譯為英文，而西方世界最早的完整系統解法由高斯在1801年提出。

形式描述

用現代數學的語言來說明的話，中國剩餘定理給出了以下的一元線性同餘方程組：

$(S):\quad \left\{{\begin{matrix}x\equiv a_{1}{\pmod {m_{1}}}\\x\equiv a_{2}{\pmod {m_{2}}}\\\vdots \qquad \qquad \qquad \\x\equiv a_{n}{\pmod {m_{n}}}\end{matrix}}\right.$

有解的判定條件，並用構造法給出了在有解情況下解的具體形式。

中國剩餘定理說明：假設整數m₁, m₂, ... , m_n其中任兩數互質，則對任意的整數：a₁, a₂, ... , a_n，方程組$(S)$有解，並且通解可以用如下方式構造得到：

1. 設$M=m_{1}\times m_{2}\times \cdots \times m_{n}=\prod _{i=1}^{n}m_{i}$是整數m₁, m₂, ... , m_n的乘積，並設$M_{i}=M/m_{i},\;\;\forall i\in \{1,2,\cdots ,n\}$，即$M_{i}$是除了m_i以外的n − 1個整數的乘積。
2. 設$t_{i}=M_{i}^{-1}$為$M_{i}$模$m_{i}$的數論倒數：$t_{i}M_{i}\equiv 1{\pmod {m_{i}}},\;\;\forall i\in \{1,2,\cdots ,n\}.$
3. 方程組$(S)$的通解形式為：$x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}+kM=kM+\sum _{i=1}^{n}a_{i}t_{i}M_{i},\quad k\in \mathbb {Z} .$ 在模$M$的意義下，方程組$(S)$只有一個解：$x=\sum _{i=1}^{n}a_{i}t_{i}M_{i}.$

證明

從假設可知，對任何$i\in \{1,2,\cdots ,n\}$，由於$\forall j\in \{1,2,\cdots ,n\},\;j\neq i,\;\;\operatorname {gcd} (m_{i},m_{j})=1$，所以$\operatorname {gcd} (m_{i},M_{i})=1.$ 這說明存在整數$t_{i}$使得$t_{i}M_{i}\equiv 1{\pmod {m_{i}}}.$ 這樣的$t_{i}$叫做$M_{i}$模$m_{i}$的數論倒數。觀察乘積$a_{i}t_{i}M_{i}$可知：

$a_{i}t_{i}M_{i}\equiv a_{i}\cdot 1=a_{i}{\pmod {m_{i}}},$

$\forall j\in \{1,2,\cdots ,n\},\;j\neq i,\;\;a_{j}t_{j}M_{j}\equiv 0{\pmod {m_{i}}}.$

所以$x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}$滿足：

$\forall i\in \{1,2,\cdots ,n\},\;\;x=a_{i}t_{i}M_{i}+\sum _{j\neq i}a_{j}t_{j}M_{j}\equiv a_{i}+\sum _{j\neq i}0=a_{i}{\pmod {m_{i}}}.$

這說明$x$就是方程組$(S)$的一個解。

另外，假設$x_{1}$和$x_{2}$都是方程組$(S)$的解，那麼：

$\forall i\in \{1,2,\cdots ,n\},\;\;x_{1}-x_{2}\equiv 0{\pmod {m_{i}}}.$

而$m_{1},m_{2},\ldots ,m_{n}$兩兩互質，這說明$M=\prod _{i=1}^{n}m_{i}$整除$x_{1}-x_{2}$. 所以方程組$(S)$的任何兩個解之間必然相差$M$的整數倍。而另一方面，$x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}$是一個解，同時所有形式為：

$a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}+kM=kM+\sum _{i=1}^{n}a_{i}t_{i}M_{i},\quad k\in \mathbb {Z}$

的整數也是方程組$(S)$的解。所以方程組$(S)$所有的解的集合就是：

$\{kM+\sum _{i=1}^{n}a_{i}t_{i}M_{i}\;;\quad k\in \mathbb {Z} \}.$

例子

使用中國剩餘定理來求解上面的「物不知數」問題，便可以理解《孫子歌訣》中的數字含義。這裡的線性同餘方程組是：

$(S):\quad \left\{{\begin{matrix}x\equiv 2{\pmod {3}}\\x\equiv 3{\pmod {5}}\\x\equiv 2{\pmod {7}}\end{matrix}}\right.$

三個模數 m₁$=$3, m₂$=$5, m₃$=$7 的乘積是 M$=$105，對應的 M₁$=$35, M₂$=$21, M₃$=$15. 而可以計算出相應的數論倒數：t₁$=$2, t₂$=$1, t₃$=$1. 所以《孫子歌訣》中的 70、21 和 15 其實是這個「物不知數」問題的基礎解：

$70=2\times 35\equiv \left\{{\begin{matrix}1{\pmod {3}}\\0{\pmod {5}}\\0{\pmod {7}}\end{matrix}},\right.21=1\times 21\equiv \left\{{\begin{matrix}0{\pmod {3}}\\1{\pmod {5}}\\0{\pmod {7}}\end{matrix}},\right.15=1\times 15\equiv \left\{{\begin{matrix}0{\pmod {3}}\\0{\pmod {5}}\\1{\pmod {7}}\end{matrix}},\right.$

而將原方程組中的餘數相應地乘到這三個基礎解上，再加起來，其和就是原方程組的解：

$2\times 70+3\times 21+2\times 15\equiv \left\{{\begin{matrix}2\times 1+3\times 0+2\times 0\equiv 2{\pmod {3}}\\2\times 0+3\times 1+2\times 0\equiv 3{\pmod {5}}\\2\times 0+3\times 0+2\times 1\equiv 2{\pmod {7}}\end{matrix}},\right.$

這個和是 233，實際上原方程組的通解公式為：

$x=233+k\times 105,\;k\in \mathbb {Z}$

《孫子算經》中實際上給出了最小正整數解，也就是 $k=-2$ 時的解：$x=23$。

交換環上的推廣

主理想整環

設R是一個主理想整環，m₁, m₂, ... , m_k是其中的k個元素，並且兩兩互質。令M$=$m₁m₂...m_n為這些元素的乘積，那麼可以定義一個從商環R/MR映射到環乘積R/m₁R × … × R/m_kR的同態：

$\phi :\;\;\mathrm {R} {\big /}M\mathrm {R} \longrightarrow \mathrm {R} {\big /}m_{1}\mathrm {R} \times \mathrm {R} {\big /}m_{2}\mathrm {R} \times \cdots \times \mathrm {R} {\big /}m_{k}\mathrm {R}$

$\left.\;\;x+M\mathrm {R} \;\mapsto \;(x+m_{1}\mathrm {R} ,x+m_{2}\mathrm {R} ,\cdots ,x+m_{k}\mathrm {R} )\right.$

並且$\phi$是一個環同構。因此$\phi$的逆映射也存在。而這個逆映射的構造方式就如同中國剩餘定理構造一元線性同餘方程組的解一樣。由於m_i和M_i$=$M/m_i互質，所以存在s_i和t_i使得

$s_{i}m_{i}+t_{i}M_{i}=1_{\mathrm {R} }.$

而映射

$\varphi :\;\;\mathrm {R} {\big /}m_{1}\mathrm {R} \times \mathrm {R} {\big /}m_{2}\mathrm {R} \times \cdots \times \mathrm {R} {\big /}m_{k}\mathrm {R} \longrightarrow \mathrm {R} {\big /}M\mathrm {R}$

$\left.\;(a_{1}+m_{1}\mathrm {R} ,a_{2}+m_{2}\mathrm {R} ,\cdots ,a_{k}+m_{k}\mathrm {R} )\;\mapsto \;\sum _{i=1}^{k}a_{i}t_{i}M_{i}+M\mathrm {R} \right.$

就是$\phi$的逆映射。

$\mathbb {Z}$也是一個主理想整環。將以上的R換成$\mathbb {Z}$，就能得到中國剩餘定理。因為

$a_{i}+m_{i}\mathrm {R} =\{x;\;x\;\equiv \;a_{i}{\pmod {m_{i}}}\}$

一般的交換環

設R是一個有單位元的交換環，I₁, I₂, ... , I_k是為環$\mathbf {R}$的理想，並且當$i\neq j$時，$I_{i}+I_{j}=\mathbf {R}$，則有典範的環同構：

$\psi :\;\;\mathbf {R} /(I_{1}\cap \cdots \cap I_{k})\longrightarrow \mathbf {R} /I_{1}\times \cdots \times \mathbf {R} /I_{k}$

$x+I_{1}\cap \cdots \cap I_{n}\longmapsto (x+I_{1},x+I_{2},\cdots ,x+I_{k}).$

模不兩兩互質的同餘式組

模不兩兩互質的同餘式組可化為模兩兩互質的同餘式組，再用孫子定理直接求解。

84=2²×3×7,160=2⁵×5,63=3²×7，由推廣的孫子定理可得 ${\begin{cases}x\equiv 23{\pmod {84}}\\x\equiv 7{\pmod {160}}\\x\equiv 2{\pmod {63}}\end{cases}}$ 與 ${\begin{cases}x\equiv 7{\pmod {2^{5}}}\\x\equiv 2{\pmod {3^{2}}}\\x\equiv 7{\pmod {5}}\\x\equiv 23{\pmod {7}}\end{cases}}$ 同解。

解法

${\begin{cases}x\equiv 7{\pmod {2^{5}}}\\x\equiv 2{\pmod {3^{2}}}\\x\equiv 7{\pmod {5}}\\x\equiv 23{\pmod {7}}\end{cases}}$ $\rightarrow$ ${\begin{cases}x\equiv 7{\pmod {2^{5}}}\\x\equiv 2{\pmod {3^{2}}}\\x\equiv 2{\pmod {5}}\\x\equiv 2{\pmod {7}}\end{cases}}$ $\rightarrow$ ${\begin{cases}x\equiv 7{\pmod {2^{5}}}\\x\equiv 2{\pmod {3^{2}\times 5\times 7}}\\\end{cases}}$

$2^{5}=32$以及$3^{2}\times 5\times 7=315$

$315a\equiv 1{\pmod {32}}\rightarrow (315-32\times 10)a\equiv 1{\pmod {32}}\rightarrow -5a\equiv 1{\pmod {32}}$，取數論倒數$a=-13$

$32b\equiv 1{\pmod {315}}\rightarrow 32b\equiv 1+315\times 13{\pmod {315}}\rightarrow 32b\equiv 4096{\pmod {315}}$，因$\gcd(32,315)=1$ ，故兩邊可同除以32， 取數論倒數$b={\frac {4096}{32}}=128$

$315\times (-13)\times 7+32\times 128\times 2=-20473$

$-20473\equiv 9767{\pmod {32\times 315}}$

所以最小正整數解為$9767$，通解為$x=9767+10080k,k\in \mathbb {Z}$。

注意求解過程中應先檢查同餘式組上是否存在矛盾，存在矛盾的同餘式組無解。

${\begin{cases}x\equiv 3{\pmod {6}}\\x\equiv 4{\pmod {10}}\\\end{cases}}\Rightarrow {\begin{cases}{\color {Red}x\equiv 1{\pmod {2}}}\\x\equiv 0{\pmod {3}}\\{\color {Red}x\equiv 0{\pmod {2}}}\\x\equiv 4{\pmod {5}}\\\end{cases}}$

參見

• 哈瑟原則

參考資料

參考書目

• 數學的100個基本問題，靳平 主編，ISBN 7-5377-2171-8