数论数学计算器模运算

中文剩余定理计算器：逐步求解模同余系统

September 8, 2026·14 min read·Solvify Team

中文剩余定理计算器通过将多个同余方程组合成单个同余方程来解决这些方程组 — 例如 x ≡ 2 (mod 3) 和 x ≡ 3 (mod 5) 这样的方程 — 其中模数是各个模的乘积（或最小公倍数）。这个方法大约距今 1500 年前来自中国古代数学文献《孙子算经》，而今天它被广泛应用于 RSA 密码学优化、日历计算和纠错码，同时也是离散数学和数论课程的主要内容。本指南将详细介绍计算器的工作原理、如何检查系统是否有解、如何求解该方法依赖的模逆元、两个完整的工作示例（一个带互质模数，一个不带）以及常见错误和练习题。

什么是中文剩余定理？

中文剩余定理（CRT）说如果您有一个同余方程组 x ≡ a₁ (mod m₁)、x ≡ a₂ (mod m₂)、...、x ≡ aₙ (mod mₙ)，且模数 m₁、m₂、...、mₙ 两两互质（每对除了 1 以外没有公因子），那么对于 x 模 M 恰好存在一个解，其中 M = m₁ × m₂ × ... × mₙ。该定理因其最早在 3 至 5 世纪的中国文献《孙子算经》（孙子的算术手册）中出现而得名，文献中提出了现在经典的谜题：找一个数，用 3 除余 2，用 5 除余 3，用 7 除余 2。这个谜题和求解它的 CRT 方法在课堂外不断出现：RSA 密码学使用 CRT 通过处理较小的模而不是一个巨大的模来加快解密速度，计算机科学家使用它将大数表示为较小剩余数的元组以进行更快的算术运算，日历系统使用它来协调不同长度的周期（一周的天数、一个月的天数和闰年周期）。

中文剩余定理：对于两两互质的模数 m₁、...、mₙ，系统 x ≡ aᵢ (mod mᵢ) 对于 M = m₁ × m₂ × ... × mₙ 恰好有一个解。

中文剩余定理计算器如何工作？

中文剩余定理计算器自动执行四个阶段，这些阶段在一个系统有三个或更多同余方程时手工跟踪会很繁琐，特别是模逆元计算。在内部，它将每个同余方程视为一对 (aᵢ, mᵢ)，确认模数可以一起使用，然后使用加权和而不是试错法构建唯一解。理解这四个阶段是让您能够验证计算器输出或在不允许使用计算器的考试中手工解决相同问题的关键。

1. 第 1 步：检查模数

确认每对模数都互质（gcd = 1）。如果任何一对共享公因子，计算器将切换到下一部分描述的兼容性检查，而不是使用标准公式。

2. 第 2 步：计算组合模数 M

将所有模数相乘：M = m₁ × m₂ × ... × mₙ。这是最终组合答案的模数。

3. 第 3 步：找到每个部分乘积及其模逆元

对于每个同余方程 i，计算 Mᵢ = M / mᵢ（除了 mᵢ 以外所有模数的乘积），然后找到 Mᵢ 模 mᵢ 的模逆元 — 称为 yᵢ，其中 Mᵢ × yᵢ ≡ 1 (mod mᵢ)。

4. 第 4 步：组合和约化

对每个同余方程求 aᵢ × Mᵢ × yᵢ 的和，然后将该和对 M 求模以获得唯一的最小非负解 x。

每个中文剩余定理计算器背后的公式：x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M，其中 Mᵢ = M/mᵢ，yᵢ 是 Mᵢ 模 mᵢ 的模逆元。

如何检查模数是否兼容？

中文剩余定理的教科书版本需要两两互质的模数，但真实系统 — 特别是出现在调度或密码学问题中的系统 — 通常有共享因子的模数。CRT 的广义版本仍然适用，但仅当系统首先通过兼容性检查时才适用：对于每对同余方程 x ≡ aᵢ (mod mᵢ) 和 x ≡ aⱼ (mod mⱼ)，两者必须在重叠部分上一致，意味着 aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ))。如果这个检查对任何一对失败，系统无论如何都没有解 — 一个好的计算器会报告这一点，而不是返回一个错误的数字。

1. 第 1 步：计算每对模数的 gcd(mᵢ, mⱼ)

对于两个同余方程的系统，只有一对要检查。对于三个同余方程的系统，检查所有三对。

2. 第 2 步：将两个剩余数都对该 gcd 求模

取 aᵢ mod gcd(mᵢ, mⱼ) 和 aⱼ mod gcd(mᵢ, mⱼ)。如果它们匹配，则该对兼容。

3. 第 3 步：不兼容系统的示例

取 x ≡ 1 (mod 4) 和 x ≡ 0 (mod 6)。gcd(4, 6) = 2。约化：1 mod 2 = 1，0 mod 2 = 0。由于 1 ≠ 0，没有整数同时满足两个同余方程 — 系统没有解，中文剩余定理计算器应该明确标记这一点，而不是强行给出一个答案。

非互质模数的兼容性规则：x ≡ aᵢ (mod mᵢ) 和 x ≡ aⱼ (mod mⱼ) 只有当 aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ)) 时才能都成立。

什么是模逆元以及如何找到它？

数字 a 模 m 的模逆元是另一个数字 b，使得 a × b ≡ 1 (mod m) — 它在固定模数内的整数范围内发挥与普通除法中 1/a 相同的作用。模逆元存在当且仅当 gcd(a, m) = 1，这正是标准中文剩余定理要求两两互质模数的原因：它保证每个 Mᵢ 在模 mᵢ 下都有逆元。手工找到模逆元最可靠的方法是扩展欧几里得算法，它向前运行普通 gcd 算法，然后向后工作以将 1 表示为 a 和 m 的组合。

1. 第 1 步：向前运行欧几里得算法

找到 4 模 7 的逆元。重复除法：7 = 1×4 + 3，然后 4 = 1×3 + 1，然后 3 = 3×1 + 0。余数是 3、然后 1、然后 0，确认 gcd(4, 7) = 1，所以逆元存在。

2. 第 2 步：向后工作以隔离 1

从倒数第二行，1 = 4 − 1×3。代入第一行的 3 = 7 − 1×4：1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7。

3. 第 3 步：读出逆元

方程 1 = 2×4 − 1×7 意味着 2×4 ≡ 1 (mod 7)，所以 4 模 7 的逆元是 2。快速检查：4 × 2 = 8 = 7 + 1，确实 ≡ 1 (mod 7)。

对于小模数，通常更快的做法是直接测试候选：将 a 乘以 1、2、3、... 模 m，直到乘积为 1。对于较大的模数，扩展欧几里得算法更为可靠。

工作示例：求解互质模数的同余方程

这是经典的孙子算经问题：找 x 使得 x ≡ 2 (mod 3)、x ≡ 3 (mod 5) 和 x ≡ 2 (mod 7)。模数 3、5 和 7 两两互质，所以标准 CRT 公式可以直接应用。

1. 第 1 步：计算 M

M = 3 × 5 × 7 = 105。

2. 第 2 步：计算每个 Mᵢ 及其逆元

M₁ = 105/3 = 35。35 mod 3 = 2，2 模 3 的逆元是 2（因为 2×2 = 4 ≡ 1 mod 3）。 M₂ = 105/5 = 21。21 mod 5 = 1，1 模 5 的逆元是 1。 M₃ = 105/7 = 15。15 mod 7 = 1，1 模 7 的逆元是 1。

3. 第 3 步：组合

x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23。

4. 第 4 步：验证

23 ÷ 3 = 7 余 2 ✓。23 ÷ 5 = 4 余 3 ✓。23 ÷ 7 = 3 余 2 ✓。最小非负解是 x = 23，每个其他解是 23 + 105k（对于任意整数 k）。

x ≡ 23 (mod 105) — 中文剩余定理计算器立即返回的答案，也是一千多年前开启数论这个分支的同一个谜题。

工作示例：协调非互质模数

现在求解 x ≡ 3 (mod 4) 和 x ≡ 1 (mod 6)，其中 4 和 6 不互质（它们共享因子 2）。互质模数示例中的标准公式不能直接应用，但系统仍可能有一个唯一解（模数的最小公倍数），前提是它首先通过兼容性检查。

1. 第 1 步：检查兼容性

gcd(4, 6) = 2。约化两个剩余数：3 mod 2 = 1，1 mod 2 = 1。它们匹配，所以系统兼容且解存在。

2. 第 2 步：找到组合模数

不是将 4 × 6 = 24 相乘，而是使用最小公倍数：lcm(4, 6) = 12。解将模 12 唯一，不是模 24。

3. 第 3 步：代入和求解

从第一个同余方程写出 x = 4k + 3，然后代入第二个：4k + 3 ≡ 1 (mod 6)，所以 4k ≡ −2 ≡ 4 (mod 6)。两边和模数都共享因子 gcd(4, 6) = 2，所以将整个同余方程除以 2：2k ≡ 2 (mod 3)。2 模 3 的逆元是 2，所以 k ≡ 2×2 ≡ 1 (mod 3)。

4. 第 4 步：重构 x

对于任意整数 j，k = 3j + 1，所以 x = 4(3j + 1) + 3 = 12j + 7。最小非负解是 x = 7。

5. 第 5 步：验证

7 mod 4 = 3 ✓。7 mod 6 = 1 ✓。所以 x ≡ 7 (mod 12) 是正确的，将同余方程除以共享因子 — 而不是忽略它 — 是使非互质 CRT 工作的步骤。

当模数共享公因子时，不能按原样使用互质公式 — 在找逆元前，必须将结果同余方程除以 gcd(mᵢ, mⱼ)，否则逆元不存在。

重构最小非负解

每个通过兼容性检查的中文剩余定理系统有无穷多个整数解，不仅仅是一个 — 但它们都模 M（或在非互质情况下模 lcm(m₁, ..., mₙ)）相同余。按惯例，计算器报告该无穷族的最小非负代表，满足 0 ≤ x₀ < M 的值 x₀，因为它是最容易表述、比较和验证的单一规范答案。每个其他解只是 x₀ 加上或减去 M 的倍数。

1. 约化负中间和

计算器方法第 4 步中的加权和如果任何剩余数 aᵢ 为负或如果模逆元被计算为负代表则可能为负。如果和为 S = −37，M = 45，重复加 M 直到结果非负：−37 + 45 = 8，所以最小非负解是 x₀ = 8，不是 −37。

2. 完整的解集

一旦您有了 x₀，完整的解集是形式为 x₀ + kM（对于 k = ...、−2、−1、0、1、2、...）的每个整数。在上面的孙子示例中，那是 23、128、233、...，也包括 −82、−187 等 — 但除非要求特定范围，23 是您报告的解。

一个负数或超大的中间结果并不错误 — 它只是还没有被约化。加上或减去 M 的倍数，直到值落在 [0, M)。

最常见的中文剩余定理错误是什么？

CRT 问题中的大多数错误来自跳过检查而不是有缺陷的最终计算，这就是为什么在问题开始时放慢速度而不是在结束时是值得的。

1. 将互质公式应用于非互质模数

如果任何两个模数共享因子，将 M 计算为它们的直接乘积并以标准方式查找模逆元将失败或产生错误答案 — 始终首先检查每对的 gcd(mᵢ, mⱼ) = 1。

2. 将模逆元与常规倒数混淆

4 模 7 的逆元是 2，不是 1/4 — 模逆元是通过扩展欧几里得算法（或小模数的试乘）找到的整数，从不是分数。

3. 未能正确约化负数模 m

−2 mod 6 是 4，不是 −2 也不是 2 — 持续加模数直到结果在范围 [0, m) 内。截断或取绝对值而不是加模数是错误答案的常见来源。

4. 忘记在非互质系统中除以共享因子

当模数共享公因子时，像 4k ≡ 4 (mod 6) 这样的同余方程必须通过 gcd(4, 6) = 2 除以变成 2k ≡ 2 (mod 3)，然后才能找到逆元 — 4 在模 6 下根本没有逆元，因为 gcd(4, 6) ≠ 1。

5. 在约化最终和模 M 之前停止

第 4 步中的加权和（例如，孙子问题中的 233）不是最终答案 — 它必须对 M 求模（233 mod 105 = 23）以达到最小非负解。

如果您的答案在代入时不满足每个原始同余方程，首先重新检查兼容性测试和模逆元 — 那是几乎每个 CRT 错误实际发生的地方。

练习题：测试您的中文剩余定理计算器技能

在将答案与下面的解决方案进行比较前，手工解决这三个系统，首先检查两两互质性或兼容性。第二个问题故意无法解决 — 识别这一点与找到存在解的数值答案一样重要。

1. 问题 1（互质）

求解：x ≡ 1 (mod 3)、x ≡ 4 (mod 5)、x ≡ 6 (mod 7)。答案：M = 105。M₁ = 35，在模 3 下的逆元是 2；M₂ = 21，在模 5 下的逆元是 1；M₃ = 15，在模 7 下的逆元是 1。和 = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244。244 mod 105 = 34。检查：34 mod 3 = 1 ✓、34 mod 5 = 4 ✓、34 mod 7 = 6 ✓。解：x ≡ 34 (mod 105)。

2. 问题 2（不兼容的模数 — 无解）

求解：x ≡ 2 (mod 8)、x ≡ 5 (mod 12)。gcd(8, 12) = 4。约化：2 mod 4 = 2，5 mod 4 = 1。由于 2 ≠ 1，系统不兼容且无解 — 中文剩余定理计算器应该返回这个结论而不是一个错误的数字。

3. 问题 3（兼容的非互质模数）

求解：x ≡ 5 (mod 9)、x ≡ 2 (mod 6)。gcd(9, 6) = 3。约化：5 mod 3 = 2，2 mod 3 = 2 — 兼容。lcm(9, 6) = 18。写出 x = 9k + 5，代入：9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6)。除以 gcd(9, 6) = 3：3k ≡ 1 (mod 2) → k ≡ 1 (mod 2)。所以 k = 2j + 1，给出 x = 9(2j+1) + 5 = 18j + 14。检查：14 mod 9 = 5 ✓、14 mod 6 = 2 ✓。解：x ≡ 14 (mod 18)。如果您想在像这样的问题上仔细检查每个模逆元和约化步骤，Solvify 的分步数学求解器将以本指南相同的方式逐步讲解每个阶段。

快速建立中文剩余定理真正流畅性的最快方法是求解互质、非互质但兼容以及不兼容系统的组合 — 识别您处于哪种情况是该技能的一半。

标签: