To boldly go where no one has gone before.

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

2019-04-01 23:25:09


中国剩余定理可以求解同余方程组:$$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