中国剩余定理¶
中国剩余定理（Chinese remainder theorem）说明了一元线性同余方程组有解的准则以及求解方法。
\[ \left\{\begin{matrix} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_n \pmod{m_n} \end{matrix}\right. \]
有解条件¶
如果模数 \(m_1,m_2,\dots,m_n\) 两两互质，则对任意整数 \(a_1,a_2,\dots,a_n\) 原方程组有解。
求解方法¶
设 \(M=\displaystyle\prod_{i=1}^{n}m_i\)，\(M_i=\dfrac{M}{m_i}\)，方程组的通解为
\[ x=kM+\sum_{i=1}^n a_i M_i M_i^{-1}, k \in \mathbb{Z} \]
\(M_i^{-1}\) 是 \(M_i\) 模 \(m_i\) 的逆元。在模 \(M\) 意义下，方程组的唯一解是
\[ x=\sum_{i=1}^n a_i M_i M_i^{-1} \]
证明¶
因为 \(m_1,m_2,\dots,m_n\) 两两互质，所以 \(m_i\) 和 \(M_i\) 互质，存在逆元 \(M_i^{-1}\) 使得
\[ M_i M_i^{-1} \equiv 1 \pmod{m_i} \]
取任意 \(i,j \in \{1,2,\dots,n\}\)，若 \(i=j\) 则
\[ a_i M_i M_i^{-1} \equiv a_i \cdot 1 \equiv a_i \pmod{m_j} \tag{1} \]
若 \(i \ne j\) 则 \(m_j \mid M_i\) 因此
\[ a_i M_i M_i^{-1} \equiv 0 \pmod{m_j} \tag{2} \]
综合 \((1)(2)\) 可知
\[ x=\sum_{i=1}^n a_i M_i M_i^{-1} \]
是原方程组的一个解。
假设 \(x_1,x_2\) 都是原方程组的解，那么 \(\forall i \in \{1,2,\dots,n\}\) 有
\[ (x_1 - x_2) \equiv 0 \pmod{m_i} \]
即 \(m_i \mid (x_1-x_2)\)，又因为 \(m_1,m_2,\dots,m_n\) 两两互质，根据整除的性质
\[ M \mid (x_1-x_2) \]
所以，方程组的任意两个解相差 \(M\) 的整数倍，通解为
\[ x=kM+\sum_{i=1}^n a_i M_i M_i^{-1}, k \in \mathbb{Z} \]