Lecture 5: Euclid, FLT, CRT（欧几里得算法、费马小定理、中国剩余定理）

目录 · ← l5 · l7 →

Lecture 5: Euclid, FLT, CRT（欧几里得算法、费马小定理、中国剩余定理）

概述

本讲把 Lecture 4 留下的三笔账一次结清，并补齐模运算的全部工具链。核心问题有三个：(1) 怎么高效地算 $\gcd(x,y)$，并顺带求出 Bézout 系数 $a,b$ 使 $ax+by=\gcd(x,y)$——由此得到求模逆元的算法；(2) 整数的质因数分解为什么存在且唯一（算术基本定理）；(3) 一组同余方程何时有唯一解、如何构造（中国剩余定理）。最后证明费马小定理，它刻画了「模质数下幂运算的周期性」，是 Lecture 6 RSA 解密正确性的直接依据。证明技巧上，本讲的主线是强归纳 + 构造性证明 + 双射计数。

核心概念的直观解释

最大公约数（Greatest Common Divisor, gcd）

• 定义：对自然数 $x,y$（不全为 $0$），$\gcd(x,y)$ 是同时整除 $x$ 与 $y$ 的最大正整数。若 $\gcd(x,y)=1$，称 $x$ 与 $y$ 互质 (relatively prime / coprime)。
• 直观解释：「用同一把尺子同时量尽两根棍子，这把尺子最长能多长」。更一般地，$\gcd$ 是「两个数的公共度量单位」——这正是欧几里得算法最初的工程背景：把设计图的长度按比例放大时，需要找到能同时整除所有尺寸的长度单位。
• 具体示例：$\gcd(30,24)=6$（$30=2\cdot3\cdot5$，$24=2^3\cdot 3$，公共部分 $2\cdot 3=6$）；$\gcd(16,10)=2$；$\gcd(35,12)=1$（$35=5\cdot7$，$12=2^2\cdot3$ 无公共因子）。约定 $\gcd(x,0)=x$，因为 $0$ 被任何数整除。
• 注意区分：$\gcd$ 取公共因子的最大者，$\operatorname{lcm}$（最小公倍数）取公共倍数的最小者。两者满足 $\gcd(x,y)\cdot\operatorname{lcm}(x,y)=xy$。

Bézout 等式与 Bézout 系数（Bézout’s Identity）

• 定义：设 $d=\gcd(x,y)$。存在整数 $a,b$（可正可负可零）使

这里的 $a,b$ 称为 Bézout 系数 (Bézout coefficients)。注意这是普通的整数等式，不是同余式。

• 直观解释：$\gcd$ 不只是「公共因子的最大值」，它还是所有形如 $ax+by$ 的整数组合中最小的那个正数。换句话说，我们要的不是「找最大公因子」，而是「用 $x$ 和 $y$ 的整数线性组合去凑出尽可能小的正数」——能凑出的最小正数恰好就是 $\gcd$。这正是扩展欧几里得算法（以及它更直观的「列等式相减」手工版本）的设计动机。
• 具体示例：$1 = \gcd(35,12) = (-1)\cdot 35 + 3\cdot 12$，所以 $a=-1,b=3$ 是一组合法的 Bézout 系数。又如 $2 = \gcd(16,10) = 2\cdot 16 + (-3)\cdot 10$。

扩展欧几里得算法（Extended Euclid’s Algorithm）

• 定义：在欧几里得算法「反复做带余除法」的基础上，在递归回溯 (unwinding) 时同步维护系数，使每次返回都满足 $d = a x + b y$。
• 直观解释：欧几里得算法告诉你「$d$ 是多少」，扩展版额外告诉你「$d$ 怎么用 $x,y$ 拼出来」。它之所以能顺手做到，是因为带余除法本身就是一次线性组合的初等变换：$x \bmod y = x - \lfloor x/y\rfloor \cdot y$。
• 具体示例：$x=35,\ y=12$，算法返回 $(d,a,b) = (1,-1,3)$，验证 $-1\cdot 35 + 3\cdot 12 = -35+36 = 1$ ✔。因为 $d=1$，从这里立刻读出 $3\cdot 12 \equiv 1 \pmod{35}$，即 $12^{-1} \equiv 3 \pmod{35}$。

算术基本定理（Fundamental Theorem of Arithmetic, FTA）

• 定义：每个正整数 $n>1$ 都可以写成质数之积 $n = p_1p_2\cdots p_k$，且这种写法在不计次序的意义下唯一。
• 直观解释：质数是整数的「化学元素」——每个整数都有唯一的「分子式」。存在性（每个数都能分解）靠强归纳（Lecture 3）；唯一性（分解不会有两种本质不同的结果）靠欧几里得算法的推论（本讲）。这是一个很深的联系：整除的唯一性来源于带余除法的唯一性。
• 具体示例：$12 = 2\cdot2\cdot3$，任何其他分解都只是 $2,2,3$ 的重排（如 $2\cdot 3\cdot 2$、$3\cdot 2\cdot 2$）。$360 = 2^3\cdot 3^2 \cdot 5$ 是唯一分解。

中国剩余定理（Chinese Remainder Theorem, CRT）

• 定义：设 $n_1,\dots,n_k$ 两两互质，$N = \prod_{i=1}^k n_i$。则对任意给定的 $a_1,\dots,a_k$，同余方程组

在模 $N$ 下有唯一解。其构造式为

该定理最早见于公元 3 世纪中国数学家孙子（Sunzi）的著作，故得名。

• 直观解释（坐标视角）：把「一个数 $x$ 模 $N$」想象成「一个 $k$ 维向量 $(x \bmod n_1, \dots, x \bmod n_k)$」。CRT 说这个对应是双射 (bijection)：模 $N$ 的每个数对应唯一一个「坐标组」，反之亦然。而每个 $b_i$ 就是第 $i$ 个坐标轴上的基向量 (basis vector)——它在自己的方向上是 $1$（即 $b_i \equiv 1 \pmod{n_i}$），在所有其他方向上都是 $0$（即 $b_i \equiv 0 \pmod{n_j}$，$j\neq i$）。于是要组装出目标向量 $(a_1,\dots,a_k)$，只需令 $x = \sum_i a_i b_i$ 即可。
• 具体示例：「今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二」即 $x \equiv 2 \pmod 3$、$x \equiv 3 \pmod 5$、$x \equiv 2 \pmod 7$。取 $N=105$，解得 $x = 23$（验算见下文）。$23$ 在 $[0,104]$ 内是唯一解，通解为 $23 + 105t$。

费马小定理（Fermat’s Little Theorem, FLT）

• 定义：设 $p$ 是质数，$a \in \{1,2,\dots,p-1\}$（等价地：$\gcd(a,p)=1$）。则

等价形式：对任意整数 $a$，$a^{p} \equiv a \pmod p$（这个形式不要求 $\gcd(a,p)=1$）。

• 直观解释：在模质数 $p$ 的乘法世界里，任何非零元素的幂都是周期性的，而且这个周期总是 $p-1$ 的因子（不一定恰为 $p-1$，例如模 $11$ 时 $7$ 的周期是 $10$，而 $10^2 = 100 \equiv 1$ 的周期是 $2$）。FLT 就是把 Lecture 4 的乘法表「每一行都是排列」这一观察乘积化的结果。
• 具体示例：$p=11,\ a=2$：$2^{10} = 1024 = 93\cdot 11 + 1$，故 $2^{10} \equiv 1 \pmod{11}$ ✔。$p=7,\ a=3$：$3^{6} = 729 = 104\cdot 7 + 1$，故 $3^6 \equiv 1 \pmod 7$ ✔。
• 条件不可省的反例：取 $m=4$（合数）、$a=2$。$m-1=3$，而 $2^{3} = 8 \equiv 0 \pmod 4 \neq 1$。所以「$a^{m-1}\equiv 1 \pmod m$」对合数 $m$ 一般不成立，FLT 的「$p$ 是质数」这一条无法删除。

模逆元的三种求法（本讲串联总结）

完整证明与推导（核心）

定理 6.1（欧几里得算法的不变量）：设 $x \ge y > 0$，则

证明策略：集合相等法（直接证明）。不直接比较两个「最大数」，而是证明两个公约数集合完全相同——既然集合相同，其最大元素当然相同。这是处理 $\gcd$ 类命题的标准降维手法：把「最大」这个序性质转化为「集合相等」这个逻辑性质。证明需要两个方向：正向与反向各用一次「整除的线性封闭性」（$d\mid u \wedge d\mid v \Rightarrow d \mid (u\pm v)$，来自 Lecture 0）。

逐步推导：

1. 设 $x = qy + r$，其中 $q = \lfloor x/y \rfloor$ 是整数，$r = x \bmod y$ 满足 $0 \le r < y$。（依据：带余除法的存在唯一性。）
2. （$\Rightarrow$ 方向） 设 $d$ 是 $x$ 与 $y$ 的任一公约数，即 $d \mid x$、$d \mid y$。
3. 由 $d \mid y$ 得 $d \mid qy$。（依据：若 $d$ 整除某数，则整除其任意整数倍。）
4. 由 $d \mid x$ 且 $d \mid qy$，得 $d \mid (x - qy)$，即 $d \mid r$。（依据：Lecture 0 的整除线性性。）
5. 于是 $d$ 同时整除 $y$ 与 $r$，即 $d$ 是 $y$ 与 $x \bmod y$ 的公约数。
6. （$\Leftarrow$ 方向） 反过来，设 $d$ 是 $y$ 与 $r$ 的任一公约数，即 $d \mid y$、$d \mid r$。
7. 由 $d \mid y$ 得 $d \mid qy$（同上）。
8. 由 $d \mid qy$ 且 $d \mid r$，得 $d \mid (qy + r)$，即 $d \mid x$。（依据：整除线性性 + $x = qy + r$。）
9. 于是 $d$ 同时整除 $x$ 与 $y$，即 $d$ 是 $x$ 与 $y$ 的公约数。
10. 步骤 2–5 与 6–9 合起来说明：$\{x,y\}$ 的公约数集合 $= \{y, x\bmod y\}$ 的公约数集合。
11. 两个相等的正整数集合当然有相同的最大元素，故 $\gcd(x,y) = \gcd(y, x\bmod y)$。$\blacksquare$

【证明机制解说】：整个证明的「灵光一现」在第 4 步——把 $r$ 写成 $x - qy$。这一步把「余数」这个看似只能通过除法定义的对象，翻译成了 $x$ 与 $y$ 的整数线性组合，于是「整除封闭性」这把万能钥匙就能插入锁孔。反向（第 8 步）用的是同一个组合的加法形式 $x = qy + r$。两个方向合起来才叫「公约数集合相同」：只证一个方向，只能得到集合包含关系，无法推出最大元相等。这个「互推对称性」是本讲后续所有证明（包括 Bézout 等式）的骨架。

具体算例（官方 Note 6 的 gcd 序列）：

  gcd(16, 10)
    = gcd(10, 16 mod 10 = 6)      16 = 1*10 + 6
    = gcd( 6, 10 mod  6 = 4)      10 = 1*6  + 4
    = gcd( 4,  6 mod  4 = 2)       6 = 1*4  + 2
    = gcd( 2,  4 mod  2 = 0)       4 = 2*2  + 0
    = 2                           第二个参数为 0，返回第一个参数

  另一例（Fibonacci 型最坏情形）:
  gcd(1071, 462)
    = gcd(462, 1071 mod 462 = 147)    1071 = 2*462 + 147
    = gcd(147,  462 mod 147 =  21)     462 = 3*147 +  21
    = gcd( 21,  147 mod  21 =   0)     147 = 7*21  +   0
    = 21

算法（递归形式）：

  algorithm gcd(x, y)          // 要求 x >= y >= 0, x > 0
      if y = 0 then return(x)
      else return(gcd(y, x mod y))

定理 6.2（欧几里得算法的正确性）：上述算法对任意满足 $x \ge y \ge 0$、$x>0$ 的自然数输入，都正确返回 $\gcd(x,y)$。

证明策略：对第二个参数 $y$ 做强归纳（Lecture 3）。之所以选 $y$ 而不是 $x$：递归调用是 $\gcd(y, x \bmod y)$，它的第二个参数是 $x \bmod y$，而定理 6.1 保证了 $x \bmod y < y$——归纳变量严格递减的方向正好由算法自身保证。之所以用强归纳而非普通归纳：递归调用一次就从 $y$ 跳到 $x \bmod y$，中间可能跨过很多值，普通归纳的假设（只覆盖 $y-1$）不够用。

逐步推导：

1. 对每个 $y \ge 0$ 定义命题 $P(y)$：对所有满足 $x \ge y$ 且 $x>0$ 的整数 $x$，算法 gcd(x,y) 正确返回 $\gcd(x,y)$。
2. 基础情形 $y=0$：算法走 if 分支返回 $x$。而 $\gcd(x,0) = x$（$0$ 被一切数整除，故公约数集合就是 $x$ 的因子集合，最大者为 $x$），且输入要求 $x>0$ 保证 $x$ 是合法返回值。故 $P(0)$ 成立。
3. 归纳假设：设 $y>0$，并假设 $P(z)$ 对所有 $0 \le z < y$ 成立。
4. 归纳步骤：$y>0$，算法走 else 分支，返回 gcd(y, x mod y)。
5. 令 $r = x \bmod y$。由带余除法 $0 \le r < y$，故 $r$ 落在归纳假设的覆盖范围内。
6. 检查递归调用的输入合法性：调用 gcd(y, r) 要求「第一个参数 $\ge$ 第二个」且「第一个参数 $>0$」。由 $r < y$ 得 $y \ge r$ ✔；由 $y>0$ 得第一个参数为正 ✔。故归纳假设 $P(r)$ 适用（取该命题中的「$x$」为 $y$）。
7. 于是递归调用正确返回 $\gcd(y,r) = \gcd(y, x\bmod y)$。
8. 由定理 6.1，$\gcd(y, x \bmod y) = \gcd(x,y)$。
9. 所以 else 分支返回的值等于 $\gcd(x,y)$，$P(y)$ 成立。
10. 由强归纳原理，$P(y)$ 对所有 $y\ge0$ 成立，算法正确。$\blacksquare$

【证明机制解说】：这个正确性证明有一个特别优雅的地方：算法与证明是同一件事的两种语言。算法通过「把 $(x,y)$ 换成 $(y, x\bmod y)$」让数值下降；证明通过「把 $P(y)$ 换成 $P(x\bmod y)$」让归纳变量下降。定理 6.1 保证两者的下降终点一致（第二个参数为 $0$）。这类「递归算法 + 强归纳正确性」的组合模式在 CS70 里反复出现：Lecture 3 的汉诺塔、Lecture 6 的模幂、Lecture 11 的 Gale-Shapley 终止性都同构。请特别注意第 6 步——检查递归调用的输入是否满足算法前提，这是很多学生写正确性证明时漏掉的一环；漏了它，归纳假设就无从落地。

定理 6.3（欧几里得算法复杂度：$O(\log x)$ 次递归调用）：

命题：在 $\gcd(x,y)$ 的计算中，每两次递归调用，第一个（较大的）参数至少缩小一半。

证明策略：分情形讨论（case analysis）。直接证明「一次调用就减半」是假的（反例：$x=100, y=99$ 时第一次调用后第一个参数变成 $99$，几乎没减），所以必须看两步。分界点选在 $y$ 与 $x/2$ 的大小关系上。

逐步推导：

1. 考虑调用 $\gcd(x,y)$，其中 $x \ge y \ge 0$，$x>0$。
2. 情形 1：$y \le x/2$。
3. 第一次递归调用是 $\gcd(y, x \bmod y)$，其第一个参数为 $y$，已满足 $y \le x/2$。
4. 第二次递归调用将其变成 $\gcd(x \bmod y,\ y \bmod (x \bmod y))$，第一个参数为 $x \bmod y < y \le x/2$。
5. 故两次调用后第一个参数 $< x/2$。（严格来说，一次调用后就已 $<x$ 至少缩半。）
6. 情形 2：$x \ge y > x/2$。
7. 此时 $x = 1\cdot y + (x-y)$，故 $x \bmod y = x - y$。（依据：因为 $y > x/2 > 0$ 且 $x<2y$，商的整数部分只能是 $1$。）
8. 于是 $x \bmod y = x - y < x - x/2 = x/2$。（依据：$y > x/2$。）
9. 第一次递归调用 $\gcd(y, x\bmod y)$ 的第一个参数是 $y < x$；第二次递归调用 $\gcd(x\bmod y, \cdot)$ 的第一个参数是 $x \bmod y < x/2$。
10. 故两次调用后第一个参数 $< x/2$。
11. 两种情形都给出「每两次调用第一个参数减半」。
12. 设 $n$ 为 $x$ 的比特数，即 $x < 2^n$。每两次调用使第一个参数至少除以 $2$，故至多 $2n$ 次调用后第一个参数变为 $0$，递归终止（第一个参数始终是非负整数，不可能无限减半）。
13. 每次调用只做一次整数比较和一次 mod 运算，在「算术运算计为常数时间」的模型下，总代价为 $O(n) = O(\log x)$。$\blacksquare$

反例（说明为什么必须看两步）：取 $x=1000,\ y=999$。第一次调用得到 $\gcd(999, 1)$，第一个参数从 $1000$ 只降到 $999$——几乎没减。但再看一步：$\gcd(1, 0)$，第一个参数降到 $1 < 500$。所以「单步减半」为假，「两步减半」为真。这个「最坏情形」正是相邻 Fibonacci 数对：递归次数最少下降模式的极端例子，可证明调用次数约为 $\log_\varphi x$（$\varphi$ 为黄金比），与我们的 $O(\log x)$ 上界一致。

【证明机制解说】：情形 2 的关键推理是「$y > x/2$ 迫使商为 $1$，从而余数就是差值 $x-y$」。这是一个把「取值范围假设」转化为「具体代数表达式」的典型技巧：一旦写出 $x \bmod y = x - y$，减半的结论就一目了然。请体会这里的分界点为什么选 $x/2$ 而不是别的：若 $y \le x/2$，减半来自 $y$ 本身；若 $y > x/2$，减半来自 $x-y$。两条路保证无论 $y$ 落在哪个区间，两步内必减半。 这种「互补区间覆盖」是算法分析中最常见的分情形设计。

扩展欧几里得算法（Extended Euclid）

目标：求三元组 $(d,a,b)$ 使 $d = \gcd(x,y)$ 且 $d = a x + b y$。

  algorithm extended-gcd(x, y)        // 要求 x >= y >= 0, x > 0
      if y = 0 then return (x, 1, 0)          // 基础情形: d = x = 1*x + 0*y
      else
          (d, a, b) := extended-gcd(y, x mod y)
          return (d, b, a - (x div y) * b)    // 关键回代公式

为什么这个回代公式是对的？（推导）

1. 递归调用返回 $(d,a,b)$，满足

1. 把恒等式 $x \bmod y = x - \lfloor x/y \rfloor\, y$ 代入 (5.1)：

1. 展开并按 $x,y$ 重新合并同类项：

1. 我们希望返回 $d = A x + B y$。对照 (5.2) 中 $x$ 与 $y$ 的系数，只需取

1. 这正是算法最后一行 return (d, b, a - (x div y) * b) ——公式不是猜出来的，是把 $x \bmod y$ 展开后比对系数得到的。 $\square$

定理 6.4（扩展欧几里得算法的正确性）：对任意 $x \ge y \ge 0$、$x>0$，extended-gcd(x,y) 返回 $(d,a,b)$ 且 $d = \gcd(x,y)$、$d = ax+by$。

证明策略：对 $y$ 做强归纳，与定理 6.2 完全同构。第一部分（$d$ 的正确性）直接借用定理 6.1/6.2；第二部分（系数的正确性）用上面的代数推导。

逐步推导：

1. 命题 $Q(y)$：对一切满足 $x \ge y$、$x>0$ 的 $x$，extended-gcd(x,y) 返回 $(d,a,b)$ 满足 $d=\gcd(x,y)$ 且 $d=ax+by$。
2. 基础情形 $y=0$：返回 $(x,1,0)$。$d = x = \gcd(x,0)$ ✔，且 $1\cdot x + 0\cdot 0 = x = d$ ✔。$Q(0)$ 成立。
3. 归纳假设：设 $y>0$，$Q(z)$ 对所有 $0\le z<y$ 成立。
4. 归纳步骤：算法递归调用 extended-gcd(y, x mod y)。令 $r = x\bmod y$，则 $0\le r<y$ 且 $y\ge r$、$y>0$，输入合法，由 $Q(r)$ 得返回 $(d,a,b)$ 满足

1. $d$ 的部分：由定理 6.1，$\gcd(y,r)=\gcd(x,y)$，故 $d = \gcd(x,y)$ ✔。
2. 系数的部分：由第 4 步的 $d = ay+br$ 与 $r = x - \lfloor x/y\rfloor y$，代入展开得

1. 取 $A=b$、$B = a-\lfloor x/y\rfloor b$，则 $d = Ax + By$ ✔，恰是算法返回的后两个分量。
2. 故 $Q(y)$ 成立；由强归纳，$Q(y)$ 对所有 $y\ge0$ 成立。$\blacksquare$

完整手算算例 1：$x=16,\ y=10$（官方 Note 6 的例子）

先记录每一步的商 $q = \lfloor x/y\rfloor$：

回溯过程（每一步用 $A=b,\ B=a-qb$）：

最终返回 $(d,a,b) = (2,2,-3)$，即 $2 = 2\cdot16 - 3\cdot10$。因为 $\gcd(16,10)=2\neq1$，这里不能读出逆元（$10$ 模 $16$ 不可逆）。

完整手算算例 2：$x=35,\ y=12$（读出逆元）

回溯：

返回 $(d,a,b) = (1,-1,3)$，即 $1 = (-1)\cdot35 + 3\cdot12$。由此读出：$3\cdot 12 \equiv 1 \pmod{35}$，所以 $12^{-1} \equiv 3 \pmod{35}$。（脚本验算 $3\cdot12 = 36 = 35+1 \equiv 1$ ✔）

完整手算算例 3：$x=1071,\ y=462$（大一点的数，读不出逆元）

回溯：$(21,1,0) \to (21,0,1) \to (21,1,-3) \to (21,-3,7)$。

最终 $21 = (-3)\cdot 1071 + 7\cdot 462$。验算：$7\cdot462 = 3234$，$3\cdot1071 = 3213$，$3234-3213 = 21$ ✔。（脚本验算通过。）$\gcd(1071,462)=21 \neq 1$，故 $462$ 模 $1071$ 不可逆。

  扩展欧几里得「手工列等式相减版」（无需递归，更适合手算）
  目标：找 x,y 的整数组合等于 gcd。从一个显然的等式出发，不断相减：

    x = 1071, y = 462
    ( 1)*1071 + ( 0)*462 = 1071        <- 等式 A
    ( 0)*1071 + ( 1)*462 =  462        <- 等式 B
    A - 2B: ( 1)*1071 + (-2)*462 =  147    (1071 - 2*462 = 147)
    B - 3*(上式): (-3)*1071 + (7)*462 =  21    (462 - 3*147 = 21)
                  ^^^^^^^^^^^^^^^^^^^^ 右边 = 21 = gcd  --> 停

  系数变化 (1,-2) 再 (-3,7) 与递归版完全一致；每一步右端就是余数序列。

用扩展欧几里得求模逆元（算法与算例）

方法：要求 $x^{-1} \bmod m$（前提 $\gcd(x,m)=1$），运行 extended-gcd(m, x) 得到

对两边取模 $m$：$a m \equiv 0$，故 $b x \equiv 1 \pmod m$，即

（若 $b$ 为负，加上若干个 $m$ 使其落入 $\{0,\dots,m-1\}$。）

算例 A：求 $12^{-1} \bmod 35$。上面已算出 $1 = (-1)\cdot35 + 3\cdot12$，故 $x^{-1} \equiv 3 \pmod{35}$。

算例 B：解 $8x \equiv 9 \pmod{15}$（官方 Note 6 例子）。先求 $8^{-1} \bmod 15$：注意 $2\cdot 8 = 16 = 15+1 \equiv 1$，故 $8^{-1}\equiv 2$。两边乘 $2$：$x \equiv 18 \equiv 3 \pmod{15}$。验算：$8\cdot 3 = 24 = 15+9 \equiv 9$ ✔。解唯一模 $15$。

算例 C：解 $5x \equiv 7 \pmod{11}$。$\gcd(5,11)=1$，逆元存在。由 $9\cdot 5 = 45 = 4\cdot 11 + 1$，得 $5^{-1}\equiv 9$。故 $x \equiv 7\cdot 9 = 63 = 5\cdot11+8 \equiv 8 \pmod{11}$。验算：$5\cdot8 = 40 = 3\cdot11+7 \equiv 7$ ✔。（脚本验算通过。）

算例 D：$2^{-1} \bmod 9$。$5\cdot2 = 10 = 9+1 \equiv 1$，故 $2^{-1}\equiv5$。验算 $2\cdot5=10\equiv1$ ✔。对照：$2^{-1}\bmod 4$ 不存在，因为 $\gcd(2,4)=2>1$。

算术基本定理（Fundamental Theorem of Arithmetic）

先证明一个关键引理（官方 Note 6 的 Claim），它是唯一性证明的唯一工具。

引理 6.5（欧几里得引理 / 互质消因子）：设 $x,y,z$ 为正整数且 $\gcd(x,y)=1$。若 $x \mid yz$，则 $x \mid z$。

证明策略：构造性证明 + 直接证明。把「互质」升级为「存在 Bézout 系数」，于是可以把 $z$ 写成两项之和，而这两项都被 $x$ 整除。选这个策略是因为：「互质」本身只给了一个否定性信息（没有大于 1 的公因子），无法直接用；扩展欧几里得把它变成了肯定性的等式 $1 = ax+by$，从此可做代数操作。

逐步推导：

1. 由 $\gcd(x,y)=1$ 及扩展欧几里得算法（定理 6.4，取 $x\ge y$ 的情形；若 $y>x$ 则调换角色），存在整数 $a,b$ 使

1. 两边同乘 $z$：

1. $x \mid axz$：因为 $axz = x\cdot(az)$，而 $az$ 是整数。
2. $x \mid byz$：由假设 $x \mid yz$，而 $byz = b\cdot(yz)$ 是 $yz$ 的整数倍。
3. 由整除线性性（Lecture 0），$x \mid (axz + byz)$。
4. 由式 (5.3)，$axz+byz = z$，故 $x \mid z$。$\blacksquare$

【证明机制解说】：这个引理是整个数论里「把不可操作的条件变成可操作的等式」的典范。它的全部力量来自 Bézout 系数：一旦 $1$ 被表示成 $x,y$ 的组合，乘上 $z$ 后 $z$ 就被劈成两半，其中一半显然被 $x$ 整除（$axz$），另一半由假设被 $x$ 整除（$byz$），于是 $z$ 本身被 $x$ 整除。再强调一次：Bézout 等式的存在性（扩展欧几里得）是整条推理的前提。

反例（为什么 $\gcd(x,y)=1$ 不可省）：取 $x=4,\ y=6$（$\gcd=2>1$）、$z=2$。此时 $x \mid yz$ 吗？$yz = 12$，$4 \mid 12$ ✔。但 $x \mid z$ 吗？$4 \mid 2$ ✘。引理失效，根源正是 $\gcd(4,6)=2>1$。

算术基本定理（FTA）：每个正整数 $n>1$ 可表示为质数之积 $n=p_1p_2\cdots p_k$，且该表示不计次序唯一。

证明策略：分成存在性与唯一性两部分。

• 存在性：强归纳（Lecture 3 已证，此处回顾思路）。对 $n$ 做强归纳：若 $n$ 本身是质数，取 $k=1$、$p_1=n$；若 $n$ 是合数，写 $n=uv$ 且 $1<u,v<n$，由归纳假设 $u,v$ 各有质数分解，把两个分解拼接起来即得 $n$ 的分解。强归纳是必需的，因为 $u,v$ 都可能远小于 $n-1$。归纳终止：规模严格下降且下界为 $2$，不可能无限下降。
• 唯一性：反证法/逐项消去法，用引理 6.5。

唯一性证明的逐步推导：

1. 设 $n$ 有两种质数分解

其中所有 $p_i,q_j$ 都是质数（各自可以重复）。

1. 不失一般性设 $k \le \ell$。（若 $k > \ell$，把两个分解的角色对调即可——这一步只是让后面「左边先处理完」的叙述方便。）
2. 目标：证明 $k = \ell$，且 $\{p_1,\dots,p_k\}$ 作为多重集合与 $\{q_1,\dots,q_\ell\}$ 相同。
3. 处理 $p_1$。因为 $p_1 \mid n = q_1q_2\cdots q_\ell$。
4. 分情形：
   • 情形 (i)：$p_1$ 等于某个 $q_j$（$1\le j\le \ell$）。那么把 $p_1$ 与 $q_j$ 配对，两边同除以 $p_1$，问题规模减 $1$。
   • 情形 (ii)：$p_1 \neq q_j$ 对所有 $1 \le j \le \ell$。由于 $p_1$ 与每个 $q_j$ 都是质数且不相等，它们除 $1$ 外无公因子，故 $\gcd(p_1, q_j) = 1$ 对每个 $j$ 成立。
5. 对情形 (ii) 逐次应用引理 6.5：
   • 由 $p_1 \mid q_1(q_2\cdots q_\ell)$ 且 $\gcd(p_1,q_1)=1$，得 $p_1 \mid q_2q_3\cdots q_\ell$；
   • 再对 $\gcd(p_1,q_2)=1$ 用一次引理，得 $p_1 \mid q_3\cdots q_\ell$；
   • 如此反复，最终得 $p_1 \mid q_\ell$。
6. 但 $q_\ell$ 是质数，它的大于 $1$ 的正因子只有自身，故 $p_1 = q_\ell$（注意 $p_1 \neq 1$，因为 $1$ 不是质数）。
7. 所以无论如何，$p_1$ 都等于某个 $q_j$。把这一对消去：两边同除以 $p_1$（等式仍成立），得到

1. 重复上述论证处理 $p_2$，再处理 $p_3$，直到 $p_k$。
2. 全部配对完毕后，左边变成 $1$，右边剩下 $\ell - k$ 个质数之积：

1. 每个质数 $\ge 2$，故若 $\ell - k \ge 1$，右边 $\ge 2 > 1$，矛盾。因此 $\ell - k = 0$，即 $k = \ell$。
2. 同时，第 4–9 步的配对过程为每个 $p_i$ 指定了一个唯一匹配的 $q_j$，且不同 $p_i$ 匹配不同 $q_j$（因为被匹配过的 $q_j$ 已从右端移除）。这说明 $\{p_1,\dots,p_k\}$ 是 $\{q_1,\dots,q_\ell\}$ 的一个重排。$\blacksquare$

【证明机制解说】：唯一性证明的精妙处在于引理 6.5 让我们能一次「吃掉」一个质数。如果没有它，我们只能得到「$p_1 \mid q_1q_2\cdots q_\ell$」，而「$p_1$ 是质数故必整除某个 $q_j$」这一步看似显然、实则正是需要证明的东西（它就是引理 6.5 的推论）。第 6 步的连用引理把「整除一个乘积」逐步降级为「整除单个质数」，这个过程有时被称为「逐个剥离」。另外请注意第 11 步的收尾方式：不是去比较两边的「质数个数」，而是让一边归约为 $1$，用「质数 $\ge2$」制造数量矛盾——这比逐个配对更干净，也自动给出了 $k=\ell$。

具体算例（分解与唯一性）：

由后两行立刻可见 $\gcd(1071,462) = 3\cdot7 = 21$，与欧几里得算法的结果一致 ✔。这也是「质因数分解求 gcd」与「欧几里得算法求 gcd」两条路的对照——注意前者在 $x,y$ 是大数时反而更慢（分解很难），这正是 RSA 安全性的来源。

中国剩余定理（Chinese Remainder Theorem, CRT）

第一步：先证 $k=2$ 的情形（官方 Note 6 的 Claim）

定理 6.6（CRT，$k=2$）：设 $\gcd(n_1,n_2)=1$。则对任意整数 $a_1,a_2$，同余方程组

在模 $n_1n_2$ 下有唯一解。

证明策略：构造性证明（存在性）+ 直接证明（唯一性）。存在性部分用扩展欧几里得提供的 $1 = c_1n_1 + c_2n_2$，然后「猜」出解 $x = a_1c_2n_2 + a_2c_1n_1$——这个猜测的构造逻辑是：每一项都设计成「在一个模数下自动消失、在另一个模数下自动变成 $a_i$」。唯一性部分用整除论证。

逐步推导（存在性）：

1. 由 $\gcd(n_1,n_2)=1$ 及扩展欧几里得，存在整数 $c_1,c_2$ 使

1. 构造候选解：

1. 验证 $x \equiv a_1 \pmod{n_1}$：由 (5.4) 移项得 $c_2 n_2 = 1 - c_1 n_1$，代入：

1. 右端第二项含因子 $n_1$，故 $\equiv 0 \pmod{n_1}$；于是 $x \equiv a_1 \pmod{n_1}$ ✔。
2. 验证 $x \equiv a_2 \pmod{n_2}$：完全对称。由 (5.4) 得 $c_1n_1 = 1 - c_2n_2$，代入：

1. 故 $x$ 是方程组的解。存在性得证。

逐步推导（唯一性）：

1. 设 $x,x^{\prime}$ 都是解，即 $x \equiv x^{\prime} \equiv a_1 \pmod{n_1}$ 且 $x \equiv x^{\prime} \equiv a_2 \pmod{n_2}$。
2. 由传递性（Lecture 4 定理 4.0），$x \equiv x^{\prime} \pmod{n_1}$ 且 $x \equiv x^{\prime} \pmod{n_2}$，即 $n_1 \mid (x-x^{\prime})$ 且 $n_2 \mid (x-x^{\prime})$。
3. 把 $x-x^{\prime}$ 写成 $n_1 t$。由 $n_2 \mid n_1 t$ 与 $\gcd(n_2,n_1)=1$，引理 6.5 给出 $n_2 \mid t$，即 $t = n_2 s$，故 $x - x^{\prime} = n_1n_2 s$。
4. 因此 $n_1n_2 \mid (x-x^{\prime})$，即 $x \equiv x^{\prime} \pmod{n_1n_2}$。
5. 换言之，在 $\{0,1,\dots,n_1n_2-1\}$ 内至多有一个解。结合第 6 步的存在性，恰有一个解，记为 $x \bmod n_1n_2$。$\blacksquare$

【证明机制解说】：存在性构造的设计思想可以用「指示函数」来概括：$c_2n_2$ 这个因子对模 $n_1$ 来说是 $1$（因为 $c_2n_2 \equiv 1$），对模 $n_2$ 来说是 $0$（因为它含因子 $n_2$）。所以 $a_1c_2n_2$ 项「只在模 $n_1$ 的世界里发声」，而 $a_2c_1n_1$ 项「只在模 $n_2$ 的世界里发声」；把两项相加，声音互不干扰，正好拼出目标。这就是官方 Note 6 所说的「基向量 (basis vectors)」视角——把 $k=2$ 推广到 $k$ 个模数，只需为每个方向造一个「在自己方向上为 $1$、在别的方向上为 $0$」的向量。

第二步：推广到 $k$ 个模数

定理 6.7（中国剩余定理 CRT，完整形式）：设 $n_1,n_2,\dots,n_k$ 两两互质（即 $\gcd(n_i,n_j)=1$ 对一切 $i\neq j$），令 $N = \prod_{i=1}^k n_i$。则对任意整数 $a_1,\dots,a_k$，同余方程组

在模 $N$ 下有唯一解。且解可显式构造为

证明策略（两种视角）：

• 视角一（迭代 / 归纳）：先用 $k=2$ 版本解出前两个方程，得到一个唯一的 $a_{12} \bmod n_1n_2$；于是前两个方程被等价地压缩成单个方程 $x \equiv a_{12} \pmod{n_1n_2}$。注意 $n_1n_2$ 仍与 $n_3,\dots,n_k$ 全部互质（由两两互质推出），所以问题规模从 $k$ 降到 $k-1$，可以一直迭代到只剩一个方程。这是对 $k$ 做归纳的证明。
• 视角二（构造 / 基向量）：直接为每个 $i$ 构造基向量 $b_i$，使得

然后令 $x = \sum_i a_i b_i$。这是构造性证明。

逐步推导（视角二，完整构造性存在性证明）：

1. 固定 $i$。令 $M_i = N/n_i = \prod_{j\neq i} n_j$。
2. $M_i$ 与 $n_i$ 互质：因为 $M_i$ 是除 $n_i$ 外所有 $n_j$ 的乘积，而每个 $n_j$ 都与 $n_i$ 互质，由引理 6.5 反复使用可知 $\gcd(M_i, n_i) = 1$。
3. 因此由定理 5.2，$M_i$ 在模 $n_i$ 下有逆元 $y_i := M_i^{-1} \bmod n_i$，满足 $M_i y_i \equiv 1 \pmod{n_i}$。
4. 定义基向量 $b_i := M_i y_i$，并验证它的两条性质：
   • 对模 $n_i$：$b_i = M_i y_i \equiv 1 \pmod{n_i}$ ✔（依据：逆元定义）。
   • 对模 $n_j$（$j\neq i$）：$M_i = \prod_{l\neq i} n_l$ 中含因子 $n_j$（因为 $j \neq i$ 且 $j$ 在指标集里），故 $n_j \mid M_i$，从而 $b_i = M_i y_i \equiv 0 \pmod{n_j}$ ✔。
5. 构造解 $x := \sum_{i=1}^k a_i b_i$。（依据：这是「目标向量的线性组合」。）
6. 验证：固定任意 $i$。对 $x$ 取模 $n_i$：

第一个 $\equiv$ 用了定理 5.1（同余式可相加、可乘常数）与步骤 4 的两条性质。故 $x$ 满足第 $i$ 个方程；由于 $i$ 任意，$x$ 满足全部 $k$ 个方程。存在性得证。 $\square$

逐步推导（唯一性）：

1. 设 $x, x^{\prime}$ 都是解。对每个 $i$，$x \equiv a_i \equiv x^{\prime} \pmod{n_i}$，故 $n_i \mid (x - x^{\prime})$。
2. 于是 $(x-x^{\prime})$ 被 $n_1,\dots,n_k$ 逐一整除。由于这些 $n_i$ 两两互质，反复应用引理 6.5 可得 $N = n_1n_2\cdots n_k \mid (x - x^{\prime})$。具体做法是对 $i=2,\dots,k$ 归纳：已有 $n_1\cdots n_{i-1}\mid u$（$u=x-x^{\prime}$，$i=2$ 时由 $n_1\mid u$ 立得），又 $n_i\mid u$ 且 $\gcd(n_1\cdots n_{i-1},n_i)=1$，故 $n_1\cdots n_i \mid u$。
3. 故 $x \equiv x^{\prime} \pmod N$，即在模 $N$ 意义下解唯一。$\blacksquare$

反例（两两互质不可省）：取 $n_1 = 4,\ n_2 = 6$，$\gcd(4,6)=2>1$。考虑方程组

若 $x \equiv 1 \pmod 4$ 则 $x$ 是奇数；若 $x \equiv 2 \pmod 6$ 则 $x$ 是偶数。矛盾，无解。（脚本穷举 $0\le x<12$（$= \operatorname{lcm}(4,6)$）确认无解 ✔。）这说明 CRT 的「两两互质」不是装饰性条件——它既保证解存在，也保证解唯一。

完整手算算例：孙子问题 $x \equiv 2 \pmod 3,\ x \equiv 3 \pmod 5,\ x \equiv 2 \pmod 7$

这里 $n_1=3,\ n_2=5,\ n_3=7$ 两两互质，$N = 3\cdot5\cdot7 = 105$。

第 1 步：算各 $M_i$ 与逆元 $y_i$

第 2 步：验证基向量性质

   b1 = 70:  70 mod 3 = 1  ✔   70 mod 5 = 0  ✔   70 mod 7 = 0  ✔
   b2 = 21:  21 mod 3 = 0  ✔   21 mod 5 = 1  ✔   21 mod 7 = 0  ✔
   b3 = 15:  15 mod 3 = 0  ✔   15 mod 5 = 0  ✔   15 mod 7 = 1  ✔

   （这正是「第 i 个方向上为 1，其余方向为 0」的坐标基）

   解方程组的结构：
      x ≡ a1*b1 + a2*b2 + a3*b3  (mod 105)
        = 2*70  + 3*21  + 2*15
        = 140   + 63    + 30
        = 233
      x ≡ 233 mod 105 = 233 - 210 = 23

第 3 步：验证解

（$23 = 7\cdot3+2$；$23 = 4\cdot5+3$；$23 = 3\cdot7+2$。）

第 4 步：穷举交叉验证（脚本对 $0\le x<105$ 逐一检查，只有 $x=23$ 满足全部三个条件 ✔）。通解为 $x = 23 + 105t$（$t\in\mathbb{Z}$）。

算例 2（$k=2$）：解 $x \equiv 1 \pmod 4$、$x \equiv 2 \pmod 5$。$\gcd(4,5)=1$，$N=20$。

• $4^{-1} \bmod 5$：$4\cdot 4 = 16 \equiv 1 \pmod 5$，故 $c_1 = 4$；$5^{-1}\bmod 4$：$5 \equiv 1 \pmod 4$，故 $c_2 = 1$。
• 按定理 6.6 的构造 $x = a_1c_2n_2 + a_2c_1n_1 = 1\cdot1\cdot5 + 2\cdot4\cdot4 = 5 + 32 = 37$。
• $x \bmod 20 = 17$。验证：$17 \bmod 4 = 1$ ✔，$17 \bmod 5 = 2$ ✔。

算例 3（用 CRT 加速大数幂运算）：想算 $3^{100} \bmod 35$。因 $35 = 5\cdot 7$（互质），先分别在模 $5$ 与模 $7$ 下用费马小定理：

• 模 $5$：$3^{4}\equiv 1$，$100 \bmod 4 = 0$，故 $3^{100}\equiv 1 \pmod 5$。
• 模 $7$：$3^{6}\equiv 1$，$100 \bmod 6 = 4$，故 $3^{100} \equiv 3^{4} = 81 \equiv 4 \pmod 7$。
• 现在解 $x \equiv 1 \pmod 5$、$x \equiv 4 \pmod 7$：$N=35$，$M_1 = 7$，$7^{-1}\bmod5 = 3$（$7\cdot3=21\equiv1$），$b_1 = 21$；$M_2 = 5$，$5^{-1}\bmod 7 = 3$（$5\cdot3=15\equiv1$），$b_2=15$。
• $x = 1\cdot21 + 4\cdot15 = 21+60 = 81 \equiv 81-70 = 11 \pmod{35}$。
• 验证：$11 \bmod 5 = 1$ ✔，$11 \bmod 7 = 4$ ✔。答案 $3^{100}\equiv 11 \pmod{35}$。（脚本直接算 $3^{100} \bmod 35 = 11$ ✔）

这个技巧的意义：CRT 让你把一个「模大合数」的难题拆成几个「模小质数」的简单题，做完再拼回去。这既是 Lecture 8 里「多项式求值可以并行化」的思想源头，也是 RSA 实现中「用 CRT 加速解密（把模 $N$ 的运算拆成模 $p$ 和模 $q$ 的两个运算，速度提升约 4 倍）」的原理。

费马小定理（Fermat’s Little Theorem, FLT）

定理 6.8（费马小定理）：设 $p$ 是质数，$a \in \{1,2,\dots,p-1\}$。则

证明策略：关键引理（乘法是排列）+ 双计数式的乘积比较。先把 Lecture 4 定理 5.2 的「乘以 $x$ 是 $\mathbb{Z}_m$ 上的双射」这一结论搬到 $S = \{1,2,\dots,p-1\}$ 上，得到「$a\cdot1, a\cdot 2,\dots,a\cdot(p-1)$ 是 $S$ 的一个排列」；然后用两种方式计算同一个乘积：直接算得 $(p-1)!$，用排列算得 $a^{p-1}(p-1)!$，两者必须相等；最后两边乘 $(p-1)!$ 的逆元消掉它。这个策略之所以有效，是因为「集合相同」这一信息比「逐一对应」更强，能直接给出乘积等式。

引理 6.9（关键引理）：设 $p$ 是质数，$a \in \{1,\dots,p-1\}$。则集合

与 $S = \{1,2,\dots,p-1\}$ 完全相同（只是一个重排）。

逐步推导（引理 6.9）：

1. 因为 $p$ 是质数，$a \in \{1,\dots,p-1\}$ 意味着 $p \nmid a$，即 $\gcd(a,p) = 1$。（依据：$p$ 的因子只有 $1$ 与 $p$。）
2. 由 Lecture 4 定理 5.2 的证明（其中的「两两不同余」断言），序列 $0, a, 2a, \dots, (p-1)a$ 模 $p$ 两两不同余。
3. 特别地，$a, 2a, \dots, (p-1)a$ 这 $p-1$ 项模 $p$ 也两两不同余。
4. 没有一项 $\equiv 0$：若 $ka \equiv 0 \pmod p$（$1 \le k \le p-1$），则 $p \mid ka$；由 $\gcd(a,p)=1$ 与引理 6.5 得 $p \mid k$，但 $1 \le k \le p-1 < p$，矛盾。
5. 于是这 $p-1$ 个余数互不相同，且全部落在 $S = \{1,\dots,p-1\}$ 内（既非 $0$，取值又在 $0..p-1$ 之间）。
6. $S$ 只有 $p-1$ 个元素，而我们有 $p-1$ 个互不相同且落在 $S$ 内的余数——由鸽笼原理（Lecture 2），它们恰好取遍 $S$ 的每个元素一次。
7. 故 $S^{\prime} = S$，$\{a\bmod p,\ 2a \bmod p,\dots,(p-1)a\bmod p\}$ 是 $\{1,2,\dots,p-1\}$ 的一个排列 (permutation)。$\blacksquare$

逐步推导（定理 6.8）：

1. 记 $S = \{1,2,\dots,p-1\}$，$S^{\prime} = \{a\cdot k \bmod p: k \in S\}$。由引理 6.9，$S^{\prime} = S$。
2. 方法一：把 $S$ 的全部元素相乘，按定义就是阶乘：

1. 方法二：把 $S^{\prime}$ 的全部元素相乘。$S^{\prime}$ 的元素依次是 $a\cdot k \bmod p$（$k=1,\dots,p-1$），故

（依据：定理 5.1，可以把每个因子先模 $p$ 再相乘；$a$ 出现 $p-1$ 次提出来。）

1. 因为 $S = S^{\prime}$ 是同一个集合，两个乘积是同一个整数（在模 $p$ 下），于是

1. 消去 $(p-1)!$：因为 $p$ 是质数，$1,2,\dots,p-1$ 每一个都与 $p$ 互质。由引理 6.5 反复应用，$\gcd((p-1)!,\,p)=1$（任何 $p$ 的质因子若整除 $(p-1)!$，就必须整除某个 $k\le p-1$，但那些 $k$ 都小于 $p$ 且非零，矛盾）。
2. 由 Lecture 4 定理 5.2，$(p-1)!$ 在模 $p$ 下可逆；两边同乘其逆元（也就是用消去律，推论 4.3）：

$\blacksquare$

【证明机制解说】：这个证明最漂亮的地方是用两种方式数同一个量（乘积的两种算法），这在组合数学里叫双计数 (double counting)，本课程 Lecture 16 会专门讲这个技巧。这里「两种方式」分别是：

• 按 $S$ 的定义直接乘 $\Rightarrow (p-1)!$；
• 按 $S^{\prime} = S$ 把每个元素写成 $ak$ 的形式再乘 $\Rightarrow a^{p-1}(p-1)!$。

由于两式的对象是同一个集合的乘积，它们必须相等。整个定理的力量全部来自引理 6.9 的「$S^{\prime}$ 就是 $S$ 本身」——如果只有「$S^{\prime}$ 与 $S$ 一一对应」而没有「相等」，这个乘积比较就不成立。

第 6 步的消去也值得细看：它又一次用到了「质数 $\Rightarrow$ 一切 $1\le k<p$ 都可逆」，这是 Lecture 4 定理 5.2 与 Lecture 5 引理 6.5 的合体应用。

FLT 的两个必要条件的反例

(1) $p$ 必须是质数。 取 $m=4$、$a=2$。$m-1 = 3$，而

再看 $m=6$、$a=2$：$2^{5} = 32 = 5\cdot6+2 \equiv 2 \neq 1 \pmod 6$（这里 $\gcd(2,6)=2>1$）。更值得注意的是 $m=8,\ a=3$（此时 $\gcd(3,8)=1$，$a$ 是可逆的）：$3^{7} = 2187 \equiv 3 \pmod 8$（因为 $3^2=9\equiv1$，故 $3^{2k}\equiv1$，$3^7 = 3^{6}\cdot3 \equiv 3$）。仍然是 $3 \neq 1$。这说明即使 $a$ 可逆，合数模数下 FLT 依然失效。

(2) $a$ 必须与 $p$ 互质。 在质数模数下，$1\le a\le p-1$ 已自动保证 $\gcd(a,p)=1$。但若允许 $a$ 是 $p$ 的倍数（如 $a \equiv 0$），结论显然变成 $0^{p-1}\equiv0\neq1$。所以 FLT 的完整前提是：$p$ 质数 且 $\gcd(a,p)=1$。（这正是「等价形式 $a^p\equiv a \pmod p$ 对任意 $a$ 成立」——当 $p\mid a$ 时两边都是 $0$，所以那个形式不需要互质条件；考试中若题目没给 $\gcd$ 条件，请用 $a^p\equiv a$ 的形式。）

推论 6.10（FLT 求逆元）：设 $p$ 是质数，$a \in \{1,\dots,p-1\}$。则

证明：由 FLT，$a^{p-1} = a\cdot a^{p-2} \equiv 1 \pmod p$。按逆元定义（Lecture 4），$a^{p-2}$ 就是 $a$ 的乘法逆元；由逆元唯一性，$a^{-1}\equiv a^{p-2}\pmod p$。$\blacksquare$

推论 6.11（幂的周期律）：设 $p$ 质数、$\gcd(a,p)=1$，则对任意整数 $k\ge 0$，

证明：写 $k = q(p-1) + r$（$0\le r<p-1$）。则 $a^{k} = (a^{p-1})^{q}\cdot a^{r} \equiv 1^{q}\cdot a^{r} = a^{r} \pmod p$。$\blacksquare$

算例（FLT 计算逆元与幂）：

• $p=7$，$a=3$：$3^{-1}\equiv 3^{5} \pmod 7$。算 $3^5 = 243 = 34\cdot7 + 5 \equiv 5$。对照 Lecture 4 表里 $3^{-1} = 5$ ✔。
• $p=11$，$a=2$：$2^{-1}\equiv 2^{9} \pmod{11}$。$2^{10}\equiv1$，故 $2^9 \equiv 2^{10}\cdot2^{-1}\equiv 1\cdot6 = 6$（$2\cdot6=12\equiv1$）。故 $2^{-1}\equiv6$ ✔。
• $p=11$，$a=7$：求 $7^{203}\bmod 11$。$203 \bmod 10 = 3$，故 $7^{203}\equiv 7^3 = 343 = 31\cdot11+2 \equiv 2 \pmod{11}$ ✔。（与 Lecture 4 思考题 Q1 的结果一致。）
• $p=13$，$a=3$：$3^{12} = 531441$，$531441 \bmod 13 = 1$ ✔（脚本验算）。

与经典问题的联系

（一）RSA 公钥密码（Lecture 6）

RSA 的完整数据流正是本讲三条主线的合体：

1. Bob 选两个大质数 $p,q$，令 $N=pq$，选 $e$ 与 $(p-1)(q-1)$ 互质。私钥 $d \equiv e^{-1} \bmod (p-1)(q-1)$ 由扩展欧几里得算法高效算出（本讲第 1 节）。
2. Alice 发送 $E(x) \equiv x^{e} \bmod N$；Bob 解密 $D(y)\equiv y^{d}\bmod N$。两次幂运算都用 Lecture 4 的快速幂，代价 $O(\log N)$ 次乘法。
3. 解密正确性 $x^{ed}\equiv x \pmod N$ 的证明依赖费马小定理：由 $ed \equiv 1 \pmod{(p-1)(q-1)}$ 写成 $ed = 1+k(p-1)(q-1)$，则
   • 若 $p \nmid x$，FLT 给 $x^{p-1}\equiv1$，故 $x^{ed} = x\,(x^{p-1})^{k(q-1)}\equiv x \pmod p$；
   • 若 $p \mid x$，两边都是 $0 \equiv 0 \pmod p$。 对 $q$ 同理，最后由 CRT 的唯一性把「模 $p$ 相等」与「模 $q$ 相等」合成「模 $pq=N$ 相等」。
4. 质数生成用费马小定理的推广（Miller–Rabin 素性测试）快速筛出大质数。

（二）大数运算的并行化 / 加速（CRT 的工程价值）

RSA 的 C 实现（如 OpenSSL）普遍使用 CRT 加速：解密时不算 $y^d \bmod N$，而是分别算 $y^{d \bmod (p-1)} \bmod p$ 与 $y^{d \bmod (q-1)} \bmod q$，再用 CRT 把两个结果拼起来。因为两个子运算都在 $N/2$ 位（数量级）的数上进行，总代价约为原来的 $1/4$。这正是本讲 CRT 构造式在工业代码里的直接落地。

（三）哈希与一致性哈希

把哈希值对 $m$ 取模分桶时，若 $m$ 是合数（如 $2^k$），低位比特的分布会暴露规律；选质数 $m$ 则能借助本讲 $\mathbb{Z}_p$ 结构的「整齐性」（乘法表每行是排列）获得更好的散列性质。

（四）快速幂 + FLT 做素性测试

若 $n$ 是质数，则对一切 $a$ 有 $a^{n-1}\equiv1 \pmod n$。反之，若发现某个 $a$ 使 $a^{n-1}\not\equiv1$，则 $n$ 必定是合数（这用到了逆否命题，Lecture 2）。这就是 Miller–Rabin 素性测试的起点——注意它只是「合数的证据」，不是「质数的证明」（存在 Carmichael 数，如 $561 = 3\cdot11\cdot17$，能骗过所有与它互质的 $a$）。这条「用随机测试换确定性结论」的路线，是 Lecture 23 集中不等式要定量分析的对象。

与其他讲次的关联

• 承接 Lecture 0（直接证明与整除性）：定理 6.1 的两个方向都只用「$d\mid u \wedge d\mid v \Rightarrow d\mid (u\pm v)$」这一条；引理 6.5 的最后一步「$x\mid(axz+byz)$」用的也是它。整除线性性是本讲最频繁调用的工具。
• 承接 Lecture 2（鸽笼原理、有限集上单射即满射）：引理 6.9 的第 6 步（$p-1$ 个互异余数落在 $p-1$ 个格子里 $\Rightarrow$ 恰好铺满）就是鸽笼原理的应用；它直接来自 Lecture 4 定理 5.2 的同一技术。
• 承接 Lecture 3（强归纳）：定理 6.2（gcd 正确性）与定理 6.4（扩展 gcd 正确性）都对第二个参数做强归纳；算术基本定理的存在性部分也是对 $n$ 做强归纳。三处都体现了 Lecture 3 强调的「归纳变量必须严格下降」这一要点。
• 承接 Lecture 4（模运算与逆元）：本讲几乎每一步都在用 Lecture 4 的三件工具：定理 5.1（同余可加可乘）、定理 5.2（$\gcd=1 \Leftrightarrow$ 可逆）、消去律（推论 4.3）。CRT 的构造本质上就是「用逆元造基向量」，FLT 的证明本质上是「用双射比较乘积」。 上一讲欠下的两笔账（欧几里得引理、逆元的算法）在本讲第 1 节全部还清。
• 通向 Lecture 6（RSA）：三条线汇聚——扩展欧几里得算 $d$、快速幂算 $x^e$ 与 $y^d$、FLT + CRT 证解密正确性。
• 通向 Lecture 7–8（多项式、秘密共享与纠错码）：把 $\mathbb{Z}_p$（$p$ 为质数）推广为有限域 $\mathrm{GF}(q)$ 后，多项式插值（Lecture 7 的 Lagrange 插值）与 Reed–Solomon 码（Lecture 8）才有意义；CRT 的「坐标视角」则是 Lecture 8 中「用多个模数并行编码」的原型。
• 通向 Lecture 12（可数性）：算术基本定理给出的「质数是整数的唯一原子」这一图景，在 Lecture 12 证明「质数有无穷多个」以及「代数数可数」时会被再次召唤。
• 通向 Lecture 14、16（计数与组合证明）：定理 6.8 的证明就是一次双计数，而 Lecture 16 会用同样的手法证明一批组合恒等式（如 Vandermonde 恒等式）。
• 通向 Lecture 23（集中不等式 / 大数定律）：Miller–Rabin 这类随机化素性测试是「随机算法的错误概率随重复次数指数衰减」的第一个实例，Lecture 23 的 Chernoff 界会给出定量的分析工具。

关键要点

1. 欧几里得算法的不变量：$\gcd(x,y) = \gcd(y, x \bmod y)$。证明方式不是比较「最大数」，而是证明两个公约数集合相同（双向包含）。递归深度 $O(\log x)$，因为每两次调用第一个参数至少减半（分 $y\le x/2$ 与 $y>x/2$ 两种情形）。
2. 扩展欧几里得 = gcd + Bézout 系数，核心回代公式 $A = b,\ B = a - \lfloor x/y\rfloor b$。它的推导只用了恒等式 $x \bmod y = x - \lfloor x/y \rfloor y$，不是猜出来的。正确性对第二个参数做强归纳。
3. Bézout 等式是数论证明的万能钥匙：引理 6.5（$x \mid yz$ 且 $\gcd(x,y)=1 \Rightarrow x\mid z$）由它推出，而引理 6.5 又支撑了算术基本定理的唯一性、CRT 的唯一性、FLT 的消去步骤。推论链：扩展欧几里得 $\to$ Bézout $\to$ 引理 6.5 $\to$ FTA/CRT/FLT。
4. 模逆元的算法：跑 extended-gcd(m,x) 得 $1 = am+bx$，则 $x^{-1}\equiv b \pmod m$（负数要加上若干 $m$）。质数模数下还有捷径 $a^{-1}\equiv a^{p-2}\pmod p$。
5. CRT 的坐标视角：$b_i = M_i(M_i^{-1}\bmod n_i)$ 是「第 $i$ 个坐标轴上的基向量」（$b_i\equiv1 \pmod{n_i}$，$b_i\equiv0 \pmod{n_j}$），解 $x = \sum_i a_i b_i$。存在性靠构造，唯一性靠「$N \mid x-x^{\prime}$」。两两互质不可省（$n_1=4,n_2=6$ 时可能无解）。
6. FLT 的条件必须记全：$p$ 质数 且 $\gcd(a,p)=1$，结论 $a^{p-1}\equiv1\pmod p$（等价形式 $a^p\equiv a$ 对任意 $a$ 成立）。对合数失效：$m=4,a=2$ 时 $2^3\equiv0\neq1$。证明的核心是「$a\cdot1,\dots,a\cdot(p-1)$ 是 $\{1,\dots,p-1\}$ 的排列」+ 双计数比较乘积 + 用 $(p-1)!$ 的逆元消去。

常见误区与注意事项

1. 把「公约数集合相同」只证一个方向。定理 6.1 的证明必须两个方向都写：只证「$d\mid x,y \Rightarrow d\mid y, x\bmod y$」只说明新集合包含旧集合（反向包含未证），无法推出两个集合的最大元相等。
2. 认为「一次递归调用就减半」。反例 $x=1000,y=999$：一次调用后第一个参数是 $999$，几乎没减。必须论证「两次调用减半」，并且要用到 $y > x/2 \Rightarrow x \bmod y = x - y$ 这一步。
3. 归纳正确性时忘记验证递归调用的输入合法性。定理 6.2 第 6 步必须检查「$y \ge x\bmod y$ 且 $y>0$」才能让归纳假设落地。漏掉这一步，证明就断了。
4. 把 Bézout 等式当成同余式。$d = ax+by$ 是普通的整数等式，$a,b$ 可以是负数（如 $1 = -1\cdot35 + 3\cdot12$）。不要写出「$d \equiv ax+by \pmod m$」这类混淆。
5. 扩展欧几里得的回代公式记错顺序。返回的是 $(d,\ b,\ a - \lfloor x/y\rfloor b)$，第一个系数换成原来的 $b$、第二个系数换成 $a - qb$。混淆 $a$ 与 $b$ 的位置是最常见的实现 bug。
6. FLT 条件写漏。写成「对任意 $m$ 与 $a$，$a^{m-1}\equiv1\pmod m$」是严重错误。正确版本：$p$ 质数、$\gcd(a,p)=1$。反例：$m=4,a=2$ 时 $2^3\equiv0$；$m=8,a=3$ 时 $3^7\equiv3$（即使 $a$ 可逆也不成立，因为 $m$ 不是质数）。
7. CRT 漏掉「两两互质」。CRT 的前提是两两互质 (pairwise coprime)，比「$\gcd(n_1n_2\cdots n_{k-1}, n_k)=1$」更强也更常用。反例：$n_1=4,n_2=6$ 时 $x\equiv1\pmod4$ 与 $x\equiv2\pmod6$ 无解。
8. CRT 的两个表述漏洞：一是漏掉「两两互质」前提（反例：$n_1=4,n_2=6$ 时 $x\equiv1\pmod4$ 与 $x\equiv2\pmod6$ 无解）；二是把唯一性说成「解唯一」而非「模 $N$ 唯一」——方程组实际有无穷多解 $x = x_0 + Nt$，唯一的只是它在模 $N$ 下的剩余类。
9. 取整方向与「唯一」的含义：$x \bmod y = x - \lfloor x/y\rfloor y$ 必须是向下取整（$x=7,y=2$ 时 $\lfloor7/2\rfloor=3$，$7-3\cdot2=1$ ✔）。另外算术基本定理的「唯一」指多重集合相同：$12=2\cdot2\cdot3$ 与 $2\cdot3\cdot2$ 是同一个分解（重排），而 $12=2\cdot6$ 根本不合法（$6$ 不是质数）。

思考题（带答案）

Q1.（计算题） 用扩展欧几里得算法求 $\gcd(240, 46)$，写出完整的商序列与回溯表，给出 $a,b$ 使 $a\cdot240 + b\cdot46 = \gcd(240,46)$，并由此求出 $46^{-1} \bmod 240$（若不存在请说明理由）。

Q2.（证明题） 设 $x,y$ 为正整数，$g = \gcd(x,y)$，$L = \operatorname{lcm}(x,y)$。证明 $gL = xy$。

Q3.（概念/构造题） 解同余方程组 $x \equiv 1 \pmod 3$、$x \equiv 4 \pmod 5$、$x \equiv 5 \pmod 7$。要求给出完整的 CRT 构造过程（列出每个基向量），用穷举验算你的答案，并说明在 $[0,104]$ 内解是否唯一。