L02 数论：一圈 n 格的表盘，和绕不回起点的那些步长

一句话版

这一讲把 RSA 要用的四样零件——GCD、模逆、欧拉定理、CRT——提前造好。

一个类比：一圈 n 格的表盘

52 页里没有一个支付场景，全是数论。想象一个刻了 n 格的表盘，所有运算都在它上面做。

取模就是把整个整数轴卷到这个表盘上。课件 p.5 那张数轴图画的正是这件事：a 夹在两个相邻的 n 倍数之间，r 是它超出下面那个倍数的距离，所以必然 0 ≤ r < n。同余则是两个数落在同一格：73 和 4 在模 23 的表盘上是同一格。往回走也一样要落进格子里——−11 mod 7 = 3，因为商必须取 ⌊−11/7⌋ = −2 而不是 −1。

加减乘可以随时先折回表盘再算，这就是 p.17 那三条性质：先取模还是后取模，结果落在同一格。除法不在这三条里，因为表盘上并非每个步长都能原路退回。把 p.19 那张模 8 乘法表按行看就明白了：步长 3 的倍数依次落在 3、6、1、4、7、2、5、0，踩遍全部八格并回到过 1；步长 2 只在 2、4、6、0 里打转，永远踩不到 1。能踩到 1 的那几个步长（1、3、5、7）恰好是与 8 互素的，它们才有乘法逆元。互素这个条件是本讲出现频率最高的东西，看到任何定理先找它。

类比在哪里失效：跳步这个图像只覆盖到加法和乘法，指数运算 a^k 已经跳出了它——费马小定理和欧拉定理那一段没法靠转表盘看出来，只能靠 p.32 的证明骨架。求 GCD 更不在单个表盘上，它比较的是两个长度、做的是辗转相除。CRT 要几个表盘同时读数，但表盘解释不了为什么模数必须两两互素，那要靠计数。最后，真实密码学用的模数是几百位，表盘根本画不出来；RSA 的安全性恰恰压在一件算不出来的事上——找大素数容易，分解大合数难。

概念卡

1. 欧几里得算法与 GCD

人话定义：gcd(a, b) 是同时整除 a 和 b 的最大整数。欧几里得算法把它从”分别分解质因数再取交集”变成一个只做取余的循环：GCD(p, q) = p if q = 0，否则 = GCD(q, p mod q)。

例子：p.13 的 Exercise-1，gcd(93, 16) 四行就到底，答案是圈出来的那个 1，即 93 与 16 互素。

p.12 更极端：a = 1160718174、b = 316258250 这两个十位数，十步就出 1078，而质因数分解是完全不同量级的工作量。

常见误解

不要死记取 a 还是 b：答案是最后一个非零余数。p.10 流程图终止位置对应 b；上面的递归写法在 q=0 时返回 p，变量名取决于实现。另一个常错点是 gcd(a, 0) = |a| 被当成可有可无的边界情况 → 它是整个递归的出口，没有它算法停不下来（p.7、p.10）。

2. 模运算的三条性质

人话定义：加、减、乘都可以随时先取模再运算，不必等大数算完才取模。

例子：p.17 的填空——211 mod 8 = 3，125 mod 8 = 5。于是 (211 + 125) mod 8 = (3 + 5) mod 8 = 0，(211 − 125) mod 8 = (3 − 5) mod 8 = 6，(211 × 125) mod 8 = 15 mod 8 = 7，三个都能用直接计算验回来。实用价值在 p.51 那道 20³⁷ mod 77：硬算 20³⁷ 是个 49 位数，逐步取模的话每步都在两位数范围内。

常见误解

把除法也算进去 → 三条里没有除法。模意义下的”除以 b”必须改写成”乘以 b⁻¹”，而 b⁻¹ 未必存在。减法那一问也常错：(3 − 5) = −2 之后还要再折回 [0, 8)，答案是 6（p.17）。

3. 模逆与扩展欧几里得

人话定义：若 a·x mod b = 1，称 x 是 a 模 b 的乘法逆元。存在性判据是双向的：a⁻¹ 存在 ⟺ gcd(a, b) = 1。求法靠 Bézout 恒等式 ax + by = gcd(a, b)，把”求模逆”翻译成”解整数方程”，再用扩展欧几里得机械地解出来。

例子：p.24–p.25 求 911⁻¹ mod 999，去程五行除法、回程五行回代，两趟都在同一张图上。

验算一次就放心：806 × 911 = 734266 = 735 × 999 + 1。

常见误解

算出负系数就交卷 → 模逆按惯例要落在 [0, n)，−193 还得补成 999 − 193 = 806。回代时丢减号也是高发错误，防法是每合并完一行抽查一次，比如 6 × 88 − 17 × 31 = 528 − 527 = 1，每行都必须等于 1（p.24、p.25）。

4. φ(n)、费马小定理与欧拉定理

人话定义：φ(n) 数的是与 n 互素的正整数个数。欧拉定理说 gcd(a, n) = 1 时 a^φ(n) ≡ 1 (mod n)；n 取素数 p 时 φ(p) = p − 1，它就退回费马小定理 a^(p−1) ≡ 1 (mod p)。

例子：三条计算公式——φ(p) = p − 1、φ(p^k) = p^k − p^(k−1)、φ(pq) = (p−1)(q−1)。第三条课件放在 p.49 让学生自己证，用数补集加容斥：1 到 pq 里 p 的倍数有 q 个、q 的倍数有 p 个、两者都是的只有 pq 自己 1 个，故 φ(pq) = pq − p − q + 1 = (p−1)(q−1)。p ≠ q 这个条件用在”两者都是的只有一个”那一步。p.31 那张模 19 的幂表是欧拉定理的可视化：最后一列 a¹⁸ 整列全是 1，没有例外。

常见误解

以为费马和欧拉要各背一套 → 只需记欧拉定理，费马是它的特例，两者的证明也共用一个骨架：乘一个可逆元不改变集合 → 取乘积 → 约掉阶乘。另外 φ 的可乘性 φ(mn) = φ(m)φ(n)（m、n 互素）课件没单列，但算 φ(36) = 12、φ(40) = 16 时非它不可（p.36、p.37）。

5. 中国剩余定理（CRT）

人话定义：给定一组两两互素的模数和各自的余数，在 0 ≤ x < N（N 为所有模数之积）范围内存在且只存在一个 x 同时满足全部同余式。课件把 “one and only one” 标成红色，同时断言存在性和唯一性。

例子：p.43 那道古题 x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7)。逐步代入：设 x = 3t + 2，代入第二式得 3t ≡ 1 (mod 5)，t ≡ 2 (mod 5)；设 t = 5s + 2 得 x = 15s + 8，代入第三式得 s ≡ 1 (mod 7)；最终 x = 105u + 23，而 105 = 3 × 5 × 7。《孫子算經》原文给的是另一条路——构造法：“三三數之賸二，置一百四十”就是 2 × 70，70 在模 3 下余 1 而被 5、7 整除，三项相加 233 再减去 210 得 23。

常见误解

把”两两互素”弱化成”整体互素” → 像 6、10、15 这种任意两个都不互素但三个的 gcd 是 1 的情形，不能直接套本讲模数乘积 N 下唯一解的版本。补充：非互素模数仍可能有解，需检查余数兼容性，解按模数最小公倍数描述。另一处是答案只写单个数 → CRT 给的是模 N 的唯一解，标准写法是 x ≡ 23 (mod 105)（p.42、p.43）。

把它们串起来

四个 Part 不是并列关系，分隔页上的箭头已经说明白了：整除推出 GCD、GCD 推出欧几里得算法；模运算推出模逆、模逆要靠扩展欧几里得；素数推出费马小定理、费马推广成欧拉定理；最后 CRT 负责把大数的模运算拆小。

它们在 RSA 那里汇合。生成密钥要两个大素数（p.28 的素数、p.29 的密度保证找得到），算 φ(n) 要 φ(pq) = (p−1)(q−1)（p.35、p.49），由 e 求 d 就是求模逆、用的是扩展欧几里得（p.24），而”加密再解密等于原文”这一步就是欧拉定理形式二的一次代入：ed = kφ(n) + 1，于是 m^(ed) = (m^φ(n))^k × m ≡ m (mod n)。CRT 则是工程加速——知道 p、q 就能分头在模 p 和模 q 下算再合并，这叫 RSA-CRT。

安全性也压在同一堆结论上：知道 p、q 能秒算 φ(n)，只知道 n 就得先分解。找大素数容易、分解大合数难，这个不对称就是 RSA 的立身之本。

课件里的坑

• [口径差异] 课件 p.4 把除法算法的条件写成「n 为正整数、a 为非负整数」→ a 取负数时结论照样成立，只要坚持 0 ≤ r < n；p.15 的 −11 mod 7 马上就要用到这一点（p.4）
• [口径差异] 课件 p.30 在费马小定理形式二后面也加了 “(not divisible by p)” → 这个限制对形式二是多余的，a^p ≡ a (mod p) 对所有整数 a 都成立，包括 p | a 的情况（此时两边都 ≡ 0）（p.30）
• [口径差异] 课件 p.34 的表里 φ(1) = 1，与同页定义「小于 n 且与 n 互素」在 n = 1 这一个点上对不上 → 表里的值是通行约定，该松的是那句定义（标准写法是「不超过 n」，即 1 ≤ k ≤ n）；n > 1 时两种说法结果相同。Stallings 原书就是这么写的，不是本课件的笔误（p.34）
• [适用条件] p.37 开头已明确 a、n 互素；第二式沿用此前提，两边乘 a 即得。不要删除条件后再判课件错误。补充：RSA 的不同素数乘积模数可用 CRT 扩展到非互素消息。
• [课件留白] 课件 p.32 费马小定理的证明页只有标题和定理陈述，正文空着 → 证明是当堂在黑板上推的，期末闭卷，这类页最值得自己补一份（p.32）
• [课件有误] 课件 p.15 的 ⌊a/n⌋ 在导出时乱码成了别的字形 → 就是向下取整（p.15）

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——模逆存在的充要条件、Bézout 回代求系数的路线、CRT 的两个前提；再把下面的「变式题」做一遍；最后回查两个最容易错的地方——算出负系数就交卷、把「两两互素」弱化成「整体互素」。三步做完再往下看答案。

必背

1. 除法算法 a = qn + r，0 ≤ r < n，q = ⌊a/n⌋ 是全讲地基；负数取模要折回 [0, n)：−11 mod 7 = 3 而不是 −4。
2. gcd(a, 0) = |a| 是欧几里得递归的出口；算法的答案是最后一个非零余数；互素 ≠ 两个都是素数（8 与 15 都是合数但互素）。
3. 模运算三性质里只有加、减、乘能先取模，没有除法；模意义下的除法必须改写成乘以模逆。
4. 模逆存在 ⟺ gcd(a, b) = 1；Z₈ 里只有 1、3、5、7 可逆，且各自是自己的逆元。
5. Bézout 恒等式 ax + by = gcd(a, b)；扩展欧几里得手算三步：正向跑除法 → 逐行回代 → 负系数折回正数。
6. φ(p) = p − 1，φ(p^k) = p^k − p^(k−1)，φ(pq) = (p−1)(q−1)（p ≠ q 为素数）；可乘性 φ(mn) = φ(m)φ(n) 要求 m、n 互素。
7. 费马小定理 a^(p−1) ≡ 1 (mod p)（p ∤ a）是欧拉定理 a^φ(n) ≡ 1 (mod n)（gcd(a, n) = 1）的特例；形式二 a^(φ(n)+1) ≡ a (mod n) 就是 RSA 解密正确性。
8. CRT 两个前提缺一不可：模数两两互素、解限定在 0 ≤ x < N；答案要写成 x ≡ x₀ (mod N) 而不是单个数。

完整例题

期末闭卷，这一讲的考法全是”给你两个数，当场跑一遍算法”。下面两题一道练模板，一道练综合。

(1) 27 模 392 的逆元存在吗？存在就求出来（p.48 Exercise-8）

1. 先按 p.22 的判据算 GCD，同时也是在为回代备料：392 = 14 × 27 + 14，27 = 1 × 14 + 13，14 = 1 × 13 + 1，13 = 13 × 1 + 0，得 gcd(27, 392) = 1，逆元存在。
2. 逐行回代，每次把式子里最老的余数用上一行换掉：1 = 14 − 13 = 14 − (27 − 14) = 2 × 14 − 27 = 2 × (392 − 14 × 27) − 27 = 2 × 392 − 29 × 27。
3. 于是 1 = (−29) × 27 + 2 × 392，取 27 那一侧的系数 −29。
4. 负系数折回正数：−29 ≡ 392 − 29 = 363 (mod 392)。
5. 验算：27 × 363 = 9801 = 25 × 392 + 1 ✓。
6. 建议展示三段推导（也可使用等价的正确方法）：判存在（算 GCD）→ 求系数（回代）→ 折正并验算。题面故意问”或说明为什么不能”，考的就是那条充要判据；如果 gcd ≠ 1，正确答案是”不存在，因为两数不互素”，不是硬算。

(2) 用 CRT 计算 20³⁷ mod 77（p.51 Exercise-11）

1. 拆模数：77 = 7 × 11，两者互素，符合 CRT 前提。
2. 模 7 这一路：20 ≡ 6 ≡ −1 (mod 7)，故 20³⁷ ≡ (−1)³⁷ = −1 ≡ 6 (mod 7)。
3. 模 11 这一路：20 ≡ 9 ≡ −2 (mod 11)，φ(11) = 10，用欧拉定理降指数，37 mod 10 = 7，故 20³⁷ ≡ (−2)⁷ = −128；128 = 11 × 11 + 7，所以 −128 ≡ −7 ≡ 4 (mod 11)。
4. 合并 x ≡ 6 (mod 7)、x ≡ 4 (mod 11)：设 x = 11k + 4，代入得 11k + 4 ≡ 6 (mod 7)，即 4k ≡ 2 (mod 7)，解出 k ≡ 4 (mod 7)（4 × 4 = 16 ≡ 2 ✓）。
5. 设 k = 7m + 4，得 x = 77m + 48，即 20³⁷ ≡ 48 (mod 77)。验算 48 mod 7 = 6 ✓、48 mod 11 = 4 ✓。
6. 这一道把四个 Part 全用上了：素数分解、欧拉定理降指数、解模逆、CRT 合并。它演示的也正是第四个分隔页说的那件事——直接算 20³⁷ 是个 49 位数，拆开后每一步都在两位数范围内。

变式题（先自己做）

同样两道，数字换掉：

(1) 求 17 模 120 的逆元，或说明为什么不存在。 (2) 用 CRT 计算 3¹⁰⁰ mod 35。

提示

第一题的 GCD 一步就除完了，别因为除得太快而跳过”判存在”那句话。第二题拆完模数以后，两边的指数都还是 100，先想想用什么把它降下来。

参考答案与自检（非官方评分标准）

自检要点：① 逆元题三段缺一不可——判存在、回代求系数、折正并验算；② CRT 题两路都必须用欧拉定理降指数，优先用定理简化而非逐次硬乘；③ 合并后要回代验算两个同余式。

(1) 120 = 7 × 17 + 1，17 = 17 × 1 + 0，故 gcd(17, 120) = 1，逆元存在。回代只有一行：1 = 120 − 7 × 17，取 17 那一侧的系数 −7，折正得 120 − 7 = 113。验算 17 × 113 = 1921 = 16 × 120 + 1 ✓。

(2) 35 = 5 × 7，互素，可用 CRT。

• 模 5：φ(5) = 4，100 mod 4 = 0，故 3¹⁰⁰ = (3⁴)²⁵ ≡ 1 (mod 5)。
• 模 7：φ(7) = 6，100 = 6 × 16 + 4，故 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7)。
• 合并：设 x = 7k + 4，代入 7k + 4 ≡ 1 (mod 5)，即 2k ≡ 2 (mod 5)，解出 k ≡ 1 (mod 5)。设 k = 5m + 1，得 x = 35m + 11，即 3¹⁰⁰ ≡ 11 (mod 35)。
• 验算：11 mod 5 = 1 ✓、11 mod 7 = 4 ✓。

闪卡自测

1. −11 mod 7 等于多少？为什么商取 −2 而不是 −1？

等于 3。要满足 0 ≤ r < 7 只能取 q = ⌊−11/7⌋ = −2，于是 −11 = (−2) × 7 + 3。C/Java/JavaScript 的 % 对负数返回 −4，与数学定义不一致，Python 的才一致（p.15）。

2. 欧几里得算法终止时答案取 a 还是 b？为什么？

看停止条件。p.10 的流程图取 b；标准 while b≠0: (a,b)←(b,a mod b) 退出时则取 a。两者都返回最后一个非零余数。

3. 8 和 15 都不是素数，它们互素吗？

互素。8 的因子是 1、2、4、8，15 的是 1、3、5、15，公共因子只有 1。互素说的是两数没有大于 1 的公因子，跟它们各自是不是素数无关（p.8）。

4. 模运算的三条性质是什么？为什么其中没有除法？

加、减、乘三种运算都满足「先取模再算 = 先算再取模」。除法不在其中，因为模意义下的除法要改写成乘模逆，而模逆未必存在（p.17、p.22）。

5. 在 Z₈ 的乘法表里哪些元素有乘法逆元？为什么是这几个？

只有 1、3、5、7，而且各自是自己的逆元（3 × 3 = 9 ≡ 1，5 × 5 = 25 ≡ 1，7 × 7 = 49 ≡ 1）。它们恰好是与 8 互素的那些。2、4、6 所在的行整行没有 1，还出现 2 × 4 = 0 这样的零因子（p.19、p.20）。

6. 模逆存在的充要条件是什么？8 模 14 的逆元为什么不存在？

充要条件是 gcd(a, b) = 1。gcd(8, 14) = 2 ≠ 1，所以逆元不存在。这条判据是双向的：反过来”逆元存在”也立刻给出两数互素（p.22）。

7. 手算 16⁻¹ mod 93。

正向：93 = 5 × 16 + 13，16 = 1 × 13 + 3，13 = 4 × 3 + 1，gcd = 1。回代：1 = 13 − 4 × 3 = 5 × 13 − 4 × 16 = 5 × 93 − 29 × 16。故 16⁻¹ ≡ −29 ≡ 93 − 29 = 64。验算 16 × 64 = 1024 = 11 × 93 + 1 ✓（p.26）。

8. 什么是一个元素模 p 的「阶」？模 19 下 7 的阶是多少？

阶是使 a^k ≡ 1 的最小正整数 k。7³ = 343 = 18 × 19 + 1，所以 7 的阶是 3；18 = 3 × 6，于是 7¹⁸ = (7³)⁶ ≡ 1。模 19 下阶恰为 18 的六个数 2、3、10、13、14、15 是原根（p.31、p.33）。

9. 计算 φ(36) 和 φ(40)，说明各用了哪条性质。

36 = 2² × 3²，φ(36) = (4 − 2) × (9 − 3) = 2 × 6 = 12；40 = 2³ × 5，φ(40) = (8 − 4) × 4 = 16。流水线是先分解质因数，再对每个素数幂套 φ(p^k) = p^k − p^(k−1)，最后用可乘性乘起来（p.35、p.36）。

10. 证明 p ≠ q 为素数时 φ(pq) = (p−1)(q−1)。p ≠ q 用在哪一步？

1 到 pq 中与 pq 不互素的是含因子 p 或 q 的数：p 的倍数 q 个、q 的倍数 p 个、两者都是的只有 pq 自己 1 个，容斥得 φ(pq) = pq − p − q + 1 = (p−1)(q−1)。p ≠ q 用在”两者都是的只有一个”这一步；若 p = q，φ(p²) = p² − p ≠ (p−1)²（p.49）。

11. 用欧拉定理算 7¹³⁴ mod 26，写出三步。

① 验互素：gcd(7, 26) = 1 ✓。② 算 φ：26 = 2 × 13，φ(26) = 1 × 12 = 12，故 7¹² ≡ 1。③ 降指数：134 = 11 × 12 + 2，7¹³⁴ ≡ 7² = 49 ≡ 23 (mod 26)（p.50）。

12. 如果只能记一个定理，为什么该记欧拉定理？

因为费马小定理是它的特例：n 取素数 p 时 φ(p) = p − 1，欧拉定理立刻退回 a^(p−1) ≡ 1 (mod p)。课件自己的总结页也把欧拉放在上层、费马放在下层（p.30、p.37、p.45）。

下一讲

下一讲 Cryptography 会把这四样零件当作已知条件直接调用，RSA 的密钥生成和解密正确性都不会再推一遍。