【学习笔记】中国剩余定理

中国剩余定理可以求解同余方程组： $$x\equiv a_1(\mod m_1)$$ $$x \equiv a_2(\mod m_2)$$ $$x \equiv a_3(\mod m_3)$$ $$\cdots$$ $$x \equiv a_k(\mod k)$$ 令$M=\prod_{i=1}^{k}m_i$，令$M_i=\frac{M}{m_i}$，$M_i^{-1}$为$M_i$在模$m_i$意义下的逆元，则解为： $$x\equiv \sum_{i=1}^k (a_iM_iM_i^{-1})(\mod M)$$ **证明：** 设$n_i \mod m_i = a_i$，那么如果： $$\sum_{j=1}^kn_j-n_i \equiv0(\mod m_i)$$ $$\therefore \sum_{j=1}^kn_j\equiv a_i(\mod m_i)$$ 同理可推知所有$n_i$的情况。又因为： $$(a\times k)\mod b=(a\mod b)\times k$$ 而对于每个$n_i$，其需要满足是$m_1,m_2,\cdots,m_{i-1},m_{i+1},\cdots,m_k$的**公倍数**，并且$n_i\mod m_i=a_i$，该问题可以简化为在公倍数中找到一个满足$N\mod m_i=1$的数$N$，再把这个数乘$a_i$，可得到满足条件的$n_i$，即$N\times a_i=n_i$。进一步简化问题，寻找$N\mod m_i=1$时，很明显$N=M\times M^{-1}(\mod m_i)$。则可知： $$n_i=a_iM_iM_i^{-1}$$ 而$x$需要满足**所有**$n_i$满足的条件，因此最小整数解$x$满足： $$x\equiv \sum_{i=1}^kn_i(\mod M)$$ --- **参考资料** [CSDN](https://www.cnblogs.com/MashiroSky/p/5918158.html )