免费中国剩余定理计算器

理解中国剩余定理

中国剩余定理（CRT）是数论中的一个基本结论，它可以求解一个同余方程组——即在给定模数下指定未知整数余数的方程。当模数两两互质时，该定理保证存在一个唯一解（模这些模数的乘积）。这个CRT计算器提供了一种快速、可靠的方式来在线求解这样的系统，使模运算变得简单，无论是学习数论、准备竞赛还是处理加密算法。

模运算与同余

在深入了解定理之前，有必要回顾一下余数的概念。当一个整数$a$被一个正整数$b$除时，余数$r$是满足以下条件的整数（介于0和$b-1$之间）：

$$a = k \cdot b + r$$

对于某个整数$k$。例如，17除以5得到$17 = 3 \cdot 5 + 2$，所以余数是2。

模运算建立在这个概念之上。我们说两个数$a$和$b$在模$n$下同余，记为$a \equiv b \pmod{n}$，当它们除以$n$时具有相同的余数。这样的表达式称为同余式。它们的行为类似于普通方程：你可以对两边加上、减去或乘以任意整数（但除法需要小心）。这个简单的性质使同余式成为处理整数的有力工具。

用于GCD的欧几里得算法

欧几里得算法是一种高效求两个整数最大公约数的方法。给定两个数$x$和$y$且$x > y$，算法进行如下：

1. 设$a_1 = x$，$b_1 = y$，且$n = 1$。
2. 确定整数$k_n$为$b_n$的最大倍数，使其不超过$a_n$（即$a_n / b_n$的向下取整）。
3. 计算余数$r_n = a_n - k_n \cdot b_n$。
4. 如果$r_n = 0$，算法停止且$b_n = \gcd(x,y)$。否则，设$a_{n+1} = b_n$，$b_{n+1} = r_n$，将$n$增加1，并从步骤2重复。

每一步都有$a_n = k_n \cdot b_n + r_n$。例如，求 gcd(1785, 546)：

n	a_n	k_n	b_n	r_n
1	1785	3	546	147
2	546	3	147	105
3	147	1	105	42
4	105	2	42	21
5	42	2	21	0

因为$r_5 = 0$，所以$\gcd(1785, 546) = b_5 = 21$。

贝祖引理

贝祖引理（Bézout's identity）指出，对于任意非零整数$a$和$b$，存在整数$k$和$l$使得：

$$k \cdot a + l \cdot b = \gcd(a,b).$$

这些系数可以通过逆推欧几里得算法步骤来求得。继续使用$a = 1785$和$b = 546$（gcd=21），我们通过等式反向代入：

$$\begin{aligned} 21 &= 105 - 2 \cdot 42 \\ 42 &= 147 - 1 \cdot 105 \\ 105 &= 546 - 3 \cdot 147 \\ 147 &= 1785 - 3 \cdot 546 \end{aligned}$$

逐步替换得到：

$$21 = -11 \cdot 1785 + 36 \cdot 546,$$

因此一个有效解是$k = -11$、$l = 36$。注意系数不一定为正，只需是满足等式的整数即可。

中国剩余定理：陈述与算法

中国剩余定理将同余式、欧几里得算法和贝祖引理融为一体。其正式陈述为：

设$n_1, n_2, \dots, n_k$是两两互质的正整数（即当$i \neq j$时，$\gcd(n_i, n_j) = 1$）。那么对于任意整数$a_1, a_2, \dots, a_k$，同余方程组

$$\begin{cases} x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \quad \vdots \\ x \equiv a_k \pmod{n_k} \end{cases}$$

在模$N = n_1 n_2 \cdots n_k$下有唯一解。

通俗地说：如果你知道一个未知数被几个互质模数除后的余数，你就可以唯一地确定该数（最多加上模数乘积的整数倍）。

要解这样的方程组，按以下步骤操作：

1. 计算乘积 $N = n_1 n_2 \cdots n_k$。
2. 对于每个模数$n_i$，设$m_i = N / n_i$。
3. 使用贝祖引理找到整数$v_i$和$u_i$，使得$u_i n_i + v_i m_i = 1$。$v_i$即为$m_i$模$n_i$的乘法逆元。
4. 定义$e_i = v_i m_i$。注意到$e_i \equiv 1 \pmod{n_i}$，且当$j \neq i$时，$e_i \equiv 0 \pmod{n_j}$。
5. 一个特解为$x_0 = a_1 e_1 + a_2 e_2 + \cdots + a_k e_k$。通解为$x \equiv x_0 \pmod{N}$。

虽然算法很直接，但手动计算逆元可能很繁琐。这正是在线CRT求解器发挥作用的地方。

使用计算器的示例

考虑一个经典的糖果分配问题。一位妈妈有一把糖果。当她平均分给三个孩子时，还剩下一颗。如果她再给邻居的女孩一颗（总共四个孩子），则会剩下两颗。再邀请女孩的哥哥（总共五个孩子）时剩下三颗。她买了多少颗糖果？

设$x$为糖果数。条件转化为方程组：

$$\begin{aligned} x &\equiv 1 \pmod{3} \\ x &\equiv 2 \pmod{4} \\ x &\equiv 3 \pmod{5} \end{aligned}$$

模数3、4、5两两互质，所以CRT适用。使用算法：

• $N = 3 \cdot 4 \cdot 5 = 60$
• $m_1 = 60/3 = 20$，$m_2 = 60/4 = 15$，$m_3 = 60/5 = 12$
• 通过欧几里得算法求逆：
  • 对于(3,20)：$20 \equiv 2 \pmod{3}$，20模3的逆元$v_1 = -1$，因为$(-1)\cdot 20 \equiv 1 \pmod{3}$ → $e_1 = (-1)\cdot 20 = -20$
  • 对于(4,15)：15模4的逆元为$-1$ → $e_2 = -15$
  • 对于(5,12)：12模5的逆元为$-2$ → $e_3 = -24$
• 计算$x_0 = 1\cdot(-20) + 2\cdot(-15) + 3\cdot(-24) = -122$
• 最小的非负解为$x \equiv -122 \equiv 58 \pmod{60}$。

所以妈妈买了58颗糖果。使用中国剩余定理计算器可以立刻得到这个结果——只需输入三个同余式，工具就会返回最小的正解。

为什么使用这个CRT求解器？

• 速度：避免手动回代和逆元计算。
• 准确性：消除处理较大模数时的算术错误。
• 灵活性：适用于任意数量的同余式（只要模数互质）。
• 教育性：算法步骤清晰解释，是学习模运算、同余方程组和数论的宝贵辅助工具。

无论你是学生还是从事依赖CRT的加密协议的专业人员，这个工具都能简化求解过程，让你专注于应用结果。