中国剩余定理
贡献者： int256
定理 1 中国剩余定理
假设一组整数 $m_1, m_2, \dots, m_k$ 两两互素，则对于任意的一组整数 $a_1, a_2, \dots, a_k$，关于 $x$ 的同余方程组
\begin{equation}\left\{
\begin{aligned}
x &\equiv a_1 \pmod{m_1} \\
x &\equiv a_2 \pmod{m_2} \\
\dots \\
x &\equiv a_k \pmod{m_k}
\end{aligned}\right. ~~
\end{equation}
在模 $m_1m_2\dots m_k$ 意义下有解且仅有一组同余解.
证明：设 $M = \prod_i m_i$，而令 $M_l = M / m_l$。由于 $m_i$ 间两两互素，故 $M_l$ 与 $m_l$ 互素，也就是 $(M_l, m_l) = 1$，利用定理 5 ，关于 $N_l$ 的同余方程
\begin{equation}
N_l M_l \equiv 1 \pmod{m_l} ~~
\end{equation}
将有且仅有一组同余意义下的解。利用各 $N_l$ 与 $M_l$ 可以构造出模 $M$ 意义下的解，具体的，
\begin{equation}
x \equiv \sum_{i=1}^k a_i \times M_i \times N_i \pmod{M} ~.
\end{equation}