孙子定理的例题讲解
深入解析中国古代数学瑰宝——孙子定理（中国剩余定理），通过经典例题与详细步骤，掌握同余方程组的求解艺术。
〓 定理简介与核心概念〓
孙子定理，又称中国剩余定理（Chinese Remainder Theorem, CRT），是数论中的一个重要定理。它主要解决的是求解一元线性同余方程组的问题。在公元5世纪左右的《孙子算经》中，就记载了著名的“物不知数”问题，这是该定理的最早雏形。
定理的核心思想是：如果已知某个数 x 除以几个两两互质的正整数 m1, m2, ..., mk 所得的余数分别为 a1, a2, ..., ak，那么存在唯一的一个解 x 在区间 [0, M-1] 内，其中 M 是所有模数的乘积（M = m1 × m2 × ... × mk）。
| 概念 | 描述 | 数学表达 |
|---|---|---|
| 模数 (Modulus) | 除数，通常两两互质 | mi |
| 余数 (Remainder) | 除以模数后的结果 | ai |
| 逆元 (Inverse) | 满足 ti·Mi ≡ 1 (mod mi) 的数 | ti |
〓 经典例题深度解析〓
为了让大家更好地理解孙子定理，我们选取了《孙子算经》中的原题以及两个现代变式进行详细讲解。
题目描述
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
解析：这是一个典型的孙子定理应用题。我们需要找到一个数 x，满足：
- x ≡ 2 (mod 3)
- x ≡ 3 (mod 5)
- x ≡ 2 (mod 7)
解题步骤：
- 计算总模数 M：M = 3 × 5 × 7 = 105。
- 计算各分模数 Mi：
- M1 = 105 / 3 = 35
- M2 = 105 / 5 = 21
- M3 = 105 / 7 = 15
- 寻找逆元 ti：
- 35 × t1 ≡ 1 (mod 3) → 2 × t1 ≡ 1 (mod 3) → t1 = 2
- 21 × t2 ≡ 1 (mod 5) → 1 × t2 ≡ 1 (mod 5) → t2 = 1
- 15 × t3 ≡ 1 (mod 7) → 1 × t3 ≡ 1 (mod 7) → t3 = 1
- 计算最终解：
x = (2×35×2 + 3×21×1 + 2×15×1) mod 105 x = (140 + 63 + 30) mod 105 x = 233 mod 105 x = 23
答案：这个数最小是 23。
题目描述
一个正整数除以 4 余 1，除以 6 余 3，除以 9 余 6。求这个数。
注意：这里的模数 4, 6, 9 并非两两互质，因此不能直接套用标准公式，需要先化简或合并同余式。
- x ≡ 1 (mod 4) → x = 4k + 1
- x ≡ 3 (mod 6) → x = 6j + 3
- x ≡ 6 (mod 9) → x = 9m + 6
观察后两个式子：x+3 能被 6 整除，也能被 9 整除。即 x+3 是 6 和 9 的公倍数，最小公倍数是 18。
所以 x + 3 ≡ 0 (mod 18) → x ≡ 15 (mod 18)。
现在问题转化为：
x ≡ 1 (mod 4)
x ≡ 15 (mod 18)
由第二个式子，x = 18n + 15。代入第一个式子： 18n + 15 ≡ 1 (mod 4) 2n + 3 ≡ 1 (mod 4) 2n ≡ -2 ≡ 2 (mod 4) 这意味着 n 是奇数。令 n = 1, x = 33。 验证：33 ÷ 4 = 8...1 (对); 33 ÷ 6 = 5...3 (对); 33 ÷ 9 = 3...6 (对)。
答案：最小正整数解为 33。
题目描述
求解同余方程组：
x ≡ 2 (mod 7)
x ≡ 3 (mod 11)
x ≡ 4 (mod 13)
这里模数 7, 11, 13 两两互质，可直接使用孙子定理公式。
- M = 7 × 11 × 13 = 1001
- M1 = 143, M2 = 91, M3 = 77
- 求逆元：
- 143 × t1 ≡ 1 (mod 7) → 3 × t1 ≡ 1 → t1 = 5
- 91 × t2 ≡ 1 (mod 11) → 3 × t2 ≡ 1 → t2 = 4
- 77 × t3 ≡ 1 (mod 13) → 12 × t3 ≡ 1 → -1 × t3 ≡ 1 → t3 = -1 ≡ 12
- x = (2×143×5 + 3×91×4 + 4×77×12) mod 1001
- x = (1430 + 1092 + 3696) mod 1001
- x = 6218 mod 1001 = 212
答案：最小正整数解为 212。
〓 解题通用步骤指南〓
掌握孙子定理的解题套路，可以大大提高效率。以下是标准化的操作流程：
第一步：检查模数互质性
确认所有模数两两互质。如果不互质，需先通过合并同余式的方法化简，使其变为互质模数或处理公因子。
第二步：计算总积 M
将所有模数相乘，得到总模数 M。这是解的周期范围。
第三步：计算分项 Mi
用 M 除以每个模数 mi，得到 Mi = M / mi。
第四步：求解逆元 ti
寻找 ti 使得 Mi × ti ≡ 1 (mod mi)。这通常可以通过扩展欧几里得算法或试除法完成。
第五步：代入公式求和
计算 S = Σ (ai × Mi × ti)。最终解 x = S mod M。
〓 历史溯源与文化背景〓
孙子定理的名字来源于中国古代数学著作《孙子算经》。该书成书大约在公元4-5世纪，作者不详。其中卷下第26题“物不知数”是世界数学史上最早的同余式理论记载之一。
南宋数学家秦九韶在《数书九章》（1247年）中将其推广到任意多个模数的情况，并提出了“大衍求一术”，这是孙子定理的一般化解法，比西方同类成果早了500多年。1801年，德国数学家高斯在《算术研究》中系统地提出了同余理论，并给出了完整的证明，因此西方称其为中国剩余定理。
〓 实际应用与拓展〓
除了数学竞赛，孙子定理在现代科技中也有着广泛的应用：
⚡ 密码学 (RSA算法)
在RSA公钥密码系统中，中国剩余定理被用于加速解密过程。通过将大数模运算分解为两个较小的模运算，可以显著提高计算效率，特别是在使用中国余数定理（CRT）优化的RSA实现中。
⚙️ 错误校正码
在通信领域，孙子定理被用于构造纠错码，如Reed-Solomon码的变体。它帮助数据在传输过程中即使出现部分损坏，也能通过余数信息恢复原始数据。
🔢 大整数运算
在计算机处理超大整数时，直接运算非常耗时。利用孙子定理，可以将一个大整数运算转化为多个小模数下的并行运算，最后再合并结果，从而提高计算速度。
〓 网友们还关心〓
以下是关于孙子定理的例题讲解中，网民关注度最高的几个问题：
Q1: 如果模数不互质怎么办？
如果模数不互质，孙子定理的标准形式不能直接应用。此时需要检查同余方程组是否有解。如果对于任意两个模数 mi 和 mj，它们的余数 ai 和 aj 满足 ai ≡ aj (mod gcd(mi, mj))，则方程组有解。解法通常是先合并两个方程为一个新方程，再与下一个方程合并，直到只剩一个方程。
Q2: 逆元怎么快速求出来？
对于小模数，可以通过试除法找到。对于大模数，推荐使用扩展欧几里得算法（Extended Euclidean Algorithm）。该算法可以在求出 gcd(a, b) 的同时，找到满足 ax + by = gcd(a, b) 的 x 和 y。当 gcd(a, b) = 1 时，x 即为 a 关于 b 的逆元。
Q3: 孙子定理和同余方程组有什么区别？
孙子定理是求解一元线性同余方程组的一个充分必要条件和构造性解法。也就是说，当模数两两互质时，方程组一定有唯一解，且孙子定理给出了这个解的具体计算公式。因此，孙子定理是同余方程组理论中的一个特例和核心工具。
Q4: 为什么叫“物不知数”？
因为原题是以问句形式出现的：“有物不知其数”，意思是“有一个东西，不知道它的数量是多少”。这种表述方式充满了中国古代数学的趣味性和生活气息，也体现了数学源于生活的特点。
Q5: 有没有编程实现的例子？
当然有。以下是Python实现的简易版孙子定理求解器：
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
else:
gcd, x, y = extended_gcd(b % a, a)
return gcd, y - (b // a) x, x
def chinese_remainder_theorem(pairs):
# pairs: list of (remainder, modulus)
m1 = pairs[0][1]
a1 = pairs[0][0]
for i in range(1, len(pairs)):
m2 = pairs[i][1]
a2 = pairs[i][0]
gcd, x, y = extended_gcd(m1, m2)
if (a2 - a1) % gcd != 0:
return None # No solution
lcm = m1 m2 // gcd
diff = (a2 - a1) // gcd
m1 = lcm
a1 = (a1 + m1 (diff x % (m2 // gcd))) % m1
return a1
示例：物不知数
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
print(chinese_remainder_theorem([(2, 3), (3, 5), (2, 7)]))
〓 总结〓
通过对孙子定理的例题讲解，我们可以看到，这不仅是一个古老的数学谜题，更是一个强大的数学工具。从《孙子算经》的“物不知数”到现代密码学的基石，中国剩余定理展现了数学跨越千年的生命力。掌握其解题步骤，特别是逆元的计算和模数互质的判断，是解决此类问题的关键。希望本文的详解能帮助大家彻底攻克这一难点。