中国剩余定理

贡献者： int256

预备知识　线性同余

定理 1　中国剩余定理

　　假设一组整数 $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}

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

中国剩余定理

定理 1 中国剩余定理

定理 1　中国剩余定理