中国剩余定理

设 (m_1), (m_2), (m_3) (ldots) , (m_k) 两两互质，求 x 满足

(left { egin{array}\ {x equiv a_1 pmod {m_1}}\ {x equiv a_2 pmod {m_2}}\ {x equiv a_3 pmod {m_3}}\ {ldots}\ {x equiv a_k pmod {m_k}}\ end{array} ight.)

设 (M = m_1m_2m_3 ldots m_k)，则

(M_i = frac{M}{m_i})，

({M_i}^{-1}) 表示 (M_i) 模 (m_i) 的逆，

那么，(x = a_1 cdot M_1 cdot {M_1}^{-1} + a_2 cdot M_2 cdot {M_2}^{-1} + a_3 cdot M_3 cdot {M_3}^{-1} + ldots + a_k cdot M_k cdot {M_k}^{-1})