中国剩余定理

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
——《孙子算经》

中国剩余定理

中国剩余定理(CRT, Chinese remainder theorem)，又称孙子定理，是一种求解一次同余方程组的方法。

问题形式

用式子来描述，CRT是用来解下列方程组的。
其中，$m_i$两两互质。

$$\begin{cases} x& \equiv \\ a_1 \\ ( \\ mod \\ m_1 \\ ) \\\\ x& \equiv \\ a_2 \\ ( \\ mod \\ m_2 \\ ) \\\\ &\cdots \\\\ x& \equiv \\ a_n \\ ( \\ mod \\ m_n \\ ) \\\\ \end{cases}$$

推导

首先，定义：

$$M = \Pi \\ m_i \\\\ M_i = \frac{M}{m_i}$$

$\because \quad m_i$ 两两互质
$\therefore \quad M_i \ u_i + m_i \ v_i = 1$ 有整数解
$\therefore \quad M_i \ u_i \equiv 1 \ ( \ mod \ m_i )$
$\therefore \quad u_i$是$M_i$在模$m_i$意义下的逆元
同余式左右同乘$a_i$，得
$a_i \ M_i \ u_i \equiv a_i \ ( \ mod \ m_i )$
$\therefore \quad x \equiv a_i \ M_i \ u_i \ ( \ mod \ m_i )$
得到结论：

$$x \equiv \sum_{i=1}^{n} {a_i \\ M_i \\ u_i} \\ ( \\ mod \\ M \\ )$$