文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文基于《算法导论》第三版第 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.md31.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 加法$_4$012300123112302230133012$\mathbb Z_5^*$ 的运算表模 5 乘法元素为与 5 互素的 ${1,2,3,4}$$\cdot_5$123411234224133314244321构造同构定义$$\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^12,\ 2^24,\ 2^33,\ 2^41 \pmod 5$指数运算在模 4 意义下还原了加法$$a b \equiv c \pmod 4 \iff 2^{a} \cdot 2^{b} \equiv 2^{ab} \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^12,\ 2^24,\ 2^38,\ 2^43,\ 2^56,\ 2^612 \equiv -1,\ 2^711,\ 2^89,\ 2^95,\ 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 中 $p11, q29$ 时 $\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$ 是置换需要证明两点映射到自身封闭性对每个 $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^*$ 内。单射性生成的值互不相同假设存在两个不同的 $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$ 映射到同一个值例如 $n6, a2$ 时 $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-2EXTENDED-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}^*$ 中每个元素的阶并选取最小原根 $g2$正是 31.3-1、31.3-2 中生成元/原根思路的延续31.6-2 给出从右向左扫描 $b$ 的二进制位的模幂算法可用来验证 $2^x \bmod 5$ 这类幂运算欧拉函数的落地场景docs/Chap31/31.7.md 的 31.7-1$p11, q29, n319, e3$解得 $d187$、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、素性测试、分解提供了群论与数论的双重基础。掌握本节推导相当于拿到了理解整个数论算法章的一把钥匙。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第 8.1 节习题精解决策树模型与比较排序的 Ω(n lg n) 下界CLRS 第 8.1 节习题精解决策树模型与比较排序的 Ω n lg n 下界 导读本文基于本仓库 C08 Sorting in Linear Time/8文档教程示例工程freeCodeCamp Python 每日挑战第 40 题精讲Photo Storage 的单位换算与整除运算freeCodeCamp Python 每日挑战第 40 题精讲Photo Storage 的单位换算与整除运算 本篇指南围绕 freeCodeCamp 开源前端后端教育CLRS《算法导论》10.4 节习题精讲有根树的表示与 O(n) 遍历全解析CLRS《算法导论》10.4 节习题精讲有根树的表示与 O n 遍历全解析 本篇文章基于 CLRS 习题解答仓库中的 docs/Chap10/10.4.md文档教程教育上一篇告别孤岛协作ChuanhuChatGPT多人编辑与冲突解决全攻略下一篇Lynx-native高级特性CSS排版引擎与原生UI组件无缝集成终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/15 6:12:40 · 阅读 1.2k CLRS 第 31.3 节「模运算」习题精解：从群的运算表到模 n 单位群的置换性
文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文基于《算法导论》第三版第 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.md31.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 加法$_4$012300123112302230133012$\mathbb Z_5^*$ 的运算表模 5 乘法元素为与 5 互素的 ${1,2,3,4}$$\cdot_5$123411234224133314244321构造同构定义$$\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^12,\ 2^24,\ 2^33,\ 2^41 \pmod 5$指数运算在模 4 意义下还原了加法$$a b \equiv c \pmod 4 \iff 2^{a} \cdot 2^{b} \equiv 2^{ab} \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^12,\ 2^24,\ 2^38,\ 2^43,\ 2^56,\ 2^612 \equiv -1,\ 2^711,\ 2^89,\ 2^95,\ 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 中 $p11, q29$ 时 $\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$ 是置换需要证明两点映射到自身封闭性对每个 $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^*$ 内。单射性生成的值互不相同假设存在两个不同的 $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$ 映射到同一个值例如 $n6, a2$ 时 $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-2EXTENDED-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}^*$ 中每个元素的阶并选取最小原根 $g2$正是 31.3-1、31.3-2 中生成元/原根思路的延续31.6-2 给出从右向左扫描 $b$ 的二进制位的模幂算法可用来验证 $2^x \bmod 5$ 这类幂运算欧拉函数的落地场景docs/Chap31/31.7.md 的 31.7-1$p11, q29, n319, e3$解得 $d187$、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、素性测试、分解提供了群论与数论的双重基础。掌握本节推导相当于拿到了理解整个数论算法章的一把钥匙。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第 8.1 节习题精解决策树模型与比较排序的 Ω(n lg n) 下界CLRS 第 8.1 节习题精解决策树模型与比较排序的 Ω n lg n 下界 导读本文基于本仓库 C08 Sorting in Linear Time/8文档教程示例工程freeCodeCamp Python 每日挑战第 40 题精讲Photo Storage 的单位换算与整除运算freeCodeCamp Python 每日挑战第 40 题精讲Photo Storage 的单位换算与整除运算 本篇指南围绕 freeCodeCamp 开源前端后端教育CLRS《算法导论》10.4 节习题精讲有根树的表示与 O(n) 遍历全解析CLRS《算法导论》10.4 节习题精讲有根树的表示与 O n 遍历全解析 本篇文章基于 CLRS 习题解答仓库中的 docs/Chap10/10.4.md文档教程教育上一篇告别孤岛协作ChuanhuChatGPT多人编辑与冲突解决全攻略下一篇Lynx-native高级特性CSS排版引擎与原生UI组件无缝集成终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考