注：本节内容为《具体数学》(原书第二版) 第四章 数论 习题 4.30 的答案。但是可以独立阅读。

中国剩余定理

定理的本质就是对一组线性同余方程组求解。

证明与构造

我们不妨写成一个更简单的形式：

对于如下线性同余方程组：

$$
x \equiv a_1 \pmod {m_1}
$$

$$
x \equiv a_2 \pmod {m_2}
$$

$$
\cdots
$$

$$
x \equiv a_n \pmod {m_n}
$$

其中，对于 $1 \leq j < k \leq n$ 都有 $m_j \perp m_k$，且 $m = m_1m_2\cdots m_n$。那么，我们总找得到整数 $x$ 使得对于任意整数 $A$ 都有上述同余方程组成立，且 $A \leq x < A + m$。

也就是说，在上述同余线性方程组成立时，总找得到 $x$，使得对于任意 $A$ 都有

$$
x \equiv A \pmod m
$$

成立。

解：

这个定理的核心在于构造。我们有能力构造出一个式子，使得每一项都对应每一个方程，使之成立。

令

$$
x \equiv t_1 + t_2 + \cdots t_n \pmod m
$$

对于 $1 \leq k \leq n$，我们想要构造 $t_k$ 使得

$$
t_k \equiv a_k \pmod {m_k}
$$

$$
t_k \equiv 0 \pmod {m_j}, j \neq k
$$

因为这样的话我们就能推得：

$$
\begin{aligned}
x & \equiv t_1 + t_2 + \cdots t_n \pmod m \\
\Rightarrow x & \equiv t_1 + t_2 + \cdots t_n \pmod {m_k} \\
& \equiv t_k \\
& \equiv a_k \pmod {m_k}
\end{aligned}
$$

即，能让每个式子都成立。

接下来，我们给出 $t_k$ 的构造：

$$
t_k = a_k M_k M_k ^ {-1}
$$

其中

$$
M_k = \frac {\prod_{j=1}^n m_j} {m_k}
$$

$M_k^{-1}$ 为 $M_k$ 对于 $m_k$ 的逆元。即

$$
M_k^{-1} M_k \equiv 1 \pmod {m_k}
$$

根据题设，不难看出 $M_k \perp m_k$，所以根据裴蜀定理，我们一定能通过扩展欧几里得算法找到 $M_k$ 对于 $m_k$ 的逆元。

我们可以发现，我们给出的 $t_k$ 的构造可以完美的满足所有的线性同余方程组。

$$
A = \sum_{k=1}^n a_kM_kM_k^{-1} \pmod {m}
$$