附录11 - 中国剩余定理

假设有 $k$ 个正整数 $m_1, m_2, \dots, m_k$，它们两两互素（即任意两个数的最大公约数都是 1，$\gcd(m_i, m_j) = 1$）。
给定任意 $k$ 个整数 $a_1, a_2, \dots, a_k$。

中国剩余定理断言：以下同余方程组必定存在解，并且在模 $M = m_1 m_2 \dots m_k$ 的意义下，解是唯一的：

$x \equiv a_1 \pmod{m_1}$

$x \equiv a_2 \pmod{m_2}$

$\vdots$

$x \equiv a_k \pmod{m_k}$

这意味着，在 $1$ 到 $M$ 的范围内，有且仅有一个 $x$ 能够同时满足上述所有的余数条件。

第一步：计算总乘积
令 $M = m_1 m_2 \dots m_k$。

第二步：计算基础“积木”
对于每一个 $i$（从 $1$ 到 $k$），定义 $M_i = \frac{M}{m_i}$。
（也就是说，$M_i$ 是除了 $m_i$ 以外，其他所有模数的乘积）。
显然，$M_i$ 能够被其他所有模数整除，所以 $M_i \equiv 0 \pmod{m_j}$（当 $j \neq i$ 时）。

第三步：求逆元（裴蜀定理的登场）
因为 $m_1, \dots, m_k$ 两两互素，所以 $M_i$ 和 $m_i$ 也是互素的。
根据裴蜀定理，必定存在一个整数 $t_i$，使得：

$M_i t_i \equiv 1 \pmod{m_i}$

这个 $t_i$ 被称为 $M_i$ 在模 $m_i$ 下的乘法逆元。

第四步：组合出最终答案
我们将所有的部件组合起来，最终的解 $x$ 的通式为：

$x = \sum_{i=1}^k a_i M_i t_i$

为什么这个式子是对的？
我们随便挑一个模数 $m_1$ 来检验：

• 当 $i = 1$ 时，那一项是 $a_1 M_1 t_1$。因为 $M_1 t_1 \equiv 1 \pmod{m_1}$，所以这一项模 $m_1$ 的结果就是 $a_1 \cdot 1 = a_1$。
• 当 $i \neq 1$（比如 $i = 2, 3 \dots$）时，那一项是 $a_i M_i t_i$。因为 $M_i$ 里面包含了因子 $m_1$，所以 $M_i \equiv 0 \pmod{m_1}$，这一整项模 $m_1$ 的结果就是 0。
• 所有的项加起来模 $m_1$，结果恰好就是 $a_1 + 0 + 0 \dots = a_1$。

这完美满足了方程组的要求！

第五步：证明唯一性
第四步中我们证明了任何一组 $a_1, a_2, \cdots, a_k$ 组合都能找到一个 $x \in \{1, \cdots, M\}$
这样的 ${a_i}$ 的组合一共有 $M$ 个，而 $x$ 可取的范围也只有 $M$ 个数，根据抽屉原理，不可能有两个不同 $x_i, x_j$ 对应同一组${a_i}$，这就证明了解的唯一性。

回顾「附录10」中证明欧拉函数积性的方法二中用的构造方法：

寻找整数 $u, v$，使得
$mu + nv = 1$
$x = (a \cdot nv + b \cdot mu) \bmod mn$

这里，我们要求 $x \equiv a \pmod m$ 且 $x \equiv b \pmod n$。
对应到上面的构造法：
$m_1 = m, m_2 = n$，
$M_1 = n, M_2 = m$，
$n$ 在模 $m$ 下的逆元是 $v$，$m$ 在模 $n$ 下的逆元是 $u$（这正是裴蜀定理 $mu + nv = 1$ 的直接推论）。
所以我们构造出的
$x = a \cdot n \cdot v + b \cdot m \cdot u$
这完全就是中国剩余定理在 $k=2$ 时的标准构造公式！