中国剩余定理

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

物不知数
一元线性同余方程组问题最早可见于中國南北朝时期（公元5世纪）的数学著作《孫子算經》卷下第二十六题，叫做“物不知數”问题，原文如下：

即，一個整數除以三-{zh-cn:余;zh-tw:餘;}-二，除以五-{zh-cn:余;zh-tw:餘;}-三，除以七-{zh-cn:余;zh-tw:餘;}-二，求這個整數。《孫子算經》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。孫子沒正式證明，但後來印度數學家及天文學家阿耶波多給出具體過程，徹底解決了此定理的任何給定實例。

最初对“物不知数”问题作出完整系统解答的是宋朝数学家秦九韶，载于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.
有解的判定条件，并用构造法给出了在有解情况下解的具体形式。

中国剩余定理说明：假设整数其中任两數互质，则对任意的整数：，方程组(S)有解，并且通解可以用如下方式构造得到：
#设M = m_1 \times m_2 \times \cdots \times m_n = \prod_{i=1}^n m_i是整数的乘积，并设M_i = M/m_i, \; \; \forall i \in \{1, 2, \cdots , n\}，即M_i是除了m_i以外的n-1个整数的乘积。
#设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\}.
#方程组(S)的通解形式为：x = a_1 t_1 M_1 + a_2 t_2 M_2 + \cdots + a_n t_n M_n + k M= k M + \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 + k M= k M + \sum_{i=1}^n a_i t_i M_i, \quad k \in \mathbb{Z}
的整数也是方程组(S)的解。所以方程组(S)所有的解的集合就是：
:\{k M + \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.
三个模数 =3, =5, =7 的乘积是 =105，对应的 =35, =21, =15. 而可以计算出相应的数论倒数：=2, =1, =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。

交换环上的推广
主理想整环
设是一个主理想整环，是其中的个元素，并且两两互质。令=为这些元素的乘积，那么可以定义一个从商环映射到环乘积的同态：
:\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的逆映射也存在。而这个逆映射的构造方式就如同中国剩余定理构造一元线性同余方程组的解一样。由于和=互质，所以存在和使得
: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}也是一个主理想整环。将以上的换成\mathbb{Z}，就能得到中国剩余定理。因为
:a_i + m_i \mathrm{R} = \{x ; \; x \; \equiv \; a_i \pmod{m_i} \}
一般的交换环
设是一个有单位元的交换环，是为环\mathbf{R}的理想，并且当i \ne 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=22×3×7,160=25×5,63=32×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 2 \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