中国剩余定理
$\left\{\begin{matrix}x\equiv a_1\bmod m_1\\ x\equiv a_2\bmod m_2\\ … \\x\equiv a_n\bmod m_n\end{matrix}\right.$
其中$m_i$两两互质
$M=\prod_{i=0}^{n}m_i, M_i=\frac{M}{m_i}$
$x=\sum_{i=0}^{n}a_i M_i M_i^{-1}\pmod {m_i}$
扩展中国剩余定理
模数不互质的时候
$x\equiv a_1\bmod m_1$
$x\equiv a_2\bmod m_2$
也就是
$x=k_1m_1+a_1=k_2m_2+a_2$
$\therefore k_1m_1=(a_2-a_1)+k_2m_2$
即$k_1m_2\equiv (a_2-a_1)\bmod m_2$
让$d=(m_1,m_2)$
即$k_1\frac{m_1}{d}\equiv \frac{(a_2-a_1)}{d}\bmod {\frac{m_2}{d}}$
这样就可以得到$k_1=k’\frac{m_2}{d}+\frac{a_2-a_1}{d}(\frac{m_1}{d})^{-1}\pmod {\frac{m_2}{d}}$
令$t=\frac{a_2-a_1}{d}(\frac{m_1}{d})^{-1}\pmod {\frac{m_2}{d}}$
带回原式得$x=(k’\frac{m_2}{d}+t)m_1+a_1$
即可并成$x=k’\frac{m_1m_2}{d}+tm_1+a_1$
即$x\equiv a\bmod m$，其中$a=tm_1+a_1, m=\frac{m_1m_2}{d}$
