中国剩余定理（CRT）（待完善）

标签：剩余 CRT 定理 cdots iM equiv mod

中国剩余定理（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

标签：剩余,CRT,定理,cdots,iM,equiv,mod
From： https://www.cnblogs.com/lyz09-blog/p/prove-CRT.html