简单介绍中国剩余定理 对于同余方程组:
\begin{cases}
& x \equiv a_1 \quad (mod \quad m_1)\\
& x \equiv a_2 \quad (mod \quad m_2)\\
& \cdot \cdot \cdot \\
& x \equiv a_i \quad (mod \quad m_i)
\end{cases}
规定约束:m_i
之间两两互质则x有公式解,只需令
M=\prod m_i, M_i=\frac{M}{m_i}\\
M_i^{-1}为M_imod \quad m_i的逆
则
x=(\sum M_i^{-1}M_ia_i )mod \quad M
一个简要的验证: 对于x求和的任意第i项
M_i^{-1}M_ia_i \\ M_i^{-1}为M_imod \quad m_i的逆
其中的因子M_i
包含除m_i
以外的所有m,所以除m_k, k \ne i
的余数都是零 并且由乘法逆元定义可知,该项mod m_i
的余数是a_i
即,x由i项求和组成,每一项都对方程组中第i个方程负责,而对第i个方程负责时,其他项都为0,故公式解正确