什么是中国剩余定理

更新日期：2026-09-18 01:34:39

标题

什么是中国剩余定理

内容

中国剩余定理（The Chinese Remainder Theorem，简称CRT）是数论中一个重要的定理，最早由中国古代数学家提出，用于解决同余方程组的问题。它在现代数学、密码学、计算机科学等领域有着广泛的应用。

一、中国剩余定理概述

中国剩余定理的核心思想是：如果一组模数两两互质，那么对于任意给定的余数，存在唯一解满足所有同余条件。简单来说，就是“已知一个数被多个不同的数除后的余数，求这个数”。

例如，已知一个数被3除余2，被5除余3，被7除余2，那么这个数是多少？

二、中国剩余定理的基本形式

设 $ m_1, m_2, \dots, m_k $ 是两两互质的正整数，$ a_1, a_2, \dots, a_k $ 是任意整数，则以下同余方程组：

\begin{cases}

x \equiv a_1 \pmod{m_1} \\

x \equiv a_2 \pmod{m_2} \\

\vdots \\

x \equiv a_k \pmod{m_k}

\end{cases}

有唯一解模 $ M = m_1 \cdot m_2 \cdot \dots \cdot m_k $。

三、中国剩余定理的应用

四、中国剩余定理的求解方法

1. 确定模数互质：确保所有模数两两互质。

2. 计算总模数：$ M = m_1 \cdot m_2 \cdot \dots \cdot m_k $

3. 计算每个模数的补数：$ M_i = \frac{M}{m_i} $

4. 求逆元：找到 $ M_i^{-1} \mod m_i $

5. 构造解：$ x = \sum_{i=1}^{k} a_i \cdot M_i \cdot M_i^{-1} \mod M $

五、例子解析

假设我们有以下同余方程组：

\begin{cases}

x \equiv 2 \pmod{3} \\

x \equiv 3 \pmod{5} \\

x \equiv 2 \pmod{7}

\end{cases}

- 模数：3、5、7，两两互质

- 总模数：$ M = 3 \times 5 \times 7 = 105 $

- $ M_1 = 35 $, $ M_2 = 21 $, $ M_3 = 15 $

- 求逆元：

- $ 35^{-1} \mod 3 = 2 $

- $ 21^{-1} \mod 5 = 1 $

- $ 15^{-1} \mod 7 = 1 $

- 解为：$ x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233 \mod 105 = 23 $

所以，满足条件的最小正整数是 23。

六、总结

通过理解中国剩余定理，我们可以更高效地处理涉及多个模数的同余问题，这在实际应用中具有非常重要的意义。

随便看