孙子定理训练题500题-孙子定理题 500 改写｜中国剩余定理实战精讲

从零入门到精通：系统讲解孙子定理（中国剩余定理）的数学原理、解题模型、高频考点与改写策略，配套500道原创训练题与真题解析，助你攻克模运算难关，提升数论思维与竞赛/考研实战能力。

立即开始学习

什么是孙子定理？——不只是古题，更是现代数学的基石

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”——《孙子算经》卷下第二十六题

? 名称由来

该定理由中国古代数学名著《孙子算经》首次系统记载，西方称其为“Chinese Remainder Theorem”（中国剩余定理）。它并非仅适用于中国，而是人类共有的数学遗产。

在公元3世纪的中国，此题已给出通用解法，比欧洲同类研究早1200余年。

? 本质定义

孙子定理（即中国剩余定理）研究的是：当模数两两互质时，同余方程组是否存在唯一解（模乘积）。

形式化表述：若 m₁, m₂, ..., mₖ 是两两互质的正整数，则对任意整数 a₁, a₂, ..., aₖ，同余方程组

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
⋮
x ≡ aₖ (mod mₖ)

在模 M = m₁m₂…mₖ 下有唯一解。

? 为什么重要？

✓ 基础数学竞赛（如CMO、IMO）高频考点
✓ 考研数学（数论、代数）必考内容
✓ 计算机科学（密码学、哈希算法、并行计算）底层支撑
✓ 日常生活（日历推算、周期问题、分组设计）实用工具

? 真实案例：《孙子算经》原题求解

题目：物不知数——三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

即：x ≡ 2 (mod 3)，x ≡ 3 (mod 5)，x ≡ 2 (mod 7)

解法思路：
① 计算 M = 3×5×7 = 105
② 分别求 M₁=35, M₂=21, M₃=15
③ 求逆元：35⁻¹ mod 3 = 2（因35×2=70≡1 mod 3）
21⁻¹ mod 5 = 1（21≡1 mod 5）
15⁻¹ mod 7 = 1（15≡1 mod 7）
④ 组合解：x = 2×35×2 + 3×21×1 + 2×15×1 = 140 + 63 + 30 = 233
⑤ 取最小正解：233 mod 105 = 23

答案：23（最小正整数解，通解为 23 + 105k, k∈Z）

别被公式吓退——孙子定理训练题500题-孙子定理题 500 改写系列将带你层层深入，从最简情形到复杂变形，掌握“降维打击”的数学思维。

核心原理精解——从互质到构造解

理解原理是解题的前提。本部分深入剖析孙子定理的数学逻辑，澄清常见误区。

互质条件解析

构造解法步骤

推广形式（非互质情形）

互质条件：为什么必须两两互质？

两两互质（pairwise coprime）指任意两个模数的最大公约数为1，即 gcd(mᵢ, mⱼ) = 1（i ≠ j）。

若不满足互质，解可能不存在或不唯一。例如：

例：x ≡ 1 (mod 2)，x ≡ 2 (mod 4)

第一个式子 ⇒ x 为奇数；第二个式子 ⇒ x = 4k+2 = 偶数 ⇒ 矛盾！
无解。

而若改为 x ≡ 1 (mod 2)，x ≡ 3 (mod 4)，则 x=3,7,11,... 是解（模4唯一）。

关键结论：孙子定理的“唯一解”是模 M = ∏mᵢ 的唯一，前提是模数两两互质。

构造解法三步法

标准解法（适用于两两互质情形）：

求总模数：M = m₁ × m₂ × ⋯ × mₖ
分块求余：对每个 i，令 Mᵢ = M / mᵢ
求逆元：找 yᵢ 使得 Mᵢ·yᵢ ≡ 1 (mod mᵢ)（即 Mᵢ 在模 mᵢ 下的乘法逆元）
组合解：x₀ = Σ aᵢ·Mᵢ·yᵢ，最小正解为 x₀ mod M

例：解 x ≡ 1 (mod 2)，x ≡ 1 (mod 3)，x ≡ 1 (mod 5)，x ≡ 1 (mod 7)

M = 2×3×5×7 = 210
M₁=105, M₂=70, M₃=42, M₄=30
105⁻¹ mod 2 = 1（105奇数）
70⁻¹ mod 3 = 1（70≡1 mod 3）
42⁻¹ mod 5 = 3（42×3=126≡1 mod 5）
30⁻¹ mod 7 = 4（30×4=120≡1 mod 7）
x₀ = 1×105×1 + 1×70×1 + 1×42×3 + 1×30×4 = 105+70+126+120 = 421
x = 421 mod 210 = 1

发现规律？当所有 aᵢ 相等时，解为 x ≡ a (mod M)，即最小正解就是 a（若 a < M）！

非互质情形：扩展孙子定理

当模数不互质时，孙子定理可推广为：

同余方程组 x ≡ aᵢ (mod mᵢ) 有解 ⇔ 对任意 i,j，有 aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ))

解存在时，可逐步合并方程：

例：x ≡ 2 (mod 4)，x ≡ 4 (mod 6)

检查：gcd(4,6)=2；2 ≡ 4 (mod 2)？→ 2 mod 2 = 0，4 mod 2 = 0 ⇒ 成立！
合并：设 x = 4k + 2，代入第二式：4k+2 ≡ 4 (mod 6) ⇒ 4k ≡ 2 (mod 6) ⇒ 2k ≡ 1 (mod 3) ⇒ k ≡ 2 (mod 3)
⇒ k = 3t + 2 ⇒ x = 4(3t+2)+2 = 12t + 10
通解：x ≡ 10 (mod 12)

虽然复杂，但可通过扩展欧几里得算法编程实现——这也是现代密码系统的基础。

理解原理后，孙子定理训练题500题-孙子定理题 500 改写的训练将事半功倍。切记：“互质是钥匙，构造是路径，逆元是核心”。

经典例题精讲——从简单到复杂

精选5道典型题，覆盖孙子定理常见题型与变形，每题附详细解析与易错点提示。

例1：标准四元组

求最小正整数 x，满足：
x ≡ 2 (mod 3)，x ≡ 3 (mod 5)，x ≡ 2 (mod 7)

解析：即《孙子算经》原题，M=105，解为23。

技巧：观察余数与模数关系：2=3−1，3=5−2，2=7−5 → 无直接规律，仍用标准法。

例2：余数等于模数减1

x ≡ 1 (mod 2)，x ≡ 2 (mod 3)，x ≡ 4 (mod 5)，x ≡ 6 (mod 7)

观察：所有余数 = 模数 − 1 ⇒ x+1 是 2,3,5,7 的公倍数 ⇒ x+1 = LCM(2,3,5,7)=210 ⇒ x=209

结论：此类题无需复杂计算，直接找最小公倍数！

例3：重复余数合并

x ≡ 1 (mod 2)，x ≡ 1 (mod 3)，x ≡ 2 (mod 5)，x ≡ 3 (mod 7)

优化：前两式合并：x ≡ 1 (mod 6)（因2,3互质）
现解：x ≡ 1 (mod 6)，x ≡ 2 (mod 5)，x ≡ 3 (mod 7)
M=210，M₁=35, M₂=42, M₃=30
逆元：35⁻¹ mod 6=5（35×5=175≡1），42⁻¹ mod 5=3（126≡1），30⁻¹ mod 7=4（120≡1）
x₀=1×35×5 + 2×42×3 + 3×30×4 = 175+252+360=787
x=787 mod 210=157

例4：大数简化（模运算性质）

求 2¹⁰⁰ mod 105（即除以3、5、7的余数）

策略：分别算 mod 3、mod 5、mod 7，再用孙子定理组合

¹⁰⁰ mod 3：2≡−1 ⇒ (−1)¹⁰⁰=1
¹⁰⁰ mod 5：φ(5)=4，100÷4=25 ⇒ 2¹⁰⁰≡1
¹⁰⁰ mod 7：φ(7)=6，100=6×16+4 ⇒ 2⁴=16≡2

即：x≡1 (mod 3)，x≡1 (mod 5)，x≡2 (mod 7)

合并前两式：x≡1 (mod 15)，再与第三式联立 ⇒ x=15k+1，代入：15k+1≡2 (mod 7) ⇒ k≡2 (mod 7) ⇒ k=7t+2 ⇒ x=105t+31

答案：2¹⁰⁰ mod 105 = 31

例5：密码学应用（RSA简化版）

在RSA中，若模数 n = p×q（p,q为质数），解密时需计算 m = cᵈ mod n。

利用孙子定理，可分别算：

mₚ = cᵈ mod p
m_q = cᵈ mod q

再合并得 m mod n，计算速度提升4倍（因模数减半）！

实际案例：p=11, q=13 ⇒ n=143；c=8, d=103
m₁₁ = 8¹⁰³ mod 11 = (8¹⁰)¹⁰ × 8³ ≡ 1¹⁰ × 512 mod 11 = 512 mod 11 = 6
m₁₃ = 8¹⁰³ mod 13 = (8¹²)⁸ × 8⁷ ≡ 1⁸ × (8⁶×8) mod 13 = (1×8) mod 13 = 8
解：x≡6 (mod 11)，x≡8 (mod 13) ⇒ x=19

以上例题均来自孙子定理训练题500题-孙子定理题 500 改写题库精选，每道题均经过命题组反复打磨，覆盖初、中、高三级难度。

训练题库说明｜500题系统训练计划

基于“基础→进阶→竞赛”三级体系设计，配套答案与解析，支持按难度筛选。

? 题型分布

基础题（200题）：直接套用公式，巩固原理
变式题（180题）：余数规律、合并简化、大数简化
应用题（70题）：密码学、日历、分组设计
竞赛题（50题）：CMO/IMO风格，综合数论知识

? 改写策略

“孙子定理题 500 改写”并非简单替换数字，而是：

✓ 改模数组合（引入非互质变体）
✓ 改余数结构（对称、递增、周期）
✓ 改背景设定（结合编程、密码、生活）
✓ 增加隐藏条件（需先化简再解）

例：原题“三三数剩二”，改写为“某数被3除余2，被5除余3，被7除余2，且在200~300之间，求该数”——增加范围限制。

? 学习路径建议

第1周

掌握原理+完成50道基础题

第2周

突破变式+100道中等题

第3周

实战应用+80道综合题

第4周

冲刺竞赛+50道高难度题

? 随堂自测题（3道）

求最小正整数 x：x ≡ 3 (mod 4)，x ≡ 5 (mod 6)，x ≡ 7 (mod 8)（提示：先检查互质性）
⁵⁰ mod 105 = ?
某数被5除余2，被7除余3，被11除余4，求最小解。

孙子定理的历史演进｜从《孙子算经》到现代密码学

条跨越1700年的数学长河，见证中国智慧的全球回响。

公元3–5世纪

《孙子算经》成书，首次记载同余问题

卷下第二十六题：“物不知数”，给出“三人同行七十稀，五树梅花甘一枝，七子团圆正半月，除百零五便得知”的歌诀解法。

年

秦九韶《数书九章》完善算法

提出“大衍求一术”（即求一次同余方程组解法），比高斯早554年。书中“鬼谷算”“隔墙算”等题均属孙子定理应用。

年

拉格朗日研究同余理论

西方首次系统讨论，但未明确互质条件。

年

高斯《算术探究》正式命名

给出严格证明，称其为“Chinese Theorem”，奠定现代数论基础。

世纪至今

计算机科学中的核心工具

应用于RSA加密、FFT快速傅里叶变换（分治策略）、分布式计算中的模运算优化。

从古代算书到现代芯片，孙子定理训练题500题-孙子定理题 500 改写不仅是数学题，更是文明传承的密码。

孙子定理的现代应用｜不止于数学

它如何在你每天使用的手机、网络中默默工作？

? 密码学：RSA的幕后功臣

在RSA解密中，若 n = p×q，计算 cᵈ mod n 可拆为：

mₚ = cᵈ mod p
m_q = cᵈ mod q

再用孙子定理合并。因模数减半，运算量降至原来的 1/4，大幅提速。

行业标准：OpenSSL、Java Crypto 等均采用此优化。

? 日历计算：千年日期推算

求公元2099年12月31日是星期几？

已知2000年1月1日是星期六，计算间隔天数 mod 7。

但涉及闰年规则（4年一闰，百年不闰，四百年再闰），需分段模运算：

总年数：99年 ⇒ 24个闰年 + 75个平年 = 99×365 + 24 = 36135 天
mod 7 = ?

用孙子定理分解：36135 mod 7 = (36135 mod 3, mod 7) 组合 ⇒ 得余数 ⇒ 星期四。

? 算法优化：分治与哈希

快速傅里叶变换（FFT）：将长度为 n 的序列分解为偶/奇下标两部分，递归处理，本质是利用模运算分治。

分布式哈希表（DHT）：节点ID分配常采用模2ᵏ−1，避免冲突，需同余知识优化路由。

? 编程实践：Python 实现孙子定理

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b)  y
def crt(congruences):
    # congruences = [(a1, m1), (a2, m2), ...]
    x = 0
    M = 1
    for _, m in congruences:
        M = m
    for a, m in congruences:
        Mi = M // m
        _, inv, _ = extended_gcd(Mi, m)
        x += a  Mi  inv
    return x % M
# 示例：x≡2(mod3), x≡3(mod5), x≡2(mod7)
print(crt([(2,3), (3,5), (2,7)]))  # 输出：23

立即加入孙子定理训练题500题-孙子定理题 500 改写系统训练！

掌握中国剩余定理，解锁数论思维，成就数学高手！

返回开头，继续学习