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

中国剩余定理，又称孙子定理，是中国古代数学一项辉煌的成就，最早见于《孙子算经》中的“物不知数”问题。其核心在于解决一组同余方程组的求解问题，即寻找一个整数，使其除以若干个两两互质的除数后，得到指定的余数。这一定理不仅在数论领域占据基础而重要的地位，其思想与方法更是广泛应用于密码学、计算机科学、编码理论、信号处理等现代科技领域。对于备考各类职考，尤其是涉及行测数量关系、数学基础或计算机专业考试的考生来说呢，深入理解并熟练运用中国剩余定理是攻克相关难题的关键。经典例题的剖析与演练，是掌握该定理从理论到实践不可或缺的桥梁。这些例题通常从最基础的“物不知数”原型出发，逐步扩展到除数不互质的情况（此时需先转化为互质情形或采用合并方程法），再延伸至更复杂的同余方程组求解，甚至与模运算的其他性质结合。通过经典例题的学习，考生不仅能学会具体的解题步骤——包括寻找模数的乘积、计算各模数对应的数论倒数（或满足条件的特定乘数）、线性组合得到特解，最后写出通解形式——更能深刻体会“化整为零、聚零为整”的数学思想，锻炼逻辑思维与抽象建模能力。易搜职考网提醒广大考生，在备考过程中，应将中国剩余定理视为一个重要的工具模块，通过反复研究经典例题，掌握其核心原理与变式应用，从而在考试中遇到相关问题时能够迅速识别、准确求解。

中国剩余定理为解决一类特定形式的同余方程组提供了构造性的通解公式。给定一组两两互质的正整数 (m_1, m_2, ldots, m_k)，以及任意整数 (a_1, a_2, ldots, 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 times m_2 times ldots times m_k)，并令 (M_i = M / m_i)（即除去(m_i)外所有模数的乘积）。由于(m_i)两两互质，故(M_i)与(m_i)也互质。根据数论知识，存在整数(t_i)（称为(M_i)模(m_i)的逆元），使得 (M_i t_i equiv 1 pmod{m_i})。这个(t_i)可以通过扩展欧几里得算法求得。

那么，该同余方程组的一个特解为：

[ x_0 = a_1 M_1 t_1 + a_2 M_2 t_2 + ldots + a_k M_k t_k ]

而方程组的通解，即所有解的集合，可以表示为：

[ x equiv x_0 pmod{M} ]

这意味着，在模(M)的意义下，解是唯一的。定理的优美之处在于它将求解多个同余方程的问题，转化为寻找一系列逆元并进行线性组合的问题，实现了问题的分解与重构。

这是最直接应用定理的情形，模数两两互质。解题步骤清晰，是理解和掌握定理的起点。

例题1（《孙子算经》原题）：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

解析与解答： 依题意，可列出同余方程组： [ begin{cases} x equiv 2 pmod{3} \ x equiv 3 pmod{5} \ x equiv 2 pmod{7} end{cases} ]

这里模数 (m_1=3, m_2=5, m_3=7) 两两互质。

• 计算总模数 (M = 3 times 5 times 7 = 105)。
• 计算各部分模数乘积 (M_1 = 105/3 = 35)， (M_2 = 105/5 = 21)， (M_3 = 105/7 = 15)。
• 寻找逆元 (t_i)：
  • 对模3：求 (35 t_1 equiv 1 pmod{3})，即 (2 t_1 equiv 1 pmod{3})，得 (t_1 = 2)（因为 (2 times 2 = 4 equiv 1 pmod{3})）。
  • 对模5：求 (21 t_2 equiv 1 pmod{5})，即 (1 cdot t_2 equiv 1 pmod{5})，得 (t_2 = 1)。
  • 对模7：求 (15 t_3 equiv 1 pmod{7})，即 (1 cdot t_3 equiv 1 pmod{7})，得 (t_3 = 1)。
• 构造特解：(x_0 = a_1 M_1 t_1 + a_2 M_2 t_2 + a_3 M_3 t_3 = 2 times 35 times 2 + 3 times 21 times 1 + 2 times 15 times 1 = 140 + 63 + 30 = 233)。
• 求最小正整数解：(233 mod 105 = 233 - 2 times 105 = 23)。
  也是因为这些，满足条件的最小正整数是23。通解为 (x = 23 + 105k, , k in mathbb{Z})。

易搜职考网提示，此类基础题的关键在于准确计算逆元。对于较小的模数，可以通过试乘法快速得到；对于较大的模数，则需掌握扩展欧几里得算法。

例题2（稍作变形）： 一个数除以5余3，除以6余4，除以7余1。求满足条件的最小自然数。

解析与解答： 方程组为： [ begin{cases} x equiv 3 pmod{5} \ x equiv 4 pmod{6} \ x equiv 1 pmod{7} end{cases} ]

注意，此处模数5、6、7中，5和7互质，5和6互质，但6和7虽然也互质，然而在标准中国剩余定理中要求两两互质，而5、6、7确实两两互质（6和7的最大公约数是1），因此可以直接应用定理。

• (M = 5 times 6 times 7 = 210)。
• (M_1 = 210/5 = 42)， (M_2 = 210/6 = 35)， (M_3 = 210/7 = 30)。
• 求逆元：
  • 解 (42 t_1 equiv 1 pmod{5})，即 (2 t_1 equiv 1 pmod{5})，得 (t_1 = 3)。
  • 解 (35 t_2 equiv 1 pmod{6})，即 (5 t_2 equiv 1 pmod{6})，得 (t_2 = 5)（(5 times 5 = 25 equiv 1 pmod{6})）。
  • 解 (30 t_3 equiv 1 pmod{7})，即 (2 t_3 equiv 1 pmod{7})，得 (t_3 = 4)。
• 特解 (x_0 = 3 times 42 times 3 + 4 times 35 times 5 + 1 times 30 times 4 = 378 + 700 + 120 = 1198)。
• 最小正整数解：(1198 mod 210 = 1198 - 5 times 210 = 1198 - 1050 = 148)。验证：148除以5余3，除以6余4（148 ÷ 6 = 24...4），除以7余1（148 ÷ 7 = 21...1），正确。故答案为148。

当模数并非两两互质时，不能直接套用标准公式。此时，方程组可能有解也可能无解。求解思路通常有两种：一是将方程组逐步合并，利用扩展欧几里得算法求解线性丢番图方程；二是先将模数分解，尝试转化为互质的情形。这是考试中的难点和重点。

例题3（模数含有公因数）： 求解同余方程组： [ begin{cases} x equiv 2 pmod{4} \ x equiv 3 pmod{6} \ x equiv 1 pmod{7} end{cases} ]

解析与解答： 观察模数4和6，不互质（最大公约数为2）。我们需要先检查方程组是否相容。通常从前两个方程开始合并。

• 由 (x equiv 2 pmod{4})，可设 (x = 2 + 4k)。
• 代入第二个方程：(2 + 4k equiv 3 pmod{6}) => (4k equiv 1 pmod{6})。
• 此同余方程有解的充要条件是 (gcd(4,6) = 2) 能整除 (1)，但2不能整除1，故方程 (4k equiv 1 pmod{6}) 无解。
  也是因为这些，原方程组无解。

此例说明，模数不互质时，方程组不一定有解。易搜职考网提醒考生，遇到非互质模数，第一步应是判断解的存在性。

例题4（可解的不互质情形）： 求解同余方程组： [ begin{cases} x equiv 3 pmod{8} \ x equiv 11 pmod{20} \ x equiv 1 pmod{15} end{cases} ]

解析与解答： 模数8、20、15不全部两两互质（例如8和20的最大公约数是4）。我们采用合并法逐步求解。

步骤一：合并前两个方程。

• 由 (x equiv 3 pmod{8})，设 (x = 3 + 8a)。
• 代入 (x equiv 11 pmod{20})： (3 + 8a equiv 11 pmod{20}) => (8a equiv 8 pmod{20})。
• 化简，两边除以 (gcd(8,20)=4)，注意模也要除以4： (2a equiv 2 pmod{5}) => (a equiv 1 pmod{5})。
• 所以 (a = 1 + 5b)。
• 回代：(x = 3 + 8(1 + 5b) = 3 + 8 + 40b = 11 + 40b)。即前两个方程等价于 (x equiv 11 pmod{40})。

步骤二：将合并结果与第三个方程合并。

• 现有 (x equiv 11 pmod{40}) 与 (x equiv 1 pmod{15})。
• 由 (x equiv 11 pmod{40})，设 (x = 11 + 40c)。
• 代入 (x equiv 1 pmod{15})： (11 + 40c equiv 1 pmod{15}) => (40c equiv -10 equiv 5 pmod{15})。
• 化简，求 (gcd(40,15)=5)，5整除5，故有解。两边同除以5： (8c equiv 1 pmod{3})。
• 进一步简化模：(8 equiv 2 pmod{3})，所以 (2c equiv 1 pmod{3})，解得 (c equiv 2 pmod{3})（因为 (2 times 2 = 4 equiv 1 pmod{3})）。
• 设 (c = 2 + 3d)。
• 回代：(x = 11 + 40(2 + 3d) = 11 + 80 + 120d = 91 + 120d)。

也是因为这些，原方程组的通解为 (x equiv 91 pmod{120})。最小正整数解是91。验证：91除以8余3，除以20余11（91 ÷ 20 = 4...11），除以15余1，完全符合。

在实际问题或考题中，余数可能以负数形式出现，或者模数、余数较大，需要先进行简化处理。

例题5（处理负余数）： 求解方程组： [ begin{cases} x equiv -2 pmod{5} \ x equiv 3 pmod{6} \ x equiv -4 pmod{11} end{cases} ]

解析与解答： 首先将负余数转化为标准的最小非负余数。

• (-2 mod 5 = 3) （因为 -2 + 5 = 3）。
• (-4 mod 11 = 7) （因为 -4 + 11 = 7）。

原方程组等价于： [ begin{cases} x equiv 3 pmod{5} \ x equiv 3 pmod{6} \ x equiv 7 pmod{11} end{cases} ]

模数5、6、11两两互质，可直接应用定理。

• (M = 5 times 6 times 11 = 330)。
• (M_1 = 330/5 = 66)， (M_2 = 330/6 = 55)， (M_3 = 330/11 = 30)。
• 求逆元：
  • (66 t_1 equiv 1 pmod{5})，即 (1 cdot t_1 equiv 1 pmod{5})， (t_1 = 1)。
  • (55 t_2 equiv 1 pmod{6})，即 (1 cdot t_2 equiv 1 pmod{6})， (t_2 = 1)。
  • (30 t_3 equiv 1 pmod{11})，即 (8 t_3 equiv 1 pmod{11})，试算得 (t_3 = 7)（因为 (8 times 7 = 56 equiv 1 pmod{11})）。
• 特解 (x_0 = 3 times 66 times 1 + 3 times 55 times 1 + 7 times 30 times 7 = 198 + 165 + 1470 = 1833)。
• 最小正整数解：(1833 mod 330 = 1833 - 5 times 330 = 1833 - 1650 = 183)。验证后正确。通解 (x equiv 183 pmod{330})。

例题6（大数简化与观察法结合）： 求一个最小的正整数，使得它除以3余2，除以5余3，除以7余4。

解析与解答： 虽然这是基础互质情形，但我们可以展示一种逐步满足条件的“尝试调整”思路，这有时在考试中更快。列出方程： [ begin{cases} x equiv 2 pmod{3} \ x equiv 3 pmod{5} \ x equiv 4 pmod{7} end{cases} ]

先找一个数满足前两个条件。由 (x equiv 2 pmod{3}) 和 (x equiv 3 pmod{5})，枚举3的倍数加2：2, 5, 8, 11, 14, 17... 检查除以5余3：8符合（8 ÷ 5 = 1...3）。所以满足前两个条件的数形如 (x = 8 + 15k)（因为3和5的最小公倍数是15）。

现在将 (x = 8 + 15k) 代入第三个条件：(8 + 15k equiv 4 pmod{7})。简化：(8 equiv 1 pmod{7})， (15k equiv k pmod{7})（因为15 ≡ 1 mod 7）。所以方程变为 (1 + k equiv 4 pmod{7}) => (k equiv 3 pmod{7})。取最小 (k=3)。

则 (x = 8 + 15 times 3 = 53)。验证：53除以3余2，除以5余3，除以7余4（53 ÷ 7 = 7...4）。故最小正整数解为53。这种方法体现了逐步合并的思想，无需计算所有逆元，对于模数较小的情况可能更快捷。易搜职考网建议考生根据题目数字特点灵活选择方法。

这类题目往往将中国剩余定理与其他数论知识或实际问题相结合，难度较大，需要较强的分析能力和综合运用能力。

例题7（与循环周期结合）： 某工厂生产零件，按顺序编号。已知编号满足：被2除余1，被3除余2，被5除余3，被7除余4。问第2024个满足此条件的零件编号是多少？

解析与解答： 这是一个四元同余方程组，模数2、3、5、7两两互质。 [ begin{cases} x equiv 1 pmod{2} \ x equiv 2 pmod{3} \ x equiv 3 pmod{5} \ x equiv 4 pmod{7} end{cases} ]

我们先求出满足条件的最小正整数解及其通解形式。

• 总模数 (M = 2 times 3 times 5 times 7 = 210)。
• 分别计算：
  • 对于模2：(M_1 = 105)， 需解 (105 t_1 equiv 1 pmod{2})，即 (1 cdot t_1 equiv 1 pmod{2})， (t_1 = 1)。
  • 对于模3：(M_2 = 70)， 需解 (70 t_2 equiv 1 pmod{3})，即 (1 cdot t_2 equiv 1 pmod{3})， (t_2 = 1)。
  • 对于模5：(M_3 = 42)， 需解 (42 t_3 equiv 1 pmod{5})，即 (2 t_3 equiv 1 pmod{5})， (t_3 = 3)。
  • 对于模7：(M_4 = 30)， 需解 (30 t_4 equiv 1 pmod{7})，即 (2 t_4 equiv 1 pmod{7})， (t_4 = 4)。
• 特解 (x_0 = 1 times 105 times 1 + 2 times 70 times 1 + 3 times 42 times 3 + 4 times 30 times 4 = 105 + 140 + 378 + 480 = 1103)。
• 最小正整数解：(1103 mod 210 = 1103 - 5 times 210 = 1103 - 1050 = 53)。验证可知53满足所有条件。
  也是因为这些吧，通解为 (x = 53 + 210k, , k ge 0) 的整数。

题目要求第2024个编号。这构成了一个首项为53，公差为210的等差数列。第N项公式为 (a_N = 53 + (N-1) times 210)。

代入 (N = 2024)： (a_{2024} = 53 + (2024-1) times 210 = 53 + 2023 times 210 = 53 + 424830 = 424883)。

所以，第2024个满足条件的零件编号是424883。此题综合了同余方程组求解和等差数列应用。

例题8（反求参数问题）： 已知同余方程组 [ begin{cases} x equiv a pmod{9} \ x equiv 3 pmod{12} \ x equiv 7 pmod{15} end{cases} ] 有解，且解在100到200之间。求参数 (a) 的值及对应的最小解。

解析与解答： 模数9、12、15不互质。因为有解，我们需要先处理后两个方程，找到它们公共解的形式，再与第一个方程结合。

第一步：合并第
二、三个方程。

• 由 (x equiv 3 pmod{12})，设 (x = 3 + 12m)。
• 代入 (x equiv 7 pmod{15})： (3 + 12m equiv 7 pmod{15}) => (12m equiv 4 pmod{15})。
• 求 (gcd(12,15)=3)，检查：3整除4？不整除，所以...等等，题目说有解，这里似乎矛盾？仔细计算：(12m equiv 4 pmod{15})，两边除以公约数前，先看是否成立。实际上，12m mod 15的可能取值是0, 12, 9, 6, 3的循环（因为121=12, 122=24≡9, 123=36≡6, 124=48≡3, 125=60≡0...），其中并没有4。所以后两个方程本身无解？这与题目“有解”矛盾。这说明题目可能预设了某种条件，或者我们对“有解”的理解是整体有解，但后两个方程单独合并可能无解，而第一个方程的加入可能通过调整a使得整体有解。更严谨的做法是，考虑整体有解的必要条件：对于任意两个方程，其模的最大公约数必须整除相应余数之差。

让我们检查所有两两条件：

1. 方程2和3：模12和15的gcd=3。需满足 (3 equiv 7 pmod{3})？即3 mod 3=0， 7 mod 3=1， 0 ≡ 1 mod 3？不成立。所以，除非题目中的余数3或7有误，或者模数有特定关系使得整体能通过第一个方程调整，否则后两个方程矛盾。但标准解法下，若两个方程模不互质，它们各自提供的条件必须相容于其最大公约数。这里(3 mod 3) ≠ (7 mod 3)，因此无论a取何值，整个方程组都无解。这提示可能原题数据需要修正，例如第二个方程改为 (x equiv 3 pmod{12}) 可能意味着 (x equiv 3 pmod{4}) 和 (x equiv 3 pmod{3}) 的组合，但处理起来非常复杂。

为了完成此类型题目的讲解，我们假设一个修正后的、可能有解的题目：例如，将第三个方程改为 (x equiv 3 pmod{15})（与第二个方程余数在模3意义下一致）。即： [ begin{cases} x equiv a pmod{9} \ x equiv 3 pmod{12} \ x equiv 3 pmod{15} end{cases} ]

现在，后两个方程在模3意义下都是余3（3 mod 3 = 0, 但更精确地说，12和15的最小公倍数是60，我们需要找公共解）。

• 由 (x equiv 3 pmod{12}) 和 (x equiv 3 pmod{15})，显然 (x = 3 + 60n) 是它们的公共解（因为3除以12和15都余3）。实际上，更准确的是解 (x equiv 3 pmod{text{lcm}(12,15)} = pmod{60})。所以后两个方程等价于 (x equiv 3 pmod{60})。
• 现在与第一个方程 (x equiv a pmod{9}) 联立。模数60和9互质（gcd(60,9)=3，等等，不互质！60和9的最大公约数是3）。所以仍需合并。
• 设 (x = 3 + 60k)，代入 (x equiv a pmod{9})： (3 + 60k equiv a pmod{9})。
• 简化：60 ≡ 6 (mod 9)，所以 (3 + 6k equiv a pmod{9})，即 (6k equiv a-3 pmod{9})。
• 此方程有解的充要条件是 (gcd(6,9)=3) 整除 ((a-3))。所以 (a-3) 必须是3的倍数，即 (a equiv 3 pmod{3})，也就是 (a) 可以是 0, 3, 6 模9？不对，a是模9的余数，取值范围0~8。条件为3 | (a-3)，所以 a = 3, 6, 0 (即9的倍数余0，但0也视为余0)。但a是模9的余数，通常取最小非负，所以a可能为0, 3, 6。
• 对于每个a，解出k，再求x在100-200之间的值。例如取a=3，则方程变为 (6k equiv 0 pmod{9})，即 (2k equiv 0 pmod{3})，所以 (k equiv 0 pmod{3})。设k=3t，则 (x = 3 + 60 times 3t = 3 + 180t)。当t=0时，x=3；t=1时，x=183（在100-200之间）；t=2时，x=363超出。所以对于a=3，一个解是183。
• 检查a=0：(6k equiv -3 equiv 6 pmod{9}) => (2k equiv 2 pmod{3}) => (k equiv 1 pmod{3})。设k=1+3t，则 (x = 3 + 60(1+3t) = 63 + 180t)。当t=0，x=63；t=1，x=243超出。所以对于a=0，在100-200间无解。
• 检查a=6：(6k equiv 3 pmod{9}) => (2k equiv 1 pmod{3})，无解（因为2模3的逆元是2，21=2≠1 mod 3？实际上2k≡1 mod 3的解是k≡2 mod 3）。有解。设k=2+3t，则 (x = 3 + 60(2+3t) = 123 + 180t)。当t=0，x=123（在区间内）；t=1，x=303超出。所以对于a=6，一个解是123。

也是因为这些，在修正后的题目假设下，参数a可以是3或6，对应的最小解（在100-200内）分别是183和123。这类题目考察了对解的存在性条件的深入理解以及合并方程的技巧。

通过对以上各类经典例题的详细剖析，我们可以清晰地看到，从基础的互质情形到复杂的非互质情形，从直接求解除到反求参数、结合周期数列，掌握中国剩余定理及其扩展方法需要系统的练习和深入的思考。易搜职考网建议学习者在理解原理的基础上，通过大量练习来熟悉各种题型的变化，从而在考试中能够游刃有余。无论是简单的直接套用，还是需要先判断相容性、合并方程，其核心思想都是将复杂的同余条件逐步化简、归并，最终化为单个同余式。这种化繁为简、逐步逼近的解题策略，其意义远超题目本身，对于培养逻辑思维能力大有裨益。