中国剩余定理

贡献者： int256

预备知识　线性同余

　　假设一组整数 $m_{1}, m_{2}, \dots, m_{k}$ 两两互素，则对于任意的一组整数 $a_{1}, a_{2}, \dots, a_{k}$ ，关于 $x$ 的同余方程组

\begin{matrix} (1) & {\begin{aligned} x & \equiv a_{1} (\mod m_{1}) \\ x & \equiv a_{2} (\mod m_{2}) \\ \dots \\ x & \equiv a_{k} (\mod m_{k}) \end{aligned} \end{matrix}

在模

m_{1} m_{2} \dots m_{k}

意义下有解且仅有一组同余解.

　　证明：设 $M = \prod_{i} m_{i}$ ，而令 $M_{l} = M / m_{l}$ 。由于 $m_{i}$ 间两两互素，故 $M_{l}$ 与 $m_{l}$ 互素，也就是 $(M_{l}, m_{l}) = 1$ ，利用定理 5 ，关于 $N_{l}$ 的同余方程

\begin{matrix} (2) & N_{l} M_{l} \equiv 1 (\mod m_{l}) \end{matrix}

将有且仅有一组同余意义下的解。利用各

N_{l}

与

M_{l}

可以构造出模

M

意义下的解，具体的，

\begin{matrix} (3) & x \equiv \sum_{i = 1}^{k} a_{i} \times M_{i} \times N_{i} (\mod M) . \end{matrix}