剩余定理经典例题-剩余定理例题

剩余定理，又称中国剩余定理，是数论中解决一组同余方程问题的核心定理，其历史渊源可追溯至中国古代的数学著作《孙子算经》中的“物不知数”问题。该定理系统性地阐述并解决了一元线性同余方程组在模数两两互质条件下的求解问题，给出了解的存在性、唯一性（在模所有模数乘积的意义下）以及具体的构造性解法。其核心思想在于通过巧妙地寻找一组“乘数”，将复杂的多元同余问题分解为若干个独立的、易于求解的同余问题，再将它们的解加权组合，从而得到原方程组的通解。
这不仅是初等数论的瑰宝，更是连接古典数学与现代密码学、计算机科学（如RSA算法、编码理论）、工程计算等领域的重要桥梁。在各类数学竞赛、研究生入学考试以及易搜职考网所服务的相关职业能力测评中，剩余定理及其应用都是考查学生逻辑构造能力与数学素养的重点和难点。掌握剩余定理，不仅意味着学会了一套解题技巧，更是对模运算思想、代数结构认知的一次深化，对于培养严谨的数学思维至关重要。理解其原理并能灵活运用于解决经典及变式例题，是通过相关考试的关键一环。

剩余定理的精妙之处在于它将一个全局性问题转化为局部问题的和，体现了“分而治之”的深刻数学思想。下面，我们将结合实际情况，通过一系列经典例题的详细阐述，来深入剖析剩余定理的应用。

设有一元线性同余方程组：

x ≡ a₁ (mod m₁)

x ≡ a₂ (mod m₂)

……

x ≡ aₖ (mod mₖ)

其中 m₁, m₂, …, mₖ 是两两互质的正整数。

记 M = m₁ m₂ … mₖ，并令 Mᵢ = M / mᵢ (i=1,2,…,k)，即 Mᵢ 是除了 mᵢ 之外所有模数的乘积。

由于 m₁, m₂, …, mₖ 两两互质，故对于每一个 i，Mᵢ 与 mᵢ 也互质。根据数论知识，存在整数 tᵢ，使得 Mᵢ tᵢ ≡ 1 (mod mᵢ)。这个 tᵢ 称为 Mᵢ 在模 mᵢ 意义下的“数论倒数”或“逆元”。

那么，该同余方程组在模 M 意义下的唯一解为：

x ≡ a₁M₁t₁ + a₂M₂t₂ + … + aₖMₖtₖ (mod M)

这个公式就是剩余定理的构造性解。解题的标准步骤可归纳为：

• 第一步：验证模数两两互质。这是应用经典剩余定理的前提。
• 第二步：计算总模数 M 及各部分模数乘积 Mᵢ。
• 第三步：求解逆元 tᵢ。即对每个 i，求解满足 Mᵢ tᵢ ≡ 1 (mod mᵢ) 的 tᵢ（通常取最小正整数解）。这可以通过扩展欧几里得算法、试探法或观察法完成。
• 第四步：代入公式合成解。计算 x₀ = a₁M₁t₁ + a₂M₂t₂ + … + aₖMₖtₖ。
• 第五步：写出最终解的形式。方程组的通解为 x ≡ x₀ (mod M)。通常题目要求最小正整数解，即计算 x₀ mod M 的最小正余数。

这是最源头的例题，出自《孙子算经》：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

翻译成同余方程组为：

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

显然，模数3, 5, 7两两互质。

• 计算：M = 357 = 105。 M₁ = 105/3 = 35， M₂ = 105/5 = 21， M₃ = 105/7 = 15。
• 求逆元：
  • 求 t₁ 满足 35 t₁ ≡ 1 (mod 3)。因为 35 mod 3 = 2，即求 2t₁ ≡ 1 (mod 3)，易得 t₁ = 2 (因为 22=4≡1 mod 3)。
  • 求 t₂ 满足 21 t₂ ≡ 1 (mod 5)。21 mod 5 = 1，所以 1t₂ ≡ 1 (mod 5)，t₂ = 1。
  • 求 t₃ 满足 15 t₃ ≡ 1 (mod 7)。15 mod 7 = 1，所以 t₃ = 1。
• 代入公式：x₀ = a₁M₁t₁ + a₂M₂t₂ + a₃M₃t₃ = 2352 + 3211 + 2151 = 140 + 63 + 30 = 233。
• 求最小正整数解：x ≡ 233 (mod 105)。计算 233 ÷ 105 = 2 余 23。所以最小正整数解是 23。

也是因为这些，满足条件的最小物品数量是23。这个解法过程清晰地展示了剩余定理的每一步，是理解定理的绝佳起点。在易搜职考网的数论题库中，此类基础题型是夯实概念的必备练习。

经典剩余定理要求模数两两互质。当模数不互质时，方程组不一定有解。若有解，则需要先将其转化为模数互质或可分层处理的情形。这是考试中的常见提高点。

例题：求解同余方程组

x ≡ 2 (mod 4)

x ≡ 3 (mod 6)

x ≡ 1 (mod 7)

这里，4和6不互质，最大公约数(4,6)=2。

解法思路：首先处理前两个不互质的方程。将同余方程转化为等式形式：x = 4k + 2。将其代入第二个方程：4k + 2 ≡ 3 (mod 6) => 4k ≡ 1 (mod 6)。

注意到(4,6)=2，而1不能被2整除，所以方程4k ≡ 1 (mod 6)无解。
也是因为这些，原方程组无解。这体现了模数不互质时解的存在性需要检验。

另一个有解的例题：求解

x ≡ 3 (mod 8)

x ≡ 7 (mod 12)

(8,12)=4。将同余方程写为：x = 8a + 3, x = 12b + 7。联立得 8a + 3 = 12b + 7 => 8a - 12b = 4 => 2a - 3b = 1。

这是一个二元一次不定方程。观察得一特解：a=2, b=1。通解为：a = 2 + 3t, b = 1 + 2t (t为整数)。代入 x = 8a + 3 = 8(2+3t) + 3 = 16 + 24t + 3 = 19 + 24t。

所以，前两个方程等价于一个新的同余方程：x ≡ 19 (mod 24)。这里24是8和12的最小公倍数。

如果还有第三个方程（例如模7），且(24,7)=1，那么就可以用经典剩余定理求解新方程组 {x ≡ 19 (mod 24)， x ≡ c (mod 7)}。这种方法的核心是合并不互质的方程，用其最小公倍数作为新模数，得到一个等价的、模数可能互质的方程组。这一技巧在易搜职考网提供的进阶解题指南中常有系统归纳。

在剩余定理的步骤中，求逆元是关键操作。除了观察法，还有两种重要方法：

• 扩展欧几里得算法：这是通用且程序化的方法。对于求 Mᵢ tᵢ ≡ 1 (mod mᵢ)，即求不定方程 Mᵢ tᵢ + mᵢ y = 1 的整数解 tᵢ。因为(Mᵢ, mᵢ)=1，该方程必有解。
  例如，求 35t ≡ 1 (mod 3)，即解 35t + 3y = 1。用扩展欧几里得算法解出 t 即可（通常取模3下的最小正余数）。
• 利用欧拉定理（当模数为素数时特别简单）：若模数 m 是素数 p，根据费马小定理，对于任意与 p 互质的 a，有 a^(p-1) ≡ 1 (mod p)。那么 a 的逆元就是 a^(p-2) mod p。虽然在大数时计算幂次较复杂，但在理论推导和小数字心算时很有用。

剩余定理常与其他数学知识结合，形成综合题。

例题（数论与代数结合）：一个自然数除以5余3，除以7余4，除以9余5。求满足条件的最小自然数。

列方程组：

x ≡ 3 (mod 5)

x ≡ 4 (mod 7)

x ≡ 5 (mod 9)

模数5, 7, 9两两互质（注意(7,9)=1, (5,9)=1, (5,7)=1）。

• M = 579 = 315。 M₁=315/5=63， M₂=315/7=45， M₃=315/9=35。
• 求逆元：
  • 63t₁ ≡ 1 (mod 5)。63 mod 5 = 3，求 3t₁ ≡ 1 (mod 5)，得 t₁ = 2 (32=6≡1)。
  • 45t₂ ≡ 1 (mod 7)。45 mod 7 = 3，求 3t₂ ≡ 1 (mod 7)，得 t₂ = 5 (35=15≡1)。
  • 35t₃ ≡ 1 (mod 9)。35 mod 9 = 8，求 8t₃ ≡ 1 (mod 9)，得 t₃ = 8 (88=64≡1)。因为88=64，64÷9=7…1。
• 计算 x₀ = 3632 + 4455 + 5358 = 378 + 900 + 1400 = 2678。
• 求最小正整数解：2678 ÷ 315 = 8 余 158。所以最小自然数是158。

验证：158 ÷ 5 = 31 余 3，158 ÷ 7 = 22 余 4，158 ÷ 9 = 17 余 5。符合。

例题（与数列、周期问题结合）：一列数，按3个一组余1个，按5个一组余2个，按7个一组余3个。问这列物品至少有多少个？若物品总数在1000到1500之间，可能的数量是多少？

这实质是解 x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7)。先求最小解：

• M=105, M₁=35, M₂=21, M₃=15。
• 逆元：35t₁≡1(mod3)=>2t₁≡1=>t₁=2；21t₂≡1(mod5)=>1t₂≡1=>t₂=1；15t₃≡1(mod7)=>1t₃≡1=>t₃=1。
• x₀=1352+2211+3151=70+42+45=157。最小正解：157 mod 105 = 52。

所以通解为 x = 52 + 105k (k为非负整数)。

求在1000到1500之间的解：令 1000 ≤ 52 + 105k ≤ 1500。解得 (1000-52)/105 ≈ 9.03， (1500-52)/105 ≈ 13.8。所以 k 取 10, 11, 12, 13。

对应的 x 为：52+10510=1102；52+10511=1207；52+10512=1312；52+10513=1417。

这类将剩余定理的解与不等式结合，求参数范围的问题，在实战中非常普遍。

虽然本文聚焦于数学例题，但了解其应用背景能加深理解。剩余定理在现代密码学，特别是RSA算法和秘密共享方案中扮演着重要角色。其思想——将大数运算分解为多个互质小模数下的并行运算——被用于加速模幂运算（如RSA的解密）。在编码理论中，它用于构造纠错码。理解这些背景，有助于考生在易搜职考网遇到相关跨学科题目时，能够灵活联想，洞察问题的数学本质。

在应用剩余定理解题时，以下几个陷阱需要警惕：

• 忽视模数互质的前提：这是最常犯的错误。必须首先检查或处理模数的互质性。
• 逆元求解错误：求得的 tᵢ 必须满足 Mᵢ tᵢ ≡ 1 (mod mᵢ)，且通常取最小正整数。计算后建议简单验证。
• 最终解的表达不规范：最终答案应写成 x ≡ x₀ (mod M) 的形式，或按要求写出特定范围内的解。不要忘记取模得到最小正解。
• 合并方程时等价转换出错：在模数不互质需要合并方程时，要仔细求解不定方程，并正确求出合并后的新模数（原模数的最小公倍数）。

通过对上述经典例题从基础到综合的层层剖析，我们可以看到，剩余定理并非一个孤立的公式，而是一个包含前提验证、问题转化、工具应用（求逆元）和结果合成的系统解题框架。在易搜职考网的学习体系中，熟练掌握这一框架，并通过大量练习将步骤内化，是应对各类数论相关考核的不二法门。从古老的“物不知数”到现代密码学，其思想一脉相承，展现了数学工具持久的生命力。