中国剩余定理

简单介绍中国剩余定理 对于同余方程组:

\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,故公式解正确

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注