中国剩余定理

中國剩餘定理，又稱孫子定理或中國餘數定理，是数论中的一個关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。该定理在中国古代也被称为「韓信點兵」、「求一术」（宋 沈括）、「鬼谷算」（宋 周密）、「隔墻算」（宋 周密）、「剪管術」（宋 杨辉）、「秦王暗點兵」、「物不知數」等。

物不知数

一元线性同余方程组问题最早可见于中國南北朝时期（公元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