中国剩余定理计算器

欢迎使用中国剩余定理计算器，这是一个强大的数论工具，使用中国剩余定理 (CRT) 求解线性同余方程组。无论您是在学习模运算、准备数学竞赛、处理密码学问题，还是在探索数论，此计算器都能提供完整的逐步解决方案，并配有显示同余类如何在唯一解处对齐的交互式可视化界面。

什么是中国剩余定理？

中国剩余定理 (CRT) 是数论中的一个基本结果，它保证了在模数两两互质的情况下，同余方程组解的存在性和唯一性。该定理最早由中国数学家孙子在其约公元 3 世纪的著作《孙子算经》中描述。

形式上，给定方程组：

如果所有模数 \(m_1, m_2, \ldots, m_k\) 均两两互质（即对于所有 \(i \neq j\)，\(\gcd(m_i, m_j) = 1\)），则在模 \(M = m_1 \times m_2 \times \cdots \times m_k\) 下存在唯一解 \(x\)。

CRT 算法的工作原理

构造性证明提供了此计算器使用的算法：

步骤 1：计算 M

计算所有模数的乘积：

步骤 2：计算每个 Mᵢ

对于每个同余式 \(i\)，计算 \(M_i = M / m_i\)。这是除 \(m_i\) 之外所有模数的乘积。

步骤 3：寻找模逆元

对于每个 \(i\)，使用扩展欧几里得算法寻找 \(y_i\)，使得 \(M_i \cdot y_i \equiv 1 \pmod{m_i}\)。由于 \(M_i\) 和 \(m_i\) 互质（所有模数均两两互质），该逆元始终存在。

步骤 4：构造解

通解为 \(x + k \cdot M\)（对于任何整数 \(k\)），这意味着解每隔 \(M\) 个整数重复一次。

如何使用此计算器

1. 输入您的同余式： 对于每个方程 \(x \equiv a \pmod{m}\)，输入余数 \(a\) 和模数 \(m\)。从 2 个同余式开始，点击“添加同余方程”增加更多（最多 10 个）。
2. 检查您的模数： 所有模数必须为正整数 ≥ 2 且两两互质。计算器会自动验证这一点。
3. 点击“求解方程组”： 计算器应用 CRT 算法，显示唯一解及详细的计算过程。
4. 查看可视化： 数轴显示了每个方程的同余类如何在解处交汇。
5. 验证： 验证部分确认了解满足每一个原始同余式。

理解结果

• 最小非负解 (x₀)： 在范围 [0, M−1] 内的唯一解。
• 通解： 所有形式为 x₀ + kM 的整数，其中 k 为任意整数。
• 验证表： 确认每个同余式的 x₀ mod mᵢ = aᵢ。
• 逐步分解： 显示每个方程的 Mᵢ、模逆元 yᵢ 和部分和 aᵢ·Mᵢ·yᵢ。
• 数轴： 同余类如何在解处对齐的视觉表示。

中国剩余定理的应用

经典的孙子问题

《孙子算经》中的原始问题问到：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

这转化为：\(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\)。使用 CRT，答案是 x = 23（更一般地，对于任何非负整数 k，为 23 + 105k）。

什么时候 CRT 不适用？

• 非互质模数： 如果任何一对模数具有大于 1 的公因数，则标准 CRT 不能保证有解。如果余数相容，解可能仍然存在，但此计算器要求使用标准算法的两两互质模数。
• 单个同余式： CRT 至少需要 2 个同余式。单个同余式 \(x \equiv a \pmod{m}\) 已经具有平凡解 x = a。

扩展欧几里得算法

扩展欧几里得算法对于 CRT 至关重要，因为它用于寻找模逆元。给定整数 \(a\) 和 \(b\)，它能找到整数 \(x\) 和 \(y\)，使得：

当 \(\gcd(a, b) = 1\) 时，\(x\) 就是 \(a\) 模 \(b\) 的模逆元，即 \(a \cdot x \equiv 1 \pmod{b}\)。

常见问题解答

什么是中国剩余定理？

中国剩余定理 (CRT) 指出，如果你有一个同余方程组 x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ)，且所有模数两两互质，则在模 M = m₁ × m₂ × ... × mₖ 下存在唯一解。该定理最早由中国数学家孙子在 3 世纪描述。

“两两互质”是什么意思？

两两互质意味着每一对模数之间除了 1 以外没有公因数。例如，{3, 5, 7} 是两两互质的，因为 gcd(3,5)=1, gcd(3,7)=1, 且 gcd(5,7)=1。然而，{4, 6, 5} 不是两两互质的，因为 gcd(4,6)=2。

如何逐步求解同余方程组？

使用 CRT 求解：(1) 验证模数两两互质。(2) 计算 M = 模数之积。(3) 计算每个 Mᵢ = M/mᵢ。(4) 使用扩展欧几里得算法求模逆元 yᵢ。(5) 计算解 x = Σ(aᵢ × Mᵢ × yᵢ) mod M。通解为 x + k×M。

中国剩余定理的应用有哪些？

CRT 有许多实际应用：RSA 加密使用 CRT 进行高效解密。计算机科学在大数运算中使用它。信号处理在纠错码中应用 CRT。具有不同间隔周期的调度和历法问题也会用到 CRT。

如果模数不互质会怎样？

如果模数不是两两互质的，标准 CRT 就不直接适用。在某些情况下，如果余数在非互质模数的最大公约数下是一致的，解可能依然存在。但如果没有解，则该方程组是不相容的。

额外资源

• 中国剩余定理 - 维基百科
• 扩展欧几里得算法 - 维基百科
• 模运算 - 维基百科