中国剩余定理

\(m_1, \dots, m_n\) 两两互素。考虑同余方程组 \[ \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots\\ x\equiv a_n \pmod {m_n} \end{cases} \] 令 \(M = m_1 m_2 \dots m_n\)。如果方程组有解，设 \(x_0\) 是一个解，那么不难证明，方程组解集是 \(\set{x_0 + kM : k\in \Z}\)。

如果 \(x_i\) 满足 \(x_i \equiv a_i \pmod{m_i}\)，\(x_i \equiv 0 \pmod{m_j}\)（\(j \ne i\)），那么 \(x_1 + x_2 + \dots + x_n\) 就是上述方程组的一个解。

令 \(M_i = \prod_{j \ne i} m_j\)，那么 \(x_i\) 可表为 \(kM_i\)。以 \(x = kM_i\) 代入 \(x\equiv a_i \pmod{m_i}\) 得 \[ kM_i \equiv a_i \pmod{m_i} \] 令 \(M_i^{-1}\) 为 \(M_i\) 在模 \(m_i\) 下的乘法逆元，对以上方程的两边同乘以 \(M_i^{-1}\) 得 \[ k \equiv a_i M_i^{-1} \pmod{m_i} \] 于是得到一个解 \[ x = \sum_{i} a_i M_i^{-1} M_i. \]