中国剩余定理（CRT）
求同余方程组\(\left\{\begin{aligned}x\equiv a_1(\mod m_1)\\x\equiv a_2(\mod m_2)\\\cdots\\x\equiv a_n(\mod m_n) \end{aligned} \right.\)的解，满足 \(m_1,m_2,\cdots,m_n\)两两互质。
\[设M=\prod_{i=1}^n m_i,Mi=\frac M {m_i},t_i是线性同余方程M_it_i\equiv 1(\mod M_i)的一个解，\\
先求M_it_i\equiv 1(\mod m_i)，即M_i的逆元，再将两边同时乘a_i，得a_iM_it_i\equiv a_i(\mod m_i)\\
\therefore 解为a_it_iM_i，方程组的解为\sum_{i=1}^na_it_iM_i
\]
exCRT