Lecture 4: Modular Arithmetic（模运算）
Lecture 4: Modular Arithmetic（模运算）
概述
本讲引入整门 CS70 后半段离散数学模块的「通用语言」：模运算 (modular arithmetic)。核心问题是：当我们需要把数字限制在一个固定的小范围 $\{0,1,\dots,m-1\}$ 内做运算（密码学要控制密钥长度、纠错码要限制符号表大小）时，加、减、乘这些运算还能不能正常进行？本讲证明可以（定理 5.1），并指出除法不行——除非引入乘法逆元。本讲的证明技巧以直接证明与反证法（鸽笼/双射论证）为主，它为下一讲的欧几里得算法、费马小定理与中国剩余定理铺好语言，最终通向 Lecture 6 的 RSA。
核心概念的直观解释
同余（Congruence）
- 定义：设 $m$ 为正整数。对任意两个整数 $a,b$，称 $a$ 与 $b$ 模 $m$ 同余 (congruent modulo $m$)，记作
即 $a-b$ 是 $m$ 的整数倍。注意这里的 $\equiv$ 是一个二元关系，不是等式；它的两边可以相差任意多个 $m$。
- 直观解释（”它是什么意思？”）：同余在说「只看余数，不管倍数」。$a$ 与 $b$ 同余，意思是它们除以 $m$ 后落在同一个「格子」里。一个等价的、更贴近计算的写法是
（右式的「$a \bmod m$」是指 $a$ 除以 $m$ 的最小非负余数，取值落在 $\{0,1,\dots,m-1\}$。）
- 具体示例：$29 \equiv 5 \pmod{12}$，因为 $12 \mid (29-5)=24$；同时 $29 \bmod 12 = 5 = 5 \bmod 12$。又如 $13 \equiv 3 \pmod 5$（$13-3=10$ 是 $5$ 的倍数）。同余还允许右侧是负数：$22 \equiv -2 \pmod{12}$，因为 $22-(-2)=24$ 是 $12$ 的倍数。这三种写法 $29\equiv 5$、$29 \equiv 17$、$29 \equiv -7 \pmod{12}$ 描述的是同一件事。
时钟算术（Clock Arithmetic）
- 定义：把整数集合按模 $m$ 折叠成一个「表盘」，表盘上有 $m$ 个刻度 $0,1,\dots,m-1$；超出刻度范围的数就「绕回去」。$m=12$ 就是钟表，$m=7$ 就是星期。
- 直观解释：如果你在下午 1 点问「13 小时后是几点」，你会答「凌晨 2 点」而不是「14 点」——因为你自动做了 $1+13=14 \equiv 2 \pmod{12}$。同理从下午 2 点起，任意整数倍的 12 小时之后都还是下午 2 点（$2+24 \equiv 2$）；而 25 小时之后是 3 点，因为「24 小时回到原地」之后只多走了 $25 \bmod 12 = 1$ 小时。
- 具体示例：$m=7$ 时，如果今天是周二（记作 $2$），那么 $100$ 天后是周几？$100 = 7\times 14 + 2$，所以 $100 \equiv 2 \pmod 7$，$2+2 = 4$，即周四。这个「绕圈」的图景就是模运算之所以能压缩数值范围的全部理由。
模 12 的「时钟」：加法就是沿圆周走步数
0 (12)
11 1
10 2
9 3
8 4
7 5
6
从 2 出发走 25 步： 25 mod 12 = 1，等价于只走 1 步 --> 落到 3
从 2 出发走 24 步： 24 mod 12 = 0，等价于不动 --> 仍是 2
模 7 的「星期盘」：0=周日, 1=周一, ..., 6=周六
0
6 1
5 2
4 3
从 2（周二）走 100 步：100 mod 7 = 2 --> 走到 4（周四）
剩余类（Residue Classes）与 $\mathbb{Z}_m$
- 定义：对固定的 $m$，把全体整数按「与 $i$ 同余」分组，得到
这 $m$ 个集合称为模 $m$ 的剩余类 (residue classes modulo $m$)，它们的全体记作 $\mathbb{Z}_m$（也常写作 $\mathbb{Z}/m\mathbb{Z}$）。
- 直观解释（”它是什么意思？”）：$\mathbb{Z}_m$ 就是把整条数轴「卷成一圈」后得到的 $m$ 个点。每个类都用其中唯一的、落在 $\{0,\dots,m-1\}$ 里的元素作标准代表元 (canonical representative)。于是「在模 $m$ 下计算」就等于「只在代表元上计算」。
具体示例：$m=12$ 时，与 $0$ 同余的类是 $\{\dots,-36,-24,-12,0,12,24,36,\dots\}$（所有 $12$ 的倍数）；与 $1$ 同余的类是 $\{\dots,-35,-23,-11,1,13,25,37,\dots\}$；与 $2$ 同余的类是 $\{\dots,-34,-22,-10,2,14,26,38,\dots\}$。恰好有 12 个这样的类，而且每个整数属于且只属于其中一个——这就是后面「$m$ 个类构成一个划分」的含义。
用 $m=5$ 看得更清楚：
数轴上的整数被模 5 折成 5 个「抽屉」：
... -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ...
| | | | | | | | | | | | | | | | | |
v v v v v v v v v v v v v v v v v v
[0] -10 -5 0 5 ... (5 的倍数)
[1] -9 -4 1 6 ...
[2] -8 -3 2 7 ...
[3] -7 -2 3 ...
[4] -6 -1 4 ...
每一个整数恰好落在一个抽屉里；5 个抽屉互不相交，并起来是全部 Z。
等价关系（Equivalence Relation）
- 定义：集合 $S$ 上的二元关系 $\sim$ 若满足以下三条，则称其为等价关系 (equivalence relation)：
- 自反性 (reflexivity)：$\forall a \in S,\ a \sim a$；
- 对称性 (symmetry)：$\forall a,b \in S,\ a \sim b \Rightarrow b \sim a$；
- 传递性 (transitivity)：$\forall a,b,c \in S,\ a \sim b \ \wedge\ b \sim c \Rightarrow a \sim c$。
- 直观解释：「等价关系」就是「某种意义下相同」。它把集合切成互不相交的等价类 (equivalence classes)，而每个元素恰好属于一个类。同余正是这样一个关系——这正是 $\mathbb{Z}_m$ 能成为「$m$ 个抽屉」的根本原因。
- 具体示例：模 $4$ 下，$7 \sim 7$（自反）；$7 \sim 3 \Rightarrow 3 \sim 7$（对称，因为 $4 \mid (7-3)$ 与 $4 \mid (3-7)$ 等价）；$7 \sim 3$ 且 $3 \sim 11 \Rightarrow 7 \sim 11$（传递，$11-7=4$）。三个性质都在下面的定理 4.0 中被证明。
快速幂 / 反复平方（Exponentiation by Repeated Squaring）
- 定义：计算 $x^y \bmod m$（$y$ 可能是上千比特的大整数）。朴素做法是连乘 $y$ 次；反复平方做法利用 $y$ 的二进制展开，把 $y$ 不断除以 2，递归深度只有 $y$ 的比特数 $n=\lceil \log_2(y+1)\rceil$。
- 直观解释：连乘 $y$ 次的代价随 $y$ 的大小指数增长，而反复平方的代价随 $y$ 的位数线性增长。$y$ 有 $1000$ 比特（约 $10^{301}$）时，前者需要 $10^{301}$ 次乘法——宇宙热寂也算不完；后者只需约 $1000$ 次。这是 RSA 能在口袋里跑起来的第二个技术前提（第一个是下一讲的扩展欧几里得）。
- 具体示例：算 $3^{11} \bmod 7$。$11 = 8+2+1 = (1011)_2$。只需先算出 $3^1,3^2,3^4,3^8$（每一步把上一步的结果平方），再挑出 $11$ 的二进制里为 $1$ 的位相乘：$3^{11} = 3^8\cdot 3^2\cdot 3^1 \equiv 2\cdot 2\cdot 3 = 12 \equiv 5 \pmod 7$。
乘法逆元（Multiplicative Inverse）
- 定义：设 $\gcd(x,m)=1$。若整数 $y$ 满足
则称 $y$ 为 $x$ 模 $m$ 的乘法逆元 (multiplicative inverse modulo $m$)，记作 $x^{-1} \bmod m$。若不存在这样的 $y$，则说 $x$ 模 $m$ 不可逆。
- 直观解释：在实数里「除以 $x$」等于「乘以 $1/x$」；这里 $1/x$ 的角色由 $x^{-1}$ 扮演。逆元一旦存在就是唯一的（模 $m$），所以「除以 $x$」在模 $m$ 下有了确定的意义。但逆元不一定存在——这是模运算与中学算术最剧烈的分歧点。
- 具体示例：$x=8,\ m=15$：$2\cdot 8 = 16 \equiv 1 \pmod{15}$，所以 $8^{-1} \equiv 2$。反过来 $x=12,\ m=15$：把 $12a \bmod 15$ 依次列出得到周期序列 $12, 9, 6, 3, 0, 12, 9, 6,\dots$，数字 $1$ 永远不出现，所以 $12$ 模 $15$ 没有逆元。注意这句话的两层「怪事」：一是非零数也可能没有逆元（实数里只有 $0$ 没有逆元）；二是非零数的乘法表中出现了 $0$（$12\cdot 5 = 60 \equiv 0 \pmod{15}$，而实数里任何非零数的乘法表都不含 $0$）。
完整证明与推导（核心）
定理 4.0（同余是等价关系）：对任意正整数 $m$，关系 $a \equiv b \pmod m$ 是 $\mathbb{Z}$ 上的等价关系。
证明策略：直接证明。三条性质都只需把定义 $m \mid (a-b)$ 翻译成「存在整数 $k$ 使 $a-b = km$」，然后对 $k$ 做代数操作——这正是 Lecture 0 里「整除性证明」的标准套路。
逐步推导：
- 自反性：取任意 $a \in \mathbb{Z}$。$a - a = 0 = 0\cdot m$，故 $m \mid (a-a)$，即 $a \equiv a \pmod m$。（依据：整除的定义，$0$ 是 $m$ 的 $0$ 倍。）
- 对称性：设 $a \equiv b \pmod m$，即存在整数 $k$ 使 $a - b = km$。两边取负得 $b - a = (-k)m$，而 $-k$ 仍是整数，故 $m \mid (b-a)$，即 $b \equiv a \pmod m$。
- 传递性：设 $a \equiv b$ 且 $b \equiv c \pmod m$，即存在整数 $k_1,k_2$ 使 $a - b = k_1 m$、$b - c = k_2 m$。两式相加：
由于 $k_1+k_2 \in \mathbb{Z}$，得 $m \mid (a-c)$，即 $a \equiv c \pmod m$。$\blacksquare$
【证明机制解说】：这三条性质之所以成立，是因为「$m \mid (a-b)$」把问题降维成了「$a-b$ 属于集合 $m\mathbb{Z}$」——而 $m\mathbb{Z} = \{km : k\in\mathbb{Z}\}$ 这个集合对取负、求和都封闭（它是 $\mathbb{Z}$ 的一个子群）。更一般地：任何把一个群映射到子群上的「同态」都给出等价关系。传递性是三者中唯一的「合成」步骤，也是后面一切运算律的真正来源。
定理 5.1（同余与加乘相容 / 运算的良定义性）：若 $a \equiv c \pmod m$ 且 $b \equiv d \pmod m$，则
\[a + b \equiv c + d \pmod m, \qquad a\cdot b \equiv c\cdot d \pmod m .\]证明策略：直接证明（对两部分各做一次）。关键是把四条同余关系全部翻译成不带模号的整数等式：$c = a + km$、$d = b + \ell m$，然后算出 $c+d$ 与 $cd$，观察它们与 $a+b$、$ab$ 的差是否恰为 $m$ 的倍数。官方 Note 5 只写了加法部分并把乘法留作习题，这里把两部分都补全。
逐步推导（加法部分）：
- 由假设 $a \equiv c \pmod m$，按定义存在整数 $k$ 使 $c = a + k m$。
- 由假设 $b \equiv d \pmod m$，存在整数 $\ell$ 使 $d = b + \ell m$。
- 相加：$c + d = (a + km) + (b + \ell m)$。（依据：代入步骤 1、2 的表达式。）
- 整理：$c + d = a + b + (k+\ell)m$。（依据：整数加法的交换律与结合律。）
- 移项：$(c+d) - (a+b) = (k+\ell)m$，而 $k+\ell$ 是整数。
- 由整除定义 $m \mid \big[(c+d)-(a+b)\big]$，按同余定义即为 $a+b \equiv c+d \pmod m$。$\square$
逐步推导（乘法部分）：
- 同前，$c = a + km$、$d = b + \ell m$。
- 相乘：$cd = (a+km)(b+\ell m)$。（依据：代入。）
- 展开：$cd = ab + a\ell m + b k m + k\ell m^2$。（依据：分配律。）
- 提取公因子 $m$：$cd = ab + m\,(a\ell + bk + k\ell m)$。（依据：因式分解。）
- 括号里的 $a\ell + bk + k\ell m$ 是整数（整数对加减乘封闭）。
- 故 $m \mid (cd - ab)$，即 $a\cdot b \equiv c\cdot d \pmod m$。$\blacksquare$
【证明机制解说】：这个证明的核心只有一句话——「同余差 $m$ 的倍数」这件事在加法与乘法下会自我繁殖。加法时倍数线性相加；乘法时倍数乘上别的整数，仍然是 $m$ 的倍数。注意第 3 步展开后出现的 $m^2$ 项也带着 $m$，这不是巧合：它说明 $m\mathbb{Z}$ 不仅是加法子群，还是环 $\mathbb{Z}$ 的理想 (ideal)。这个性质正是「模运算可以做任意多次加、减、乘」这一事实的代数根基。
关于「良定义性 (well-definedness)」的重要说明：
定理 5.1 的真正意义不是「两个同余式可以相加」，而是：
在 $\mathbb{Z}_m$ 上定义 $[a]_m + [b]_m := [a+b]_m$、$[a]_m \cdot [b]_m := [a\cdot b]_m$ 时，结果不依赖于我们为每个等价类挑选了哪个代表元。
如果没有这个定理，上述定义就是一句空话：因为 $[2]_{12}$ 的代表元可以是 $2$，也可以是 $14$、$-10$、$38$；我们凭什么保证「$[2]+[1]$」用 $2+1$ 算出 $3$，而用 $14+1$ 算出 $15$，两者代表的是同一个类？定理 5.1 恰好保证了 $15 \equiv 3 \pmod{12}$，所以两种选法结果一致。任何「通过代表元定义类之间的运算」的构造，都必须先过这一关——这就是数学里「良定义性检验」的标准范式，后面 Lecture 7 用多项式插值定义秘密共享、Lecture 8 定义有限域上的编码，都要重复同样的检验。
推论 4.1（中途归约律）：在只含加、减、乘的任意算术表达式中，可以把任意中间结果先模 $m$ 再继续计算，最终结果不变。
证明：对表达式的结构做归纳（Lecture 3 的结构归纳思想）。基础情形是单个变量或常量，归约后同余不变。归纳步骤：设两个子表达式的值 $u,v$ 分别同余于其归约值 $u^{\prime},v^{\prime}$，则由定理 5.1 得 $u+v \equiv u^{\prime}+v^{\prime}$ 与 $uv \equiv u^{\prime}v^{\prime}$；减法同理（因为 $u - v \equiv u^{\prime} - v^{\prime}$ 可由定理 5.1 先对 $-v \equiv -v^{\prime}$ 用一次，再对加法用一次得到）。$\blacksquare$
具体算例（中途归约）：计算 $(13+11)\cdot 18 \bmod 7$。
\[\begin{aligned} (13+11)\cdot 18 &\equiv (6+4)\cdot 4 &&\text{（}13\equiv 6,\ 11\equiv 4,\ 18\equiv 4 \pmod 7\text{）}\\ &= 10\cdot 4\\ &\equiv 3\cdot 4 &&\text{（}10\equiv 3 \pmod 7\text{）}\\ &= 12\\ &\equiv 5 \pmod 7 &&\text{（}12 \equiv 5 \pmod 7\text{）} \end{aligned}\]脚本验算：$(13+11)\times 18 = 432$，$432 \bmod 7 = 5$。两条路殊途同归，且第二条路全程没让中间结果超过 $12$ ——这就是归约的实际价值：把大数运算变成小数运算。
引理 4.2（有限集上「有左逆」即双射）：设 $A$ 是有限集，$f: A \to A$。若存在函数 $g: A \to A$ 使 $\forall x \in A,\ g(f(x)) = x$，则 $f$ 是双射。
证明策略：直接证明，先证单射再证满射。这是 Lecture 2「有限集上单射即满射」的精确形式化，也是定理 5.2 中「乘以 $x$ 是双射」这一断言的独立论证方式。
逐步推导：
- $f$ 是单射：设 $f(x) = f(x^{\prime})$。两边同施 $g$ 得 $g(f(x)) = g(f(x^{\prime}))$。
- 由 $g$ 的定义 $g(f(x)) = x$、$g(f(x^{\prime})) = x^{\prime}$，故 $x = x^{\prime}$。单射得证。
- $f$ 是满射：单射意味着 $A$ 中 $\vert A\vert $ 个元素映射到 $\vert A\vert $ 个互不相同的像，故 $f$ 的值域大小恰为 $\vert A\vert $。
- 而值域 $\subseteq A$ 且 $\vert A\vert $ 有限，大小相同的子集只能是 $A$ 本身，故值域 $= A$，即 $f$ 满射。
- 单射 + 满射 = 双射。$\blacksquare$
【证明机制解说】：这里「有限性」是关键且不可省的。在无限集上，单射不必是满射（例如 $f(n)=n+1$ 在 $\mathbb{N}$ 上是单射但值域漏掉了 $0$）。所以 CS70 里凡是写「一一 $\Rightarrow$ 满」，都必须先确认集合有限——Lecture 5 的费马小定理、Lecture 14 的计数双射都依赖这个前提。把这条引理套用到定理 5.2 上：$A = \mathbb{Z}_m$（有限），$f([a]) = [ax]_m$，而「$x$ 可逆」提供的正好是那个 $g([b]) = [b x^{-1}]_m$。两条路径（鸽笼原理 / 左逆引理）结论一致，只是叙述的抽象层级不同。
反例 4.1（除法不能自由进行）：定理 5.1 对除法没有对应结论。取 $m=6$，$a = 2\cdot 3$、$c = 2 \cdot 0$：
\[2\cdot 3 = 6 \equiv 0 \equiv 2\cdot 0 \pmod 6,\]即 $2\cdot 3 \equiv 2\cdot 0 \pmod 6$ 成立，但
\[3 \not\equiv 0 \pmod 6 \quad(\text{因为 } 6 \nmid 3).\]所以「从 $2\cdot 3 \equiv 2\cdot 0$ 消去 $2$」这一步是非法的。更直白地写：$2x \equiv 2y \pmod 6$ 推不出 $x \equiv y \pmod 6$。失灵的根源是 $\gcd(2,6)=2>1$，即 $2$ 在模 $6$ 下没有乘法逆元。下面的消去律（推论 4.3）会精确标出什么时候可以消。
定理 5.2（逆元存在性）：设 $m,x$ 为正整数且 $\gcd(m,x)=1$。则 $x$ 在模 $m$ 下有乘法逆元，且该逆元模 $m$ 唯一。
证明策略：反证法 + 鸽笼原理（双射论证）。官方 Note 5 的思路是：考虑 $m$ 个数 $0, x, 2x, \dots, (m-1)x$。先证这 $m$ 个数两两不同余（用反证法，并由 $\gcd(m,x)=1$ 推出矛盾），于是它们是 $\mathbb{Z}_m$ 上的一次一一映射 (bijection)；再数一数「只有 $m$ 个不同的余数」这一事实，就逼出「$1$ 一定出现在这个序列里」，那个位置就是逆元。选择这个策略的原因是：我们手里唯一的信息是「互质」这个乘法性质，而反证法能把「互质」转化为「整除的排除条件」，这是整除语言最好用的地方。
逐步推导：
- 构造序列 $T = \{\, 0\cdot x,\ 1\cdot x,\ 2\cdot x,\ \dots,\ (m-1)\cdot x \,\}$，共 $m$ 个整数（可能有重复的数值，但作为「带索引的项」有 $m$ 项）。
- 断言：这 $m$ 项模 $m$ 两两不同余。
- 用反证法证明断言：假设存在 $a,b$ 满足 $0 \le b < a \le m-1$（即 $a \neq b$）但
- 移项得 $(a-b)x \equiv 0 \pmod m$，按定义即存在整数 $k$ 使
- 由 $\gcd(m,x)=1$ 知 $m$ 与 $x$ 不含任何大于 $1$ 的公因子。式 (4.1) 说明 $m$ 整除乘积 $(a-b)x$，而 $m$ 与 $x$ 互质，故 $m$ 必须整除 $a-b$。（这一步的严格依据是「欧几里得引理」：$\gcd(m,x)=1$ 且 $m \mid xz$ $\Rightarrow$ $m \mid z$；它在 Lecture 5 用扩展欧几里得算法给出完整证明。这里先引用。）
- 但 $1 \le a-b \le m-1$（由 $0\le b < a \le m-1$），所以 $a-b$ 落在 $1$ 与 $m-1$ 之间，不可能是 $m$ 的正倍数，也非 $0$。
- 这就与步骤 5 矛盾。断言得证。（依据：反证法。）
- 断言说明「乘以 $x$」这个映射 $f([a]_m) = [ax]_m$ 是一一的 (one-to-one)。
- 而定义域与陪域都是有限集 $\mathbb{Z}_m$（大小 $m$），一一映射在一一对应的有限集上必然是满射 (onto)——这正是 Lecture 2 里「有限集上一一即满」的鸽笼原理直接推论（$m$ 只鸽子放进 $m$ 个笼子且不重合，则每个笼子恰好一只）。
- 于是 $1 \in \mathbb{Z}_m$ 必是某个 $[ax]_m$ 的像：存在唯一（模 $m$）的 $a$ 使 $ax \equiv 1 \pmod m$。
- 这个 $a \bmod m$ 就是 $x$ 的乘法逆元；由唯一性（步骤 10 的「唯一」）知逆元模 $m$ 唯一。$\blacksquare$
【证明机制解说】：整个证明是「带索引的 $m$ 个数 + 两两不同余 $\Rightarrow$ 恰好铺满 $\mathbb{Z}_m$」这一鸽笼原理的标准用法。请特别注意索引与数值的区别：$0,x,\dots,(m-1)x$ 有 $m$ 个索引，它们映射到最多 $m$ 个余数；「不同余」说明映射是单射，于是 $m$ 个索引必然覆盖全部 $m$ 个余数，一个不漏。这个「单射 + 有限 + 定义域陪域等势 $\Rightarrow$ 双射」的三步曲在本课程里反复出现：Lecture 5 证明费马小定理、Lecture 8 证明有限域结构、Lecture 14 做计数双射，用的都是同一招。
定理 5.2 的补集（必要性：$\gcd(m,x)=1$ 不可省）：若 $\gcd(m,x)=d>1$，则 $x$ 在模 $m$ 下没有乘法逆元。
证明策略：反证法。假设逆元存在，写出对应的（非模的）整除方程，然后从公因子 $d$ 出发制造矛盾——即把「$d>1$」逼到「$d \mid 1$」这个不可能。
逐步推导：
- 假设存在整数 $a$ 使 $ax \equiv 1 \pmod m$。
- 按定义，存在整数 $k$ 使 $ax - 1 = km$，即
- 设 $d = \gcd(m,x) > 1$。由定义 $d \mid m$ 且 $d \mid x$。
- 于是 $d \mid ax$（因为 $d \mid x$）且 $d \mid km$（因为 $d \mid m$）。
- $d$ 整除 $(ax - km)$。（依据：Lecture 0 中「若 $d$ 整除两数则整除其差」。）
- 由式 (4.2)，$d \mid 1$。
- 但 $d>1$ 是正整数，不可能整除 $1$。矛盾。
故假设不成立，$x$ 模 $m$ 无逆元。$\blacksquare$
【证明机制解说】：这个证明之所以只有五行却很有力，是因为它揭示了一个不变量：在模 $m$ 下，凡是「能表示成 $ax + bm$ 形式的整数」，一定都被 $\gcd(x,m)$ 整除。逆元存在要求 $1$ 能被这样表示，那就必须 $\gcd(x,m)=1$。这句话下一讲会被正面用出来（Bézout 等式：$\gcd(x,m)$ 本身总能写成 $ax+bm$），从而把「互质」与「可逆」彻底等价起来。注意 $\gcd(m,x)=1$ 是充要条件，不是充分条件——这是本讲最容易写错的地方。
具体算例（可逆与不可逆）：
| $x$ | $m$ | $\gcd(x,m)$ | 逆元 $x^{-1} \bmod m$ | 验算 |
|---|---|---|---|---|
| $8$ | $15$ | $1$ | $2$ | $2\cdot 8 = 16 \equiv 1 \pmod{15}$ |
| $12$ | $35$ | $1$ | $3$ | $3\cdot 12 = 36 \equiv 1 \pmod{35}$ |
| $3$ | $7$ | $1$ | $5$ | $5\cdot 3 = 15 \equiv 1 \pmod{7}$ |
| $12$ | $15$ | $3$ | 不存在 | 序列 $12,9,6,3,0,\dots$ 中 $1$ 永不出现 |
| $2$ | $4$ | $2$ | 不存在 | $2a \bmod 4 \in \{0,2\}$，永不为 $1$ |
推论 4.3（消去律 / Cancellation Law）：设 $\gcd(c,m)=1$。若 $ca \equiv cb \pmod m$，则 $a \equiv b \pmod m$。
证明策略：构造性 + 直接证明。既然 $c$ 可逆，就把两边同乘 $c^{-1}$——这正是「模运算里的除法」。存在性由定理 5.2 保证，所以这一步合法。
逐步推导：
- 由 $\gcd(c,m)=1$ 及定理 5.2，存在整数 $c^{-1}$ 使 $c\,c^{-1} \equiv 1 \pmod m$。
- 两边同乘 $c^{-1}$：$c^{-1}(ca) \equiv c^{-1}(cb) \pmod m$。（依据：定理 5.1 的乘法部分——同余式两端可同乘一个整数。）
- 左端 $c^{-1}ca \equiv (c^{-1}c)a \equiv 1\cdot a = a \pmod m$。（依据：结合律 + 逆元定义 + 定理 5.1。）
- 右端同理 $\equiv b \pmod m$。
- 由传递性得 $a \equiv b \pmod m$。$\blacksquare$
反例 4.2（消去律的条件不可省）：取 $c=2,\ m=6$，则 $\gcd(2,6)=2>1$。此时 $2\cdot 1 \equiv 2 \pmod 6$ 且 $2\cdot 4 = 8 \equiv 2 \pmod 6$，所以 $2\cdot 1 \equiv 2\cdot 4 \pmod 6$，但 $1 \not\equiv 4 \pmod 6$。「消去 $c$」这一步是否合法，完全取决于 $\gcd(c,m)$ 是否等于 $1$。
补充：快速幂算法的正确性（归纳证明，官方 Note 5 的习题）
命题：对 $y \ge 0$，算法 mod-exp(x,y,m) 返回 $x^y \bmod m$，其中 $m>1$。
证明策略：对 $y$ 做强归纳 (strong induction)（Lecture 3）。之所以用强归纳而非普通归纳，是因为递归调用发生在 $y \operatorname{div} 2 = \lfloor y/2 \rfloor$ 上，它比 $y-1$ 小得多且不连续，强归纳假设「所有小于 $y$ 的值都正确」才能覆盖。
逐步推导：
- 基础情形 $y=0$：算法返回 $1$，而 $x^0 = 1 \equiv 1 \pmod m$。正确。
- 归纳假设：设对所有 $0 \le z < y$ 及任意 $x$，
mod-exp(x,z,m)返回 $x^z \bmod m$。 - 归纳步骤：设 $y>0$，令 $a = \lfloor y/2 \rfloor$，则 $y \in \{2a, 2a+1\}$。
- 算法计算 $z = $
mod-exp(x, a, m)。因 $a < y$，由归纳假设 $z \equiv x^a \pmod m$。 - 情形 $y = 2a$（偶数）：算法返回 $z\cdot z \bmod m$。而 $z^2 \equiv (x^a)^2 = x^{2a} = x^y \pmod m$。（依据：定理 5.1 + 幂的乘法律。）
- 情形 $y = 2a+1$（奇数）：算法返回 $x\cdot z\cdot z \bmod m$。而 $x z^2 \equiv x\,(x^a)^2 = x^{2a+1} = x^y \pmod m$。
- 两种情形都返回 $x^y \bmod m$，故 $P(y)$ 成立。由强归纳，命题对所有 $y\ge 0$ 成立。$\blacksquare$
复杂度：每次递归把 $y$ 换成 $\lfloor y/2\rfloor$，故递归深度等于 $y$ 的比特数 $n$；每次调用只做常数次乘法与取模，故总代价 $O(n)$ 次算术运算。朴素连乘需要 $y$ 次运算，本例中 $y$ 可达 $2^{n}-1$，即指数级差距。
具体算例（完整手算两次快速幂）：
算例 A：$3^{11} \bmod 7$。先列表做好平方（每行是上一行结果的平方再取模）：
| 步骤 | 计算 | 结果 |
|---|---|---|
| $3^{1}$ | 基础 | $3$ |
| $3^{2}$ | $3^2 = 9$，$9 \bmod 7$ | $2$ |
| $3^{4}$ | $2^2 = 4$，$4 \bmod 7$ | $4$ |
| $3^{8}$ | $4^2 = 16$，$16 \bmod 7$ | $2$ |
现在 $11 = 8 + 2 + 1$（二进制 $1011$），故
\[3^{11} \equiv 3^8\cdot 3^2\cdot 3^1 \equiv 2\cdot 2\cdot 3 = 12 \equiv 5 \pmod 7 .\]脚本验算：$3^{11} = 177147$，$177147 \bmod 7 = 5$。✔
算例 B：$5^{13} \bmod 11$（$13 = 8+4+1$，二进制 $1101$）：
| 步骤 | 计算 | 结果 |
|---|---|---|
| $5^{1}$ | 基础 | $5$ |
| $5^{2}$ | $25 \bmod 11$ | $3$ |
| $5^{4}$ | $3^2 = 9$，$9 \bmod 11$ | $9$ |
| $5^{8}$ | $9^2 = 81$，$81 \bmod 11 = 81-77$ | $4$ |
脚本验算：$5^{13} = 1220703125$，$1220703125 \bmod 11 = 4$。✔
算例 C（定理 5.1 的加乘同余）：$a = 14,\ b = 25,\ m = 12$（官方 Note 5 的例子）。
- $a \equiv 2 \pmod{12}$（$14 = 1\cdot 12 + 2$），$b \equiv 1 \pmod{12}$（$25 = 2\cdot 12+1$）。
- 加法：$a+b = 39 \equiv 3$；先归约再算 $2+1 = 3$。✔（$39 = 3\cdot 12+3$）
- 乘法：$ab = 350$；$350 = 29\cdot 12 + 2$，故 $\equiv 2$；先归约再算 $2\cdot 1 = 2$。✔
- 减法：$a - b \equiv 2 - 1 = 1$；直接算 $14-25 = -11$，$-11 + 12 = 1$。✔
算例 D（模 $7$ 的完整乘法表与逆元速查）：把 $i\cdot j \bmod 7$ 全部列出，可以直接「看出」每个非零元素的逆元。
模 7 乘法表 (i * j mod 7)
j=0 1 2 3 4 5 6
i=0 | 0 0 0 0 0 0 0
1 | 0 1 2 3 4 5 6
2 | 0 2 4 6 1 3 5
3 | 0 3 6 2 5 1 4
4 | 0 4 1 5 2 6 3
5 | 0 5 3 1 6 4 2
6 | 0 6 5 4 3 2 1
观察 1：除第 0 行/列外，每一行都是 {1,2,3,4,5,6} 的一个排列
--> 这正是定理 5.2 的「双射」结论的可视化
观察 2：数字 1 出现的位置即逆元对：
1^-1=1, 2^-1=4, 3^-1=5, 4^-1=2, 5^-1=3, 6^-1=6
观察 3：第 0 行/列中 0 之外还出现别处，说明模 7 是「域」般干净
（因为 7 是质数）；而模 15 时 12*5=0 会破坏这个整齐性
脚本验算：上表每一行都独立用程序生成比对，$2\cdot 4 = 8 \equiv 1$、$3\cdot 5 = 15 \equiv 1 \pmod 7$ 均成立。✔
与经典问题的联系
（一）密码学与 RSA（Lecture 6 的主题）
RSA 的全部运算都发生在 $\mathbb{Z}_N$（$N=pq$，$p,q$ 是上千比特的质数）里：加密是 $E(x) \equiv x^e \pmod N$，解密是 $D(y) \equiv y^d \pmod N$。要让这套方案跑起来，必须有：
- 定理 5.1 保证「先乘再取模」与「先取模再乘」等价——否则每次幂运算的中间结果会膨胀到天文数字；
- 快速幂 把 $x^e \bmod N$ 的代价从 $e$ 次乘法降到 $O(\log e)$ 次；
- 定理 5.2 保证解密指数 $d \equiv e^{-1} \bmod (p-1)(q-1)$ 存在（因为 $e$ 被特意选成与 $(p-1)(q-1)$ 互质）。
（二）纠错码（Lecture 8）
纠错码需要在有限字母表上做线性代数（例如 GF(256)），也就是在一个大小为 $2^8$ 的「有限域」上做加减乘除。其中的除法正是本讲的乘法逆元；而 「每个非零元都可逆」这一性质（本讲在质数模数下证明的定理 5.2）正是域 (field) 的定义要件。
（三）不引入逆元的后果：为什么「模运算不能随便约分」是个安全问题
很多初学者把 $ax \equiv ay \pmod m$ 直接约掉 $a$。在 RSA 参数下这是致命的：$m$ 是合数（$N=pq$），许多 $a$ 与 $N$ 不互质，消去律失效。本讲的推论 4.3 给出了唯一合法约分的判据：先检查 $\gcd(a,m)=1$。
与其他讲次的关联
- 承接 Lecture 0（直接证明）：定理 4.0 与定理 5.1 的加法部分都是典型的「展开定义 → 代数操作 → 回到定义」的直接证明；「$d \mid a$ 且 $d \mid b \Rightarrow d \mid (a\pm b)$」这一工具在 Lecture 0 已备好，本讲只是反复调用。
- 承接 Lecture 2（鸽笼原理/有限集上一一即满）：定理 5.2 的存在性证明完全依赖「有限集上单射 $\Rightarrow$ 满射」。若没有 Lecture 2 的这条引理，我们就只能证明「这 $m$ 个数互不相同」，无法断言「$1$ 一定出现」。
- 承接 Lecture 3（归纳法）：推论 4.1 对表达式结构做归纳、快速幂正确性对指数 $y$ 做强归纳，都是 Lecture 3 技巧的直接应用。
- 通向 Lecture 5（欧几里得算法、FLT、CRT）：本讲留下了两个「欠账」——(a) 证明定理 5.2 时引用了「$\gcd(m,x)=1$ 且 $m \mid xz \Rightarrow m \mid z$」；(b) 说「逆元唯一且可计算」但没有给出算法。Lecture 5 的扩展欧几里得算法一次还清这两笔账，并给出 $x^{-1} \bmod m$ 的具体求法。同讲的费马小定理还提供 $a^{-1} \equiv a^{p-2} \pmod p$ 这条质数模数下的捷径。
- 通向 Lecture 6（RSA）：$x^{e}$ 与 $y^{d}$ 的计算 = 本讲快速幂；$d \equiv e^{-1} \bmod (p-1)(q-1)$ 的合法性 = 本讲定理 5.2。Lecture 6 的解密正确性证明依赖 Lecture 5 的费马小定理。
- 通向 Lecture 7–8（多项式与秘密共享/纠错码）：秘密共享要在有限域上解多项式方程组，而「有限域」的构造就是把 $\mathbb{Z}_p$（$p$ 为质数）这个结构中本讲的运算律完整继承下来。
- 通向 Lecture 20（哈希与负载均衡）：哈希函数的「模 $m$ 映射到 $m$ 个桶」正是剩余类划分；「模质数」比「模合数」分布更均匀的原因，也可从本讲 $\mathbb{Z}_p$ 的结构整齐性（乘法表每行是排列）看出端倪。
关键要点
- 同余的定义与两种等价视角：$a \equiv b \pmod m \iff m \mid (a-b) \iff a \bmod m = b \bmod m$。前者用于证明（代数操作方便），后者用于计算（数值归约方便）。
- 定理 5.1 是全部模运算的合法性基础：加、减、乘在模 $m$ 下自由进行、中途可任意归约；这条定理的实质是良定义性——类运算不依赖代表元。
- 除法必须换成乘逆元。$a \equiv b \pmod m$ 与 $ca \equiv cb \pmod m$ 之间只有在 $\gcd(c,m)=1$ 时才可互相推导；这是消去律（推论 4.3），不是普遍规律。
- 逆元存在当且仅当 $\gcd(x,m)=1$（充要条件）：存在性由鸽笼/双射论证（定理 5.2），必要性由「$d \mid ax - km = 1$ 而 $d>1$」的矛盾得出。逆元存在时模 $m$ 唯一。
- 快速幂把指数代价从 $O(y)$ 降到 $O(\log y)$：利用 $x^{2a}=(x^a)^2$ 与 $x^{2a+1}=x(x^a)^2$，递归深度 = 指数比特数。这是 RSA 可行的技术支柱之一。
- 黄金法则：在模 $m$ 下，你可以随便约简加减乘的中途结果，但绝不可以在没有检查 $\gcd$ 的情况下约简除/约分。
常见误区与注意事项
- 把「有余数」与「同余」混为一谈。
a mod m是一个数（落在 $\{0,\dots,m-1\}$）；$a \equiv b \pmod m$ 是一个命题（真/假）。写作时不要出现「$29 \bmod 12 \equiv 5 \pmod{12}$」这种把两者混写的表达式。 - 忘记模运算中除法需要逆元存在。看到 $ax \equiv ay \pmod m$ 就想约掉 $a$ 是最高频错误。反例：$2\cdot 1 \equiv 2\cdot 4 \pmod 6$ 但 $1 \not\equiv 4 \pmod 6$。正确做法：先算 $\gcd(a,m)$；只有为 $1$ 时才可约。
- 认为「非零数必有逆元」。$12$ 在模 $15$ 下非零却不可逆。实数里「只有 $0$ 不可逆」的直觉在模运算中完全失效，因为 $\mathbb{Z}_m$ 仅在 $m$ 为质数时才是域。
- 把定理 5.2 的条件记成充分条件。$\gcd(m,x)=1$ 是充要条件；漏写「且」或错写成「若 $\gcd>1$ 则……无逆元」都算对，但正说成「$\gcd=1$ 时可能有也可能没有逆元」就错了——一定有，且唯一。
- 快速幂把 $y \operatorname{div} 2$ 写成 $y/2$。当 $y$ 是奇数时 $y/2$ 不是整数，取整方向必须是向下取整 $\lfloor y/2 \rfloor$；相应地奇偶分支的那次「多乘一个 $x$」不能漏。
- 定理 5.1 的乘法证明漏掉 $m^2$ 项。展开 $(a+km)(b+\ell m)$ 时必须写出四项，$k\ell m^2$ 虽小但必须显式说明它也是 $m$ 的倍数，否则「$m \mid (cd-ab)$」的结论缺一步依据。
- 负数的取模。$-11 \bmod 12$ 在数学约定下是 $1$（最小非负余数），而某些编程语言的
%会给出 $-11$。写证明时以数学约定（$0 \le r \le m-1$）为准。
思考题（带答案）
Q1.（计算题） 求 $7^{203} \bmod 11$。（要求写出反复平方的中间表，不要直接给结果。）
答案
先建立 $7$ 的 2 的幂次表（每步平方取模）： | 幂 | 计算 | 结果 mod 11 | |:---|:---|:---| | $7^{1}$ | — | $7$ | | $7^{2}$ | $49 = 4\\cdot 11 + 5$ | $5$ | | $7^{4}$ | $5^2 = 25 = 2\\cdot 11+3$ | $3$ | | $7^{8}$ | $3^2 = 9$ | $9$ | | $7^{16}$ | $9^2 = 81 = 7\\cdot 11+4$ | $4$ | | $7^{32}$ | $4^2 = 16 = 11+5$ | $5$ | | $7^{64}$ | $5^2 = 25$ | $3$ | | $7^{128}$ | $3^2=9$ | $9$ | $203 = 128+64+8+2+1 = (11001011)_2$（校验：$128+64+8+2+1 = 203$ ✔）。 $$7^{203} \equiv 7^{128}\cdot 7^{64}\cdot 7^{8}\cdot 7^{2}\cdot 7^{1} \equiv 9\cdot 3\cdot 9\cdot 5\cdot 7 \pmod{11}.$$ 逐步归约：$9\\cdot 3 = 27 \\equiv 5$；$5\\cdot 9 = 45 \\equiv 1$；$1\\cdot 5 = 5$；$5\\cdot 7 = 35 \\equiv 2 \\pmod{11}$。 **答案：$7^{203} \\equiv 2 \\pmod{11}$。**（脚本验算：$7^{203} \\bmod 11 = 2$ ✔） 注意这里出现了一个可做交叉验证的规律：$7^{32} \\equiv 5 \\equiv 7^{2} \\pmod{11}$，说明 $7$ 的幂在模 $11$ 下的**最小正周期是 $10$**（脚本列出 $7^1,\\dots,7^{10}$ 为 $7,5,2,3,10,4,6,9,8,1$，到第 $10$ 次才回到 $1$）。于是 $203 \\bmod 10 = 3$，$7^{203} \\equiv 7^{3} \\equiv 2 \\pmod{11}$ ✔。这个「周期恰为 $p-1$（或它的因子）」的现象，正是 Lecture 5 费马小定理 $a^{p-1}\\equiv 1 \\pmod p$ 的实例。Q2.（概念/证明题） 判断下列命题真假，为真者给出证明，为假者给出反例：
(a) 若 $a \equiv b \pmod m$ 且 $c \equiv d \pmod m$，则 $a - c \equiv b - d \pmod m$。 (b) 若 $a \equiv b \pmod m$，则 $2a \equiv 2b \pmod{2m}$。 (c) 若 $x^2 \equiv y^2 \pmod p$（$p$ 为质数），则 $x \equiv y \pmod p$ 或 $x \equiv -y \pmod p$。 (d) 若 $ax \equiv ay \pmod m$ 且 $a \not\equiv 0 \pmod m$，则 $x \equiv y \pmod m$。
答案
**(a) 真。** 由 $a \\equiv b$ 得 $m \\mid (a-b)$；由 $c \\equiv d$ 得 $m \\mid (c-d)$。于是 $m \\mid \\big[(a-b) - (c-d)\\big] = \\big[(a-c)-(b-d)\\big]$，即 $a-c \\equiv b-d \\pmod m$。（也可以说：先由对称性得 $-c \\equiv -d$，再用定理 5.1 的加法部分。） **(b) 真。** $a \\equiv b \\pmod m$ 意味着存在整数 $k$ 使 $a - b = km$。两边乘 $2$：$2a - 2b = 2km = k(2m)$，故 $2m \\mid (2a-2b)$，即 $2a \\equiv 2b \\pmod{2m}$。这是定理 5.1 的一个「模数也一起放大」的变体，注意**模数必须同步放大**才成立。 **(c) 真。** $x^2 \\equiv y^2 \\pmod p$ 推出 $x^2 - y^2 \\equiv 0$，即 $(x-y)(x+y) \\equiv 0 \\pmod p$，也就是 $p \\mid (x-y)(x+y)$。由欧几里得引理（$p$ 为质数且 $p \\mid uv \\Rightarrow p\\mid u$ 或 $p \\mid v$），得 $p \\mid (x-y)$ 或 $p \\mid (x+y)$，即 $x \\equiv y$ 或 $x \\equiv -y \\pmod p$。**注意：结论里的「或」是真析取——两者可以同时成立**（当 $p=2$ 或 $x\\equiv y \\equiv 0$ 时）；而且这个结论对**合数模数失效**：$m=8$ 时 $1^2 = 1$、$3^2 = 9 \\equiv 1 \\pmod 8$，但 $3 \\not\\equiv \\pm 1 \\pmod 8$（$3 \\not\\equiv 1$，$3 \\not\\equiv 7$）。 **(d) 假。** 反例：$m=6$，$a=2$，$x=1$，$y=4$。则 $a \\not\\equiv 0 \\pmod 6$（$2 \\not\\equiv 0$），$2\\cdot 1 = 2$、$2\\cdot 4 = 8 \\equiv 2 \\pmod 6$，故 $ax \\equiv ay$；但 $1 \\not\\equiv 4 \\pmod 6$。**根源**：$\\gcd(a,m) = \\gcd(2,6) = 2 > 1$，消去律（推论 4.3）不适用。「$a \\not\\equiv 0$」远不足以推出可消去——正确的条件是 $\\gcd(a,m)=1$。Q3.（概念题） 定理 5.2 的证明中，为什么要考察 $0,x,2x,\dots,(m-1)x$ 这 $m$ 个数，而不是 $1,x,2x,\dots,(m-1)x$ 这 $m-1$ 个数？如果只取 $m-1$ 个数，鸽笼原理那一步还能用吗？