企业官网建设流程全解析

• 文档
• 教程
• 教育

本文基于《算法导论》第三版第 31 章「数论算法」第 31.3 节「模运算」（Modular Arithmetic）的习题解答文档 docs/Chap31/31.3.md 展开，系统梳理该节全部 5 道习题的完整推导：包括 $(\mathbb Z_4, +4)$ 与 $(\mathbb Z_5^*, \cdot_5)$ 的群运算表及同构构造、$\mathbb Z_9$ 与 $\mathbb Z{13}^*$ 的全部子群枚举（Lagrange 定理 + 原根）、定理 31.14 的证明、欧拉函数素数幂公式 $\phi(p^e)=p^{e-1}(p-1)$，以及模 $n$ 单位群上的乘法置换性质。读完本文，你将掌握群、子群、同构、原根、欧拉函数等模运算核心概念在数论算法中的落地证明思路，并能直接复用于后续章节的模线性方程求解、中国剩余定理与 RSA 公钥体制。

一、本节定位：模运算在第 31 章数论算法中的角色

第 31 章「数论算法」按「初等数论概念 → 最大公约数 → 模运算 → 模线性方程 → 中国剩余定理 → 元素的幂 → RSA → 素性测试 → 整数分解」的脉络组织（见 mkdocs.yml 中的章节导航），其中31.3 节「模运算」是承上启下的枢纽：

• 承上：31.1 节定义了整除、素数、$\gcd$ 与欧拉函数 $\phi$ 等基本概念；31.2 节给出了 EUCLID 与 EXTENDED-EUCLID 算法（docs/Chap31/31.2.md），用于计算模逆元。
• 启下：31.4 节求解模线性方程 $ax \equiv b \pmod n$ 需要单位（unit）的概念；31.6 节「元素的幂」讨论原根、阶与离散对数 $\text{ind}_{n,g}(x)$（docs/Chap31/31.6.md）；31.7 节 RSA 的核心依据正是欧拉定理 $a^{\phi(n)} \equiv 1 \pmod n$（docs/Chap31/31.7.md）。

本节引入的两类基本群结构贯穿全章：

• 加法群$\mathbb Z_n = {0, 1, \dots, n-1}$，运算为模 $n$ 加法 $+_n$；
• 乘法群（单位群）$\mathbb Z_n^* = {x \in \mathbb Z_n : \gcd(x, n) = 1}$，运算为模 $n$ 乘法 $\cdot_n$，其元素个数恰为欧拉函数值 $\phi(n)$。

31.3 节的 5 道习题（31.3-1 ~ 31.3-5）正是围绕这两类群的结构、子群、同构与置换展开的。

二、习题 31.3-1：绘制运算表并证明 $\mathbb Z_4$ 与 $\mathbb Z_5^*$ 同构

题目：画出群 $(\mathbb Z_4, +_4)$ 与 $(\mathbb Z_5^*, \cdot_5)$ 的群运算表，并通过给出元素之间的一一对应 $\alpha$ 证明这两个群同构，使得

$$a + b \equiv c \pmod 4 \iff \alpha(a) \cdot \alpha(b) \equiv \alpha(c) \pmod 5.$$

$\mathbb Z_4$ 的运算表（模 4 加法）：

$\mathbb Z_5^*$ 的运算表（模 5 乘法，元素为与 5 互素的 ${1,2,3,4}$）：

构造同构：定义

$$\alpha : \mathbb Z_4 \to \mathbb Z_5^*, \quad \alpha(x) = 2^{x} \bmod 5.$$

逐一验证该映射是双射：$\alpha(0)=1,\ \alpha(1)=2,\ \alpha(2)=4,\ \alpha(3)=8 \bmod 5 = 3$，恰好把 $\mathbb Z_4$ 的 4 个元素一一对应到 $\mathbb Z_5^*$ 的 4 个元素 ${1,2,3,4}$。

同构条件成立：由于模 5 乘法中 $2$ 的阶（order）恰为 4（$2^1=2,\ 2^2=4,\ 2^3=3,\ 2^4=1 \pmod 5$），指数运算在模 4 意义下"还原"了加法：

$$a + b \equiv c \pmod 4 \iff 2^{a} \cdot 2^{b} \equiv 2^{a+b} \equiv 2^{c} \pmod 5.$$

这正是题目要求的充要条件。从结构上看，$\mathbb Z_5^*$ 是 4 阶循环群，$2$ 是其生成元（即原根）；两个 4 阶循环群必然同构，本题把这一抽象结论落到了具体的运算表与映射上。这也为 31.6 节「原根」与离散对数的讨论（docs/Chap31/31.6.md）埋下伏笔。

三、习题 31.3-2：枚举 $\mathbb Z_9$ 与 $\mathbb Z_{13}^*$ 的全部子群

题目：列出 $\mathbb Z_9$ 与 $\mathbb Z_{13}^*$ 的所有子群。

由Lagrange 定理，有限群的子群阶必整除群的阶。$\mathbb Z_9$ 的阶为 9，因此其子群阶只能是 $1, 3, 9$，对应的子群为（注意原解答采用 1 起始记法，$\{3,6,9\}$ 即标准的 ${0,3,6}$，$\{1\}$ 即平凡子群 ${0}$）：

• $\{1\} \cong \mathbb Z_1$（平凡子群，仅含单位元 0）；
• $\{3, 6, 9\} \cong \mathbb Z_3$（即 ${0, 3, 6}$，模 9 下是 3 阶循环子群）；
• $\mathbb Z_9$ 自身（9 阶，注意 $\mathbb Z_9$ 作为循环群并不同构于 $\mathbb Z_3^2$，后者是非循环的 9 阶群）。

对于 $\mathbb Z_{13}^*$：其元素是模 13 的全部单位 ${1, 2, \dots, 12}$，阶为 12，且由 $2$ 生成，即

$$\mathbb Z_{13}^* = \langle 2 \rangle = {2^0, 2^1, \dots, 2^{11}} \pmod{13}.$$

（验证：$2^1=2,\ 2^2=4,\ 2^3=8,\ 2^4=3,\ 2^5=6,\ 2^6=12 \equiv -1,\ 2^7=11,\ 2^8=9,\ 2^9=5,\ 2^{10}=10,\ 2^{11}=7,\ 2^{12}=1$，确实遍历 ${1,\dots,12}$。）循环群 $\langle 2 \rangle$ 的子群与其阶 12 的因子一一对应：对每个满足 $n \mid 12$ 的 $n$，子群为 $\langle 2^n \rangle$。于是：

• $\langle 2^1 \rangle = \langle 2 \rangle$（12 阶，整个群）；
• $\langle 2^2 \rangle = \langle 4 \rangle$（6 阶）；
• $\langle 2^3 \rangle = \langle 8 \rangle$（4 阶，元素 ${1,8,12,5}$）；
• $\langle 2^4 \rangle = \langle 3 \rangle$（3 阶，因为 $2^4 \equiv 3 \pmod{13}$）；
• $\langle 2^6 \rangle = \langle -1 \rangle$（2 阶，因为 $2^6 \equiv 12 \equiv -1 \pmod{13}$）；
• $\langle 2^{12} \rangle = \langle 1 \rangle$（1 阶，平凡子群）。

值得注意：原文的表述"generators are $\langle 2^n \rangle$"在措辞上略欠严谨——更准确地说，是"由 $2^n$ 生成的子群 $\langle 2^n \rangle$"恰好遍历 $\mathbb Z_{13}^*$ 的全部子群，且每个子群恰好出现一次（$2^n$ 的阶为 $12/\gcd(12,n)$，随 $n \mid 12$ 取遍 12 的所有因子）。这一"循环群子群与阶因子一一对应"的结论是后续 31.6 节计算元素阶、31.8 节分析 Carmichael 数（见 docs/Chap31/31.8.md）时的基础工具。

四、习题 31.3-3：证明定理 31.14——有限群的封闭非空子集是子群

定理 31.14：有限群的非空封闭子集必为子群。

设 $G$ 是有限群，$S \subseteq G$ 非空，且对任意 $a, b \in S$ 有 $ab \in S$（封闭性）。逐条验证子群的四条公理：

• 封闭性（Closure）：由假设直接给出。
• 单位元（Identity）：任取 $a \in S$，由封闭性知 $a, a^2, a^3, \dots$ 全部落在 $S$ 中。由于 $S$ 有限，幂序列必有周期，即存在 $m > n$ 使得 $a^{(m)} = a^{(n)}$。在 $G$ 中两边同时乘 $a^{(-n)}$ 得 $a^{(m-n)} = e$（$e$ 为 $G$ 的单位元）；又因为 $m-n \ge 1$，$a^{m-n}$ 是 $a$ 的正幂次，仍在 $S$ 中，故 $e \in S$。
• 结合律（Associativity）：$S$ 中的元素都是 $G$ 的元素，结合律从原群 $G$ 继承。
• 逆元（Inverses）：对任意 $a \in S$，由上面的论证知存在 $k \ge 1$ 使 $a^{(k)} = e$。若 $k = 1$，则 $a = e$，其逆元就是自身 $e \in S$；若 $k > 1$，则 $a$ 的逆元为 $a^{(k-1)}$，因为

$$a \cdot a^{(k-1)} = a^{(k)} = e,$$

且 $a^{k-1}$ 是 $a$ 的正幂次，由封闭性仍在 $S$ 中。

综上，$S$ 在群的运算下封闭、含单位元、每个元素有逆元且运算满足结合律，故 $S$ 是 $G$ 的子群。这里"有限"是不可或缺的前提——它保证了幂序列必然产生重复（鸽巢原理），从而在不显式要求逆元存在的情况下推出单位元与逆元；对无限群，仅封闭性不足以保证构成子群（如整数加法群的封闭子集 $\mathbb N$ 并非子群）。

五、习题 31.3-4：欧拉函数对素数幂的公式 $\phi(p^e) = p^{e-1}(p-1)$

题目：证明若 $p$ 为素数、$e$ 为正整数，则

$$\phi(p^e) = p^{e - 1}(p - 1).$$

欧拉函数 $\phi(n)$ 定义为 $1$ 到 $n$ 之间与 $n$ 互素的整数个数。对素数幂 $p^e$，与 $p^e$ 不互素的整数恰好是 $p$ 的倍数：

$$p, 2p, 3p, \dots, p^{e-1} \cdot p,$$

共 $p^{e-1}$ 个。因此与 $p^e$ 互素的整数个数为

$$\phi(p^e) = p^e - p^{e-1} = p^e \cdot \left(1 - \frac{1}{p}\right) = p^{e - 1}(p - 1).$$

这条公式是整个第 31 章多条定理的基石：

• 31.6 节的逆元公式：由欧拉定理 $a^{\phi(n)} \equiv 1 \pmod n$，可得 $a^{-1} \equiv a^{\phi(n)-1} \pmod n$（见 docs/Chap31/31.6.md 的 31.6-3），而 $\phi(n)$ 的具体值正依赖素数幂公式；
• RSA 密钥计算：当 $n = pq$ 为两个素数之积时，$\phi(n) = (p-1)(q-1)$（docs/Chap31/31.7.md 的 31.7-1 中 $p=11, q=29$ 时 $\phi(n) = 280$ 即由此得出），私钥指数 $d = e^{-1} \bmod \phi(n)$ 的求解直接建立在这条公式之上。

六、习题 31.3-5：$f_a(x) = ax \bmod n$ 是 $\mathbb Z_n^*$ 上的置换

题目：证明对任意整数 $n > 1$ 与任意 $a \in \mathbb Z_n^*$，函数

$$f_a : \mathbb Z_n^* \to \mathbb Z_n^*, \quad f_a(x) = ax \bmod n$$

是 $\mathbb Z_n^*$ 的一个置换（即双射）。

要证明 $f_a$ 是置换，需要证明两点：

1. 映射到自身（封闭性）：对每个 $x \in \mathbb Z_n^*$，有 $f_a(x) \in \mathbb Z_n^*$。因为 $a \in \mathbb Z_n^*$ 与 $x \in \mathbb Z_n^*$ 都满足 $\gcd(a,n)=\gcd(x,n)=1$，两个与 $n$ 互素的数之积 $ax$ 仍与 $n$ 互素，故 $ax \bmod n$ 也是单位，落在 $\mathbb Z_n^*$ 内。
2. 单射性（生成的值互不相同）：假设存在两个不同的 $x, y \in \mathbb Z_n^*$ 使得 $f_a(x) = f_a(y)$，即

$$ \begin{aligned} f_a(x) & = f_a(y), \ ax \bmod n & = ay \bmod n, \ ax & \equiv ay \pmod n, \ n & \mid a(x - y). \end{aligned} $$

由于 $\gcd(a, n) = 1$，由 Euclid 引理知 $n \mid (x - y)$，即 $x \equiv y \pmod n$。而 $\mathbb Z_n^*$ 中每个元素代表一个互不相同的模 $n$ 剩余类，故 $x = y$，与假设矛盾。因此 $f_a$ 生成的 $f_a(x)$ 互不相同。

由于 $\mathbb Z_n^*$ 是含有 $\phi(n)$ 个元素的有限集合，从有限集到自身的单射必为双射，故 $f_a$ 是 $\mathbb Z_n^*$ 上的置换。原文的推导（见 docs/Chap31/31.3.md）核心正是"由 $f_a(x)=f_a(y)$ 推出 $x \equiv y \pmod n$，与 $x \ne y$ 矛盾"这一单射论证。

直觉与延伸：$\mathbb Z_n^*$ 中所有乘法置换 ${f_a : a \in \mathbb Z_n^*}$ 构成一个置换群。单位（unit）这一条件不可省略——若 $\gcd(a,n) > 1$，$f_a$ 会将不同的 $x$ 映射到同一个值（例如 $n=6, a=2$ 时 $f_2(1)=2$ 与 $f_2(4)=2$ 冲突），不再是置换。这一"单位乘法保持单射性"的结论是 31.4 节模线性方程 $ax \equiv b \pmod n$ 有唯一解（当 $\gcd(a,n)=1$）的群论根源，也与 31.7 节 RSA 中 $e$ 必须满足 $\gcd(e, \phi(n)) = 1$ 的要求一脉相承。

七、仓库中的相关资源与阅读指引

本解答出自 CLRS 习题解答仓库（CLRS，面向《算法导论》第三版，见 README.md），全部习题按章节以 Markdown 组织在 docs/Chap31 目录下，且站点通过 MkDocs + Material 主题构建、使用 KaTeX 渲染数学公式（见 mkdocs.yml 中extra_javascript对js/katex.js与 KaTeX CDN 的配置），因此文中的 $\LaTeX$ 公式可直接在渲染页面中阅读。

阅读 31.3 节习题时，建议按以下线索在仓库中交叉查阅：

• 群结构的"上游"工具：docs/Chap31/31.2.md 的 31.2-2（EXTENDED-EUCLID(899, 493)返回 $(29, -6, 11)$）、31.2-3 与 31.2-7 提供了求模逆元与推广 gcd 的算法，是判断 $a \in \mathbb Z_n^*$、计算 $a^{-1} \bmod n$ 的实际手段；
• 同构与子群的下游应用：docs/Chap31/31.6.md 的 31.6-1 计算 $\mathbb Z_{11}^*$ 中每个元素的阶并选取最小原根 $g=2$，正是 31.3-1、31.3-2 中"生成元/原根"思路的延续；31.6-2 给出从右向左扫描 $b$ 的二进制位的模幂算法，可用来验证 $2^x \bmod 5$ 这类幂运算；
• 欧拉函数的落地场景：docs/Chap31/31.7.md 的 31.7-1（$p=11, q=29, n=319, e=3$，解得 $d=187$）、31.7-2 全部依赖 31.3-4 的 $\phi(p^e)$ 公式与 $\phi(pq)=(p-1)(q-1)$；
• 置换性的相关论证：docs/Chap31/31.5.md（中国剩余定理）与 docs/Chap31/31.8.md（素性测试）中反复用到 $\gcd(a,n)=1$ 条件下单位乘法保持双射这一事实。

小结：31.3 节这 5 道习题从"画运算表、构造同构"的直观操作，逐步深入到"枚举子群（Lagrange + 原根）、证明有限封闭子集定理、推导欧拉函数公式、证明单位乘法是置换"的理论层面，为第 31 章后续所有算法（模逆、模线性方程、CRT、RSA、素性测试、分解）提供了群论与数论的双重基础。掌握本节推导，相当于拿到了理解整个数论算法章的一把钥匙。

• 文档
• 教程
• 教育