可除性：水壶问题的终审判决
Divisibilitya | b（a 整除 b）定义为存在整数 k 使 ak = b。它一出场就带来惊喜——第六章那两把水壶，现在有了终审判决。回忆：Die Hard 3 用 3/5 壶能凑 4 加仑；换 12/18 壶凑 4 加仑、899/1147 壶凑 32 加仑则必死。为什么？
水壶引理 9.1.6：壶里的水量永远是 a、b 的线性组合（sa + tb，s、t 为整数）。推论 9.2.4：其实永远是 gcd(a, b) 的倍数。所以：
gcd(899, 1147) = 31，而 32 不是 31 的倍数 ⇒ 还是死
gcd(3, 5) = 1，而 4 是 1 的倍数 ⇒ 有救 ✓
判决器在此——输入任意两把壶和目标量：
欧几里得算法与 Pulverizer
Euclid's Algorithm & the Pulverizergcd 怎么算？两千三百年前欧几里得就知道：gcd(a, b) = gcd(b, rem(a, b))——反复碾压，余数归零时的 x 就是 gcd。把它形式化成状态机 (x, y) → (y, rem(x, y))：gcd 是保持不变量（引理 9.2.1），x 每两步至少减半 ⇒ 至多 1 + 2log a 步终止。第六章的不变量原理 + 良序原理在此双剑合璧。
而 Pulverizer（粉碎机，公元六世纪印度人叫它 kuttaka）在欧几里得的骨架上加了一层簿记，反推出 gcd(a, b) = sa + tb（定理 9.2.2）。例如 gcd(259, 70) = 7 = 3·259 − 11·70。这看似平凡的等式是整个 RSA 的地基：
9.2.3水壶完全解
用容量 a、b 的壶，能在 a 壶中凑出 c ⟺ c 是 gcd(a, b) 的倍数。策略甚至不需要知道系数：反复"灌满小壶 → 全倒入大壶（满了就倒空大壶）"，gcd 的每个倍数都会依次出现。
素数之谜
Prime Mysteries素数是数论的明星，也是未解问题的重灾区：
孪生素数猜想：使 p、p+2 皆为素数的 p 有无穷多。（1966 年陈景润证明了"几乎"：p+2 至多是两个素数之积。）
分解难：给 n = pq（p、q 为大素数），没有已知的多项式时间算法还原 p、q——目前最快是数域筛，300 位以上即不可行。
哥德巴赫猜想：大于 2 的偶数都是两素数之和——第一章的老朋友了。
但也有铁律：素数定理 π(n) ~ n/ln n（每 ln n 个数里约 1 个素数），切比雪夫给了初等下界 π(n) > n/(3 ln n)。2004 年 Google 的招聘广告牌"e 中连续数字的第一个 10 位素数 .com"——答案 7427466391 出现得很早，正是这条密度的胜利。
算术基本定理
The Fundamental Theorem of Arithmetic每个正整数都是唯一一个弱递减素数序列的乘积。例：75237393 = 23·17·17·11·7·7·7·3，别无他法。
定理 2.3.1 证过"存在性"（良序），现在证"唯一性"：反设存在两种分解的最小整数 n，比较两个素数序列的首项，用引理 9.4.2（p 素且 p | ab ⇒ p | a 或 p | b）导出矛盾。注意引理 9.4.2 本身用 gcd 线性组合证明——刻意绕开唯一分解，避免循环论证。顺带一提：唯一分解在复数域的 n + m√−5（m、n 取遍 ℤ，互相独立）整数里会失效——它根本不是“显然”的。
Alan Turing 与图灵密码 1.0
Alan Turing24 岁那年（1936 年——比第一台电子计算机还早整整十年），图灵写下《论可计算数及其在判定问题上的应用》：用纯数学建模"计算机"，并立刻证明了存在任何计算机都解决不了的问题——无论程序员多聪明。"判定问题"（Entscheidungsproblem）是 Hilbert 1900 年列的 28 个数学问题之一，被他顺手解决；你听说过的"Church–Turing 论题"？同一篇论文。
1937 年秋，希特勒重整军备，世界大战在即。图灵和英国人一样忧心：他预见到军事通信保密将是胜负手，提出用数论加密通信。这个念头一路反弹到我们这个时代——今天数论是公钥密码、数字签名、哈希与电子支付的地基，军方也确实是密码学研究最大的金主之一。Sorry, Hardy！
先把消息翻译成整数：A = 01, B = 02, …；"victory" → 22 09 03 20 15 18 25。规则要求 m 本身是素数——素数定理保证末尾补几位数字即可（这里补 13：m = 2209032015182513 是素数）。
事先：收发双方共享一个大素数 k 作密钥。加密：m̂ ::= m · k。解密：m̂ / k = m。
原书例子：k = 22801763489 时，m̂ = 2209032015182513 · 22801763489 = 50369825549820718594667857。
两个基本问题：①怎么保证 m、k 是素数？朴素试除到 ⌊√n⌋ 要跑指数级步数；1974 年 Strassen 发明了快速概率素性检验——素数必判对，合数只有小概率误判，错率比"硬件自己出错"还低；2002 年 Agrawal–Kayal–Saxena 用 13 行给出了多项式时间的确定性检验（次数从 12 降到 5，但实践中仍用更快的概率检验）。②安全吗？纳粹只看得见 m̂ = m·k，想还原 m 就得分解 m̂——"分解没有高效算法"是被普遍接受的猜想。图灵把"计算的极限"这个发现直接变成了武器。
但 1.0 有死刑级破绽（9.5.2）：同一密钥发第二条消息，纳粹手里就有 m̂₁ = m₁·k 与 m̂₂ = m₂·k——gcd(m̂₁, m̂₂) 就是密钥 k，而 gcd 用欧几里得算法眨眼算完。第二条消息发出之日，全部通信沦陷。图灵这样的头脑不太可能漏掉这么显眼的问题——他心中的系统多半建在模算术上（9.8 节的 2.0 版再会）。亲手引爆它：
模算术：高斯的同余
Modular Arithmetic高斯在《算术研究》（Disquisitiones Arithmeticae）的第一页就引入了"同余"：a ≡ b (mod n) ⟺ n | (a − b)。例：29 ≡ 15 (mod 7)，因为 7 | (29 − 15)。从此约定模数 n > 1。
同余与余数是同一枚硬币的两面——余数引理 9.6.1：a ≡ b (mod n) ⟺ rem(a, n) = rem(b, n)（带余除法 a = q₁n + r₁、b = q₂n + r₂ 相减，r₁ − r₂ ∈ (−n, n) 中 n 的倍数只有 0）。所以 29 ≡ 15 (mod 7) 也可以这样看：rem(29, 7) = 1 = rem(15, 7)。由此立刻得到：同余是等价关系（引理 9.6.2：自反/对称/传递——第十章细说），把整数划分成 n 个剩余类（mod 3 就分成 ≡0、≡1、≡2 三类）；以及推论 9.6.3：a ≡ rem(a, n) (mod n)。
若 a ≡ b 且 c ≡ d (mod n)，则 a + c ≡ b + d 且 a·c ≡ b·d (mod n)。
同余与加减乘"兼容"——这条其貌不扬的引理是下一节"余数算术"的全部发动机。
余数算术与环 ℤₙ
Remainder Arithmetic & the Ring ℤₙ求一串加减乘除 n 的余数：① 每个操作数先换成它除 n 的余数；② 每步结果一旦越出 [0..n) 立即取余——整个计算永远只碰小数字。
看原书的巨兽（式 9.9）：rem((444273456789 + 155558585555)·4036666666, 36)。444273456789 写出来约有 2000 万位十进制数字，硬算绝望。但 rem(44427, 36) = 3、rem(15555858, 36) = 6、rem(403, 36) = 7，巨兽瞬间缩成 (33456789 + 65555)·76666666。再看幂的循环：3 的幂的余数 3, 9, 27, 9, 27, …（从 3² 起两步一循环），3456789 是 ≥ 3 的奇数 ⇒ 33456789 ≡ 27；6² ≡ 0，之后全是 0 ⇒ 65555 ≡ 0；7 的幂六步一循环且 rem(7⁶, 36) = 1 ⇒ 76666666 = (7⁶)1111111 ≡ 1。总计 (27 + 0)·1 = 27。
9.7.1 把这套把戏升级为代数：i +ₙ j ::= rem(i + j, n)，i ·ₙ j ::= rem(i·j, n)。[0..n) 配上 +ₙ、·ₙ 就是环 ℤₙ（引理 9.7.1 保证每步取余与先算再取余一致）。结合律、交换律、分配律、0 与 1 单位元、加法逆元 −k 全部照旧——"余数算术很像普通算术"，但有两个例外马上登场（9.9 的消去律）。
图灵密码 2.0 与乘法逆
Turing's Code v2.0 & Multiplicative Inverses1940 年法国沦陷，英国独抗纳粹，补给全靠美国船队跨北大西洋——与德国 U-boat 潜艇的猫鼠游戏，胜负系于信息：谁能更准地定位对方？德国输了。关键原因直到 1974 年才公开：Enigma 早被波兰密码局攻破，1939 年入侵波兰前几周转交英国；图灵 1939 年加入布莱切利园（Bletchley Park），成为 Enigma 快速批量解密方法的首席开发者（英国政府 1996 年才公开全部细节）。
也许 1.0 的思路没错（消息乘密钥），错的只是用了普通算术而非模算术。Version 2.0：公开大模数 n，秘密素数 k < n；加密 m̂ ::= m·k (ℤₙ)。解密呢？（Uh-oh.）m̂ 是 mk 除 n 的余数——"除以 k"的结果连整数都不一定是。什么时候在 ℤₙ 里能"除"？答案是乘法逆。
有理数里除 0 外每个数都有逆（3 的逆是 1/3）；整数里只有 ±1 有。ℤ₁₅ 里 2·8 = 1——8 是 2 的逆；而 3 无逆：若 3·j = 1 (ℤ₁₅)，两边乘 5 得 5 = 5·(3·j) = (5·3)·j = 0·j = 0——矛盾。判据是互素（9.9.1）：gcd(8, 15) = 1 有逆，gcd(3, 15) = 3 没有。引理 9.9.1：k 与 n 互素 ⇒ Pulverizer 给出 sn + tk = 1 ⇒ rem(t, n) 就是 k 的逆；引理 9.9.2：逆若存在必唯一（i = i·1 = i·(k·j) = (i·k)·j = 1·j = j）。
消去律也在这里触礁（9.9.2 小节）：3·10 = 3·5 (ℤ₁₅)，消去 3 会推出 10 = 5 的荒谬结论——不能消去公因子，是 ℤₙ 与普通算术最显著的不同。好消息：有逆 ⇒ 可消去（引理 9.9.4，两边乘上逆元即可）。总结成三位一体：
对 k ∈ [0..n)：gcd(k, n) = 1 ⟺ k 在 ℤₙ 中有乘法逆 ⟺ k 可消去。
例：ℤ₁₅ 中 2·8 = 1（8 是 2 的逆）；3 与 15 不互素 ⇒ 3 无逆（否则 5 = 0）。逆存在时唯一，且可用 Pulverizer 直接算出 rem(t, n)。
于是 2.0 的解密落地（9.9.3）：m̂·j = (m·k)·j = m·(k·j) = m·1 = m (ℤₙ)，j 是 k 的逆，Pulverizer 秒算；保证互素的省事办法是 n 取素数——ℤₚ 中每个非零元都有逆，像有理数一样舒服。
然而 2.0 也被破了（9.9.4）：德军嫌天气报告无关紧要，不加密封发，却又从 U-boat 用 Enigma 把同一份报告发了一遍——盟军拿明文密文一比对，当日密钥直接推出来（known-plaintext 攻击，1941 年大西洋战局的英军关键优势）。同一招对 2.0 绝杀：知道一组明文 m 与密文 m̂ = m·k (ℤₙ)，用 Pulverizer 求 m 的逆 j，则 j·m̂ = k (ℤₙ)——密钥又泄露了，2.0 没有实用价值。好在图灵后来的密码学造诣远超这个早期构想：他的 Enigma 破译即便没拯救整个英国，也至少拯救了成千上万条生命。
欧拉定理
Euler's Theoremφ(n) ::= [0..n) 中与 n 互素的整数个数（φ(7) = 6，φ(12) = 4，φ(300) = 80）。
欧拉定理：gcd(k, n) = 1 ⇒ k^φ(n) ≡ 1 (mod n)。
特例：p 素时 φ(p) = p − 1，得 Fermat 小定理 k^(p−1) ≡ 1 (mod p)。素数幂 φ(pᵏ) = pᵏ − pᵏ⁻¹；φ(pq) = (p−1)(q−1)。
证明是 ℤₙ*（与 n 互素的剩余类之集）上的一个漂亮 pigeonhole：k ∈ ℤₙ* 时 k·ℤₙ* = ℤₙ*（乘 k 只是重排），于是 (k·c₁)(k·c₂)⋯ = (c₁)(c₂)⋯，消去得 k^φ(n) = 1。另一路求逆：k 的逆 = k^(φ(n)−1)，可用第六章的快速幂高效计算。
RSA 公钥加密
RSA Public Key Encryption1977 年，MIT 的 Rivest、Shamir、Adleman 把 Turing 的遗愿做成了现实：公钥加密。接收者生成两个数百位的大素数 p、q，公开 (e, n := pq)，私藏 d := e 在 ℤ₍ₚ₋₁₎₍q₋₁₎ 中的逆。任何人都能用公钥加密 m̂ ::= mᵉ (ℤₙ)，只有持有 d 的人能解密 m ::= m̂ᵈ——因为 e·d ≡ 1 (mod φ(n))，欧拉定理保证 m̂ᵈ = m。安全性押在"分解 n 为 p·q 是难事"这条未证猜想上——四十余年全球攻击无果。
下面是真的 RSA（玩具尺寸）。选素数、发消息，走一遍完整流程：
9.12SAT 与 RSA 的命运
为什么相信 RSA 安全？知道 p、q 就能像接收者一样用 Pulverizer 求出 d；反过来，知道私钥和公钥也同样容易分解 n（习题 9.83）——所以"从公钥反推私钥"与"分解 n"同等困难。但这并不能排除绕过私钥直接解密的可能："任何破解 RSA 的方法都蕴含分解能力"仍是密码学重要的未证猜想。真正的信心来源很朴素：40 多年来全球最顶尖的密码学家轮番攻击，无一得手——数学界、金融界、情报界都把家当押在了上面。
与 SAT 的关联（3.5 节的悬念在此回收）：数字电路 ⇔ 命题公式，电路可满足性就是 SAT。造一台"乘积检验器"电路：4n 根输入线（n 位的 i、n 位的 j、2n 位的 k），输出 1 ⟺ ij = k 且 i, j > 1，约 n² 个门即可实现。分解 2n 位的 m：把 k 的输入固定为 m，然后逐位敲定 i——第 1 位试置 1，问 SAT 求解器"剩余输入可满足吗"，可满足就定 1，否则定 0；依此逐位推进，n 次 SAT 调用后 i 的完整二进制表示到手，j = m / i。结论：SAT 若有多项式（d 次）算法，分解 2n 位数就是 d + 1 次多项式——RSA 应声而破。这就是"SAT 高效求解之日，全社会密码崩盘之时"的完整链条。
习题实战：费马检验与小定理
9.9 & FLT, Playable9.9 的 Turing/费马素性检验做成互动器，再用两道模算术快题收尾。
终局自测
Final Check八题，覆盖全章。
彩蛋与课后挑战
Easter Eggs & ProblemsHardy 的乌鸦与 Turing 的苹果（原书章首引言 / 9.9.5 Turing Postscript）
数论学家 Hardy 曾庆幸数论"因远离军事而洁净"，还担心它被用于战争——他错了两次：数论是现代密码学的地基，而图灵（Turing's Code 的构想者）后来在布莱切利园领衔破解 Enigma，拯救了无数生命。图灵本人的结局则令人心碎：因同性恋被定罪、接受"化学治疗"，1954 年死于氰化物与一只苹果——他的母亲至死相信那是意外。2009 年英国政府正式道歉，2013 年女王赦免。
Google 的素数广告牌（原书 9.4 节文框）
2004 年美国多地的广告牌写着："{first 10-digit prime found in consecutive digits of e}.com"。解出 7427466391 就能到达 Google 的招聘页。素数定理保证 10 位数中约每 ln(10¹⁰) ≈ 23 个就有一个素数——所以这题其实不难，难的是想到用素数定理。Google 要雇的正是"会想到"的人。
完美数与黎曼假设（原书 9.1 / 9.9.5 末尾）
毕达哥拉斯学派的"完美数"（等于自身真因子之和：6 = 1+2+3, 28 = 1+2+4+7+14）——欧几里得刻画的都是偶完美数，奇完美数存在吗？两千三百年无解，已排除至 10¹⁵⁰⁰。另一边，Riemann 假设把素数分布写进 ζ 函数的零点——千禧年七大难题之一，同样悬赏百万美元。素数density的每一个转角都通向深渊。
课后挑战（均出自原书习题）
- 9.2 用偶完美数的欧几里得刻画（2^(k−1))(2^k − 1)，2^k − 1 为素数）自己找几个完美数。
- 8.10 把 Schröder-Bernstein 定理的构造双射补完（第八章伏笔回收）。
- 9.14 证明欧几里得算法至多 log_φ(a) 步（φ 是黄金比）——斐波那契最坏情形。
- 9.81 证明即使 m 与 n 不互素，RSA 解密依然还原 m（欧拉定理之外的补充论证）。