中国剩余定理

中国剩余定理（CRT）给出两两互素模数下同余方程组的统一解法。

定理

设 $m_1, m_2, \dots, m_k$ 两两互素，$M = m_1m_2\cdots m_k$。则同余方程组

$$x \equiv a_i \pmod{m_i}, \qquad i = 1,2,\dots,k$$

模 $M$ 有唯一解：

$$x \equiv \sum_{i=1}^{k} a_i M_i M_i^{-1} \pmod M$$

其中 $M_i = \dfrac{M}{m_i}$，$M_i^{-1}$ 是 $M_i$ 模 $m_i$ 的逆元（由Bezout 定理保证存在）。

示例

求满足 $x\equiv 1\pmod 3$，$x\equiv 2\pmod 5$，$x\equiv 3\pmod 7$ 的 $x$。

$M = 105$，$M_1 = 35 \equiv 2 \pmod 3$，$M_1^{-1} = 2$；$M_2 = 21 \equiv 1 \pmod 5$，$M_2^{-1} = 1$；$M_3 = 15 \equiv 1 \pmod 7$，$M_3^{-1} = 1$。于是

$$x \equiv 1\cdot 35\cdot 2 + 2\cdot 21\cdot 1 + 3\cdot 15\cdot 1 = 70 + 42 + 45 = 157 \equiv 52 \pmod{105}$$

最小正整数解为 $52$。这是"物不知数"（韩信点兵）问题的经典数值。