中国剩余定理

中国剩余定理(chinese remainder theorem)

若整数\(m_1,m_2,\cdots,m_n\)两两互质,且\(M=m_1m_2\cdots m_n\),那么对于任意整数\(a_1,a_2,\cdots,a_n\),关于\(x\)的同余方程组

\[\begin{cases} x\equiv a_1\,mod\,m_1\\ x\equiv a_2\,mod\,m_2\\ \vdots\\ x\equiv a_n\,mod\,m_n\\ \end{cases} \]

有模\(M\)的唯一解:
令\(M_i=M/m_i\),\(M_i^{-1}\)为其模\(m_i\)的逆元,即\(M_i^{-1}M_i\equiv 1\,mod\,m_i\),那么同余方程组的通解为:

\[x\equiv \left(\sum_{i=1}^{n}{a_iM_i^{-1}M_i}\right)\,mod\,M \]

上一篇:题解 P2455 【[SDOI2006]线性方程组】


下一篇:二次型求偏导