这篇文档主要介绍中国剩余定理及其证明过程。
定理描述
首先介绍同余方程：如果两个整数a和b被正整数m所除的余数相同，则称a和b对模m同余，记作$a \equiv b \ (mod\ \ m)$。同余方程组是由多个同余方程组成的方程组。
接着再介绍数论倒数：给定两个整数$a$和$m$，如果存在一个整数$b$，使得$a \times b \equiv 1 \ (mod \ \ m)$，则称$b$是$a$对模$m$的数论倒数。并非所有的整数都存在数论倒数，只有当$a$与$m$互质时，$a$对模$m$的数论倒数才存在。
中国剩余定理是数论中一个关于一元线性同余方程组的定理，一元线性同余方程组问题最早可以见于中国南北朝时期的数学著作《孙子算经》，因此也被称之为孙子定理，它的数学描述如下所示：
$$ S=\begin{cases} x \equiv a_1 \pmod{m_1}\ x \equiv a_2 \pmod{m_2}\ …\ x \equiv a_n \pmod{m_n} \end{cases} $$
其中，若$m_i \ (1 \le i \le n)$两两互质，则对任意的整数$a_i \ (1 \le i \le n)$方程组$S$有解，该通解形式为：
$$ x=kM + \sum_{i=1}^{n}a_it_iM_i $$
其中，$k \in \mathbb{Z}$，$M$是$m_i$的乘积，$M_i=M/m_i$，$t_i$是$M_i$对$m_i$的数论倒数。
定理证明
对于$i \ (1 \le i \le n)$以及$j \ (1 \le j \le n)$，$i \neq j$，$m_i$与$m_j$互质，则$m_i$与$M_i$互质。存在$t_i$使得$t_iM_i \equiv 1 \ (mod\ \ m_i)$，则$a_it_iM_i \equiv a_i \ (mod\ \ m_i)$。而对于$j \neq i$，$a_jt_jM_j \equiv 0 \ (mod\ \ m_i)$。因此有：
$$ x=\sum_{i=1}^{n}a_it_iM_i $$
假设存在同余方程组存在两个解$x_1$和$x_2$，则$x_1-x_2 \equiv 0 \ (mod\ \ m_i)$，因为$m_i$之间彼此互质，且$M$可以整除$x_1-x_2$，因此$x_1$和$x_2$之间相差$M$的整数倍。则全部的通解形式为：
$$ x=kM + \sum_{i=1}^{n}a_it_iM_i $$