前置知识
同余，逆元等数论基础。
引入
我们来看这样一个问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？——《孙子算经》
即： \[ \left\{ \begin{aligned} x&\equiv 2\pmod {3}\\ x&\equiv 3\pmod {5}\\ x&\equiv 2\pmod {7} \end{aligned} \right.\tag{1.0} \]
求解
先以古人的问题为例吧。
我们先解下面三个特殊的同余方程组：
\[ \left\{ \begin{aligned} x&\equiv 1\pmod {3}\\ x&\equiv 0\pmod {5}\\ x&\equiv 0\pmod {7} \end{aligned} \right.\tag{1.1} \] \[ \left\{ \begin{aligned} x&\equiv 0\pmod {3}\\ x&\equiv 1\pmod {5}\\ x&\equiv 0\pmod {7} \end{aligned} \right.\tag{1.2} \] \[ \left\{ \begin{aligned} x&\equiv 0\pmod {3}\\ x&\equiv 0\pmod {5}\\ x&\equiv 1\pmod {7} \end{aligned} \right.\tag{1.3} \]
以方程 \((1.1)\) 为对象，相当于解一个这样的同余方程：\(35y\equiv1\pmod3\)。
为什么呢？原因是从 \((1.1)\) 的模数及条件知道 \(x\) 应该是 \(5\times7=35\) 的倍数，这样才能同余 \(0\)。于是可以假设 \(x=35y\)，有 \(35y\equiv1\pmod3\)，相当于 \(2y\equiv1\pmod3\)，解出 \(y=2\pmod3\)，于是 \(x\equiv35\times2\equiv70\pmod{105}\)。
同样的方法可以解出：
\(x\equiv21\times1\equiv21\pmod{105}\) 和 \(x\equiv15\times1\equiv15\pmod{105}\)。
所以，
\((1.0)=2(1.1)+3(1.2)+2(1.3)=2\times70+3\times21+2\times15\equiv23\pmod{105}\)
中国剩余定理
中国剩余定理可以求解以下线性同余方程组： \[ \left\{ \begin{aligned} x&\equiv a_1\pmod {n_1}\\ x&\equiv a_2\pmod {n_2}\\ &\vdots\\ x&\equiv a_k\pmod {n_k} \end{aligned} \right. \] 其中 \(n_1\)，\(n_2\)，\(\cdots\)，\(n_k\) 两两互质。