数论专题 · 课件

中国剩余定理

算

Chinese Remainder Theorem · 又称「孙子定理」

从《孙子算经》的「物不知数」说起——一个 1700 年前的问题,如何长成了现代数学与信息技术的基石。

按 → 或点击右下角按钮翻页

01 · 历史背景

从《孙子算经》出发

今有物不知其数

三三数之剩二,

五五数之剩三,

七七数之剩二,

问物几何?

——《孙子算经》卷下(约公元 3–5 世纪)

这是世界上最早的同余方程组问题,原文给出的答案是 二十三。
南宋 秦九韶《数书九章》(1247)提出「大衍总数术」,给出了系统化的算法。
明代 程大位《算法统宗》(1592)以口诀形式让它在民间广为流传(见下一页)。
西方直到 1801 年高斯《算术研究》才系统论述——因而它也被称为「孙子定理」。

02 · 数学翻译

「物不知数」的数学翻译

每句话翻译成一个同余式

三三数之剩二→x ≡ 2 (mod 3)
五五数之剩三→x ≡ 3 (mod 5)
七七数之剩二→x ≡ 2 (mod 7)

得到同余方程组

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

「问物几何」⇔ 求满足以上全部条件的最小正整数 x。

03 · 古法口诀

口诀里的构造思想

三人同行七十稀,五树梅花廿一支,
七子团圆正半月,除百零五便得知。

—— 明 · 程大位《算法统宗》(1592)

70

「三」的余数 × 70
70 ≡ 1 (mod 3);70 ≡ 0 (mod 5)、0 (mod 7)

21

「五」的余数 × 21
21 ≡ 1 (mod 5);21 ≡ 0 (mod 3)、0 (mod 7)

15

「七」的余数 × 15
15 ≡ 1 (mod 7);15 ≡ 0 (mod 3)、0 (mod 5)

04 · 定理陈述

中国剩余定理(孙子定理)

设 m1, m2, …, mk 两两互素(即 gcd(mi, mj) = 1,i ≠ j)。则对任意整数 a1, a2, …, ak,下列同余方程组恰有一个模 M = m1m2⋯mk 的解:

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
x ≡ ak (mod mk)

「恰有一个模 M 的解」:全部解构成一个同余类 x ≡ x0 (mod M)。

直观理解:模 M 的「大世界」可以拆成若干互不干扰的「小世界」(mod mi)——数论版的「分而治之」。

05 · 构造性证明

先「造」一个解出来

1
记 M = m1m2⋯mk,并令 Mi = M / mi(即去掉第 i 个模数后,其余模数之积)。
2
因模数两两互素,故 gcd(Mi, mi) = 1,于是存在 模逆元 ti,满足 Miti ≡ 1 (mod mi)。
3
按下面的公式组合出候选解:

x0 = a1M1t1 + a2M2t2 + ⋯ + akMktk

关键观察:乘上 Mi 之后,这一项只对自己的模数「可见」,对其余模数都「隐身」(≡ 0)。

06 · 验证与唯一性

验证成立,而且唯一

① 验证:每一项各管一个方程

当 j ≠ i 时,因 mi | Mj,故第 j 项 ajMjtj ≡ 0 (mod mi);

于是只剩第 i 项:x0 ≡ aiMiti ≡ ai·1 = ai (mod mi)。

第 i 个方程恰好被满足 ✓

② 唯一性:两个解之差必是 M 的倍数

设 x 与 x′ 都是解,则对每个 i 都有 mi | (x − x′);

而模数两两互素,故乘积也整除:m1m2⋯mk | (x − x′),即 x ≡ x′ (mod M)。

07 · 例题一

例一:物不知数

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

M = 3×5×7 = 105,M1 = 35,M2 = 21,M3 = 15。

求逆元:35t1 ≡ 2t1 ≡ 1 (mod 3) ⇒ t1 = 2;21t2 ≡ t2 ≡ 1 (mod 5) ⇒ t2 = 1;15t3 ≡ t3 ≡ 1 (mod 7) ⇒ t3 = 1。

imiaiMi = M / mitiaiMiti
132352140
25321163
37215130
x0 = 140 + 63 + 30 = 233 ≡ 23 (mod 105)

最小正整数解 x = 23,通解 x = 23 + 105n(n ∈ ℤ)。检验:23 = 3×7+2 = 5×4+3 = 7×3+2 ✓

08 · 例题二

例二:韩信点兵

韩信点兵:三人一排余一人,五人一排余四人,七人一排余二人。

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

模数与上一题相同,可沿用:M = 105,M1 = 35(t1 = 2),M2 = 21(t2 = 1),M3 = 15(t3 = 1)。

x0 = 1×70 + 4×21 + 2×15 = 70 + 84 + 30 = 184 ≡ 79 (mod 105)

最少兵数 x = 79;若再知 150 < x < 250,则唯一确定 x = 184。检验:79 = 3×26+1 = 5×15+4 = 7×11+2 ✓

09 · 一般情形

模数不必互素的推广

判别与唯一性:方程组有解 ⟺ 对任意 i ≠ j,gcd(mi, mj) | (ai − aj);有解时,解在模 lcm(m1, …, mk) 意义下唯一。

方法:两两合并

先把前两个方程合并成一个模 lcm(m1, m2) 的方程(过程中用一次扩展欧几里得),再与第三个合并,依次进行。

例:x ≡ 1 (mod 4),x ≡ 3 (mod 6)

gcd(4, 6) = 2,且 2 | (3 − 1) ⇒ 有解;合并得 x ≡ 9 (mod 12)。

9 = 4×2+1 = 6×1+3 ✓,全部解:9 + 12n

互素只是「最好用」的情形;相容性判别给出了更一般的存在性条件。

10 · 应用

它在哪里大显身手?

🧮

计算数学

大整数乘法、线性方程组分别取多个小模数计算,再用 CRT 合并重组,显著提速。

🔐

密码学

RSA 解密用 CRT 加速(约 4 倍);Asmuth–Bloom 门限秘密共享亦以其为基础。

📡

编码与容错

纠错码与冗余编码的经典构造工具之一。

🧭

抽象代数

理想互素时 R/(I∩J) ≅ R/I × R/J——CRT 在现代代数中的化身。

🏛️

历法与天文

古代求「上元积年」就是解同余方程组;秦九韶「大衍术」正为此而生。

🎯

周期问题

多个周期叠加时的最小同步点,本质是在解同余方程组。

11 · 小结

小结与练一练

① 条件

模数两两互素;更一般的情形需要满足相容性判别。

② 公式

x ≡ Σ aiMiti (mod M),其中 ti 是 Mi 的模逆元。

③ 结构

解在模 M 意义下唯一;大模问题可拆成小模问题。

练一练

1. 解同余方程组 x ≡ 1 (mod 3),x ≡ 2 (mod 5),x ≡ 3 (mod 7)。

查看答案

M1 = 35,t1 = 2;M2 = 21,t2 = 1;M3 = 15,t3 = 1 ⇒ x0 = 1×70 + 2×21 + 3×15 = 157 ≡ 52 (mod 105)。

2. 思考:x ≡ 0 (mod 2) 与 x ≡ 1 (mod 4) 为什么无解?

查看答案

x ≡ 1 (mod 4) ⇒ x 必为奇数,与 x ≡ 0 (mod 2) 矛盾;用判别法看:gcd(2, 4) = 2,而 2 不整除 a1 − a2 = 1 − 0。

END

谢 谢

试着用中国剩余定理,解决一个属于你的「物不知数」。

参考:《孙子算经》《数书九章》《算法统宗》· 高斯《算术研究》

1 / 13