群论 2 - 有限群, 循环群
本文内容已完全施工完毕, 读者可放心阅读！
2.1. 有限群
定义 2.1.1 (元素阶)
对于任意群 $G$, 任意的群元 $g \in G$, 若存在最小正整数 $n$ 使得：
- 若存在最小正整数 $n$ 使得 $g^n = e$, 则 $n$ 被称为 $g$ 的 有限阶 (finite order of elements), 记为 $|g| = n$ 或 $\operatorname{ord}(g) = n$;
- 若对于任意正整数 $n$ 使得 $g^n \neq e$, 则称 $g$ 的 阶无限 (infinite order of elements), 记为 $|g| = \infin$.
注释
特别地, 假设在任意群 $G$ 中的任意元素 $g$ 有阶 $|g|$, 那么必然存在 $n \in \Z^+$, 使得 $|g| \leq n$, 那么我们便能够得出以下的小引理.
引理 2.1.2 (元素阶可整除任意群元指数)
若存在 $n \in \Z^+$ 使得 $g^n = e$, 那么 $|g|$ 能整除 $n$.
证明
利用带余除法, 即对于 $|g| \mid n$, 使得其余数项 $r = 0$ 则可证得整除性, 所以命题转化为： $$
|g| \mid n \iff \exists! q, r \in \Z, (|g|q + r = n) \and (r = 0) \quad (0 \leq r < |g|)
$$
证明 $r$ 的存在性：
透过对 $|g|q + r = n$ 移项得 $r = n - |g|q$, 并且由于需要确保 $0 \leq r < |g|$, 可考虑以群元 $g$ 的指数对 $r$ 观察, 则有： $$
g^r = g^{n-|g|q} = g^n \cdot (g^{|g|})^{-q} = e \cdot e^{-q} = e
$$ 得 $g^r = e$, 由于我们需要确保 $0 \leq r$, 同时 $g^r$ 的 $r$ 又不可能小于 $g^{|g|}$ 的 $|g|$ (因为 $|g|$ 为最小的正整数), 换句话说只要 $g^r = e$ 不为群的阶即可, 那么必定只能取 $r = 0$ (注意到 $\Z^+$ 不含 $0$) 使得 $r = 0 = n - |g|q$.证明 $q$ 的存在性：
由于上面已解得 $0 = n - |g|q$, 即当 $n = |g|q$ 时必然整除 $|g|$ 使得 $q$ 存在.
这两者的唯一性都是显然的, 因此命题成立.
推论 2.1.3 (任意群元指数必为元素阶的倍数)
对于任意群 $G$, 设 $g \in G$, 并且 $g$ 的阶有限, 以及 $N \in \Z$, 则有： $$
g^N = e \iff \text{$N$ 为 $|g|$ 的倍数}
$$
定义 2.1.4 (群阶, 有限群, 无限群)
对于任意群 $G$：
- $G$ 的基础集的势被称为群 $G$ 的 阶 (order of groups), 记为 $|G|$;
- 若 $|G| = n$, 其中 $n \in \Z^+$, 则称 $G$ 为 有限群 (finite group);
- 若 $|G| = \infin$, 则称 $G$ 为 无限群 (infinite group).
例子 2.1.5 (置换群, 二面体群, 克莱因四元群, $\Z, \Q, \R, \C$)
- $n$ 元集合 $\set{1,2, \dots, n}$ 的全体置换所构成的置换群 $S_n$ 是有限群.
- 二面体群 $D_n$ 是有限群, 因为其共有 $2n$ 个元素, 并且其同构于 $S_n$.
- 由 $4$ 个元素所组成, 并且除幺元外的元素阶均为 $2$, 则构成 克莱因四元群 (Klein four-group), 事实上它也是最小的非循环群.
- 由加法所构成的交换群 $\Z, \Q, \R, \C$ 均是无限群.
而接下来将重点讨论的整数模 $n$ 同余加法或乘法群 $\Z_n, \Z_n^\times$, 亦是极其重要的有限群具体例子.
引理 2.1.6 (有限群的任意元素均为有限阶)
对于有限群 $G$ 以及任意 $g \in G$, 则有 $|g| \leq |G|$, 换言之即当 $G$ 为有限群时任意的 $|g|$ 亦有限.
证明 1
利用鸽笼原理, 考虑群 $G = \set{ g^0 = e, g^1, g^2, \dots, g^{|G|} }$ 中有 $|G| + 1$ 个元素, 那么由于群中的元素会多出一个, 即群中元素并非两两不同, 换言之会存在一对元素是相同的, 即 $\exists i, j \in \N, g^i = g^j\quad (1 \leq j \lt i)$, 那么对该式右乘 $g^{-j}$ (即应用消除律) 可得 $g^{i-j} = e$, 使命题成立.
证明 2
利用反证法, 若 $|G| = \infin$, 所以 $G$ 中元素的阶都是无限的, 即 $G$ 中元素均两两不同, 应满足对于任意 $g^i, g^j \in G, g^i \neq g^j$, 然后再透过反证法假设 $g^i = g^j \quad (i \gt j)$, 则可挑选元素 $1 \leq j \lt i$ 使得 $g^{i-j} = e$, 则说明与 $g^i \neq g^j$ 矛盾, 因此存在元素是相同的, 换言之命题成立.
注释
这是一个非常好用的结论, 该结论实际意味着有限群中的任意元素均可透过自乘有限次回到幺元, 即所有群元均具备了周期性.
引理 2.1.7 ($|g|$ 有限蕴含 $|g^m|$ 亦有限)
对于任意群 $G$, 若 $g \in G$ 为有限阶元素, 那么对于任意 $m \geq 0$, $g^m$ 仍是有限阶的, 并且使得以下等式成立： $$
|g^m| = \frac{\text{lcm}(m, |g|)}{m} = \frac{|g|}{\gcd(m, |g|)}.
$$
证明
在数论中, 由于 $\text{lcm}(a, b) = \frac{ab}{\gcd(a, b)}$, 因此有： $$
\frac{\text{lcm}(m, |g|)}{m} = \frac{1}{m} \cdot \frac{m|g|}{\gcd(m, |g|)} = \frac{|g|}{\gcd(m, |g|)}
$$ 所以仅需证明存在最小正整数 $n = \frac{\text{lcm}(m, |g|)}{m}$ 使得 $|g^m| = n \iff (g^m)^n = e$： $$
(g^m)^n = (g^m)^{\frac{\text{lcm}(m, |g|)}{m}} = g^{\text{lcm}(m, |g|)} = g^{m|g|} = e
$$ 注意到 $g^{\text{lcm}(m, |g|)}$ 利用了 推论 2.1.3, 即 $m, n$ 与 $|g|$ 的最小公倍数那必然就是最小的 $m|g|$, 那么 $m|g|$ 为 $|g|$ 的倍数时 $g^{m|g|} = e$, 而由于 $n$ 是最小正整数因此 $m|g|$ 必定是最小的那个元素, 最终使得命题成立.
命题 2.1.8 (基本的同阶元素)
对于任意群 $G$ 以及 $a,b,c \in G$：
- 任意群元与其逆元同阶：$|a| = |a^{-1}|$;
- 任二群元的结合与交换形式同阶：$|ab| = |ba|$;
- 任意群元与其共轭形式同阶：$|a| = |cac^{-1}|$.
证明
下面均已假设 $n \in \Z^+$ 为最小正整数：
- 假设 $|a| = n$, 则 $a^n = e$, 两侧同时乘以 $a^{-n}$ 得 $e = a^{-n}$, 则有 $(a^{-1})^n = e$, 因此 $|a| = |a^{-1}| = n$ 成立.
- 假设 $|ab| = n$, 则 $(ab)^n = e$, 显然根据轮换性有 $\overbrace{ab \cdot ab \cdot \ldots \cdot ab}^{\text{$n$ 次}} = \overbrace{ba \cdot ba \cdot \ldots \cdot ba}^{\text{$n$ 次}} = e$, 因此 $|ab| = |ba| = n$ 显然成立.
- 假设 $|cac^{-1}| = n$, 则 $(cac^{-1})^n = ca^nc^{-1} = e$, 显然就能推出 $a^n = e$, 因此 $|a| = |cac^{-1}|$ 成立.
引理 2.1.9 (阶大于 $2$ 的元素必成对出现)
对于任意群 $G$ 以及 $g \in G$, 若 $|g| > 2$, 则有 $g \neq g^{-1}$ (意味着这一对元素就是 $g$ 与 $g^{-1}$).
证明
利用反证法, 假设 $|g| > 2$ 时 $g = g^{-1}$, 则 $g^2 = e$, 显然有 $|g| = 2$, 那么这与条件 $|g| > 2$ 矛盾, 因此命题成立.
定理 2.1.10 (偶数阶群有奇数个 $2$ 阶元素)
设有偶数阶群 $G$, 则存在一些元素 $g \in G$, 使得 $|g| = 2$ 的元素个数为奇数个 (换句话说, 即共有奇数个群元满足 $\exists g \in G, g^2 = e$).
证明 1
我们假设有集合 $S$, 而 $S$ 是由 $G$ 中所有的阶大于 $2$ 的元素所组成的, 即 $S = \set{ g \in G : |g| > 2 }$, 那么由 引理 2.1.9 得知 $S$ 中的元素肯定是成对出现的, 则 $|S|$ 为偶数, 而由于 $|G|$ 是偶数, 则 $|G \backslash S|$ 也是偶数个, 然后减掉阶为 $1$ 的幺元 $e$ 后则剩下的都是二阶元, 所以 $2$ 阶元是奇数个 (利用整数的奇偶性：$偶数-奇数=奇数$).
证明 2
利用等价类证明, 由于 $g^2 = e \iff g = g^{-1}$, 则按照该等式分别划分为等价类 $P, P'$： $$
P \coloneqq \set{ g \in G : g = g^{-1} } \\
P' \coloneqq \set{ g \in G : g \neq g^{-1} }
$$ 那么按照这种划分方式, 它们之间的不交并必定等价于 $G$, 即 $G = P \sqcup P'$, 那么由于 $|G|$ 是偶数, 而由 引理 2.1.9 得 $|g| > 2$ 的偶数个元素都落入 $P'$ 中, 且再加上幺元 $e$ 则 $|P'|$ 有奇数个元素, 使得 $|G| - |P'| = |P|$ 时, $|P|$ 为奇数个元素 (该处极其类似 证明 1 的思路, 只不过使用等价类划分而为补集).
证明 3
利用反证法, 我们假设 $2$ 阶元素有偶数个, 并把它们归类到集合中, 即 $S = \set{ g \in G : |g| = 2}$, 并且 $|S| = 2m$, 那么由于 $G$ 为偶数阶群, 所以有 $|G| = 2k$ 个元素, 则 $|G| - |S| = 2k - 2m = 2(k - m)$ , 即偶数个元素的阶不等于 $2$, 那么由 引理 2.1.9 得阶大于 $2$ 的元素成对出现, 设该部分元素为 $2n$ 个, 则有 $2(k-m) - 2n = 2(k-m-n)$, 即仍为偶数个元素, 但群中包含了幺元 $e$, 将其剔除后应有奇数个二阶元, 则与 $2(k-m-n)$ 产生矛盾, 使得命题成立.
推论 2.1.11 (偶数阶群存在 $2$ 阶元素)
设有偶数阶群 $G$, 那么存在一些元素 $g \in G$, 使得 $|g| = 2$ (换句话说, 即 $\exists g \in G, g^2 = e$ 有偶数个解).
证明
这显然是 定理 2.1.10 的直接推论.
定理 2.1.12 (任意群仅包含有限个子群则其自身有限)
设有群 $G$, 若 $G$ 有限 $\iff$ $G$ 仅包含有限个子群.
证明
$(\Rightarrow)$ 由逆否命题证明, 假设 $G$ 包含了无穷个子群, 显然由这些子群会组成无穷个子集的幂集 $\mathcal{P}(G)$, 显然 $|\mathcal{P}(G)| = \infin$, 那么 $G$ 也是无限的.
$(\Leftarrow)$ 若 $G$ 仅包含有限个子群 $H_1, H_2, \dots, H_k$, 假设这些子群的构成了幂集 $\mathcal{P}(G)$, 则对于任意的 $H_i \in \mathcal{P}(G)$ 其中 $1 \leq i \leq k $, 那么由于 $\mathcal{P}(G)$ 是有限集, 则 $|\mathcal{P}(G)| = 2^n$, 其中有 $n \in \N$ 为有限数, 那么显然 $|G| = n$, 则 $G$ 是有限的.
2.2. 有限交换群
命题 2.2.1 (有限交换群蕴含 $|gh| \big| \text{lcm}(|g|, |h|)$)
若 $G$ 为有限交换群, 对于任意 $g, h \in G$, 则 $|gh| \big| \text{lcm}(|g|, |h|)$.
证明
设 $|g|, |h|$ 的最小公倍数为 $N = \text{lcm}(|g|, |h|)$, 那么利用 推论 2.1.3, 由于 $N$ 是 $|g|$ 或 $|h|$ 的倍数, 因此有 $g^N = e = h^N$, 换句话说 $g^N \cdot h^N = e$, 那么则可推出： $$
e = g^N \cdot h^N = \underbrace{g \ldots g}_{N\ 次} \cdot \underbrace{h \ldots h}_{N\ 次} \overset{交换律}{=} \underbrace{gh \cdot gh \cdot \ldots \cdot gh}_{N\ 次} = (gh)^N
$$ 则得知 $g^N = g^{\text{lcm}(|g|, |h|)}$, 而根据 引理 2.1.2, 因存在 $\text{lcm}(|g|,|h|)$, 那么 $|gh|$ 必然整除 $\text{lcm}(|g|, |h|)$, 使得命题成立.
命题 2.2.2 ($g^2 = e$ 蕴含交换群)
对于任意群 $G$, 以及 $\forall g \in G$, 若 $g^2 = e$, 则 $G$ 是交换群.
证明
由于 $g^2 = e \iff g = g^{-1}$, 那么对于 $\forall x, y \in G$, 则 $xy = x^{-1}y^{-1} = x^{-1}y^{-1}(yx) = yx$ 使得命题成立.
命题 2.2.3 ($|G| \leq 4$ 蕴含交换群)
对于任意群 $G$, 若 $|G| \leq 4$, 则 $G$ 是交换群.
证明
$|G| = 1$ 或 $2$ 时结论是显然的, 因此以下只证明 $3, 4$ 的情况：
若设 $G = \set{e, f, g}$, 根据群的封闭性 $fg \in G$, 那么：
- 当 $fg = e$ 时, 得 $g = f^{-1}$, 使得 $f^{-1}f = gf = e$, 因此 $fg = gf$.
- 当 $fg = f$ 时, 得 $g = e$, 使得 $fg = ef = gf$.
- 当 $fg = g$ 时, 与上述同理.
使得群元素均可交换, 对于 $4$ 个元素亦是如此, 因此命题成立.
命题 2.2.4 (有限交换群)
对于任意有限交换群 $G$, 若仅有元素 $f \in G$ 的阶为 $2$, 则 $\prod_{g \in G} g = f$.
证明
设 $G = \set{g_1, g_2, \dots, f = f^{-1}, \dots, g_n}$, 即 $|G| = n$, 而由于 $G$ 是有限群, 因此必有 $g_k^i = e\quad (0 \lt i \leq |G|)$, 那么则有： $$
\begin{align}
g_1 g_2 \ldots f \ldots g_n & = f \\
g_1 g_2 \ldots g_n f & = f \\
g_1 g_2 \ldots g_{n-1} & = e \\
\end{align}
$$ 使得对于其中任意的 $g_j$ 都等同于 $g^i_k = e$, 因此命题成立.
2.3. 同余群
定义 2.3.1 (同余关系, 同余类, $\Z_n$)
设有 $n \in \Z^+$, 则：
- 对于任意 $a, b \in \Z$, 称定义在 $\Z$ 上的等价关系 $a \equiv b \pmod{n} \iff n \mid (b-a)$ 为 整数 $a$ 模 $n$ 的同余关系 (congruence modulo $n$);
- 若给定 $a \in \Z$, 则称 $[a]_n \coloneqq \set{ b \in \Z : a \equiv b \pmod{n} } = \set{ b \in \Z : \exists k \in \Z, b-a = kn }$ 为由 $\Z$ 中元素 $a$ 模 $n$ 的同余关系所构成的 同余类 (congruence class), 并且为等价类的一种;
- 同余类的全体所构成的集合为 $\Z_n$ 或 $\Z/n\Z$, 即有 $\Z_n \coloneqq \set{[0]_n, [1]_n, \dots, [n-1]_n}$, 其中 $|\Z_n| = n$.
定理 2.3.2 ($\Z_n$ 构成整数模 $n$ 加法群)
设 $n \in \Z^+$, 定义二元运算 $\begin{align} \Z_n \times \Z_n & \overset{+}{\to} \Z_n \\ [a] + [b] & \mapsto [a + b] \end{align}$, 则 $(\Z_n, +)$ 构成交换群, 称为 整数模 $n$ 加法群 (additive group of integer modulo $n$).
证明
设任意 $[a], [b], [c] \in \Z_n$：
首先证明所定义的二元运算是良定义的, 即对于任意其他的 $[a]', [b]' \in \Z_n$, 若 $[a] = [a]'$, $[b] = [b]'$, 则 $[a] + [b] = [a]' + [b]'$：
由同余关系的定义有 $[a] + [b] = [a]' + [b]' \iff a + b = a' + b' \pmod{n}$, 按其定义展开即证 $n \mid [(a' + b') - (a+b)]$, 显然根据 $a = a' \pmod{n} \iff n \mid (a' - a)$ 以及 $b = b' \pmod{n} \iff n \mid (b' - b)$, 那么就有 $n \mid (a'-a)+(b'-b)$, 使得命题成立.
其次证明满足了交换群公理, 其中幺元为 $[0]$ 而逆元为 $[-a] \coloneqq [-a]$：
封闭性：$[a] + [b] = [a + b] \in \Z_n$.
结合律：$([a] + [b]) + [c] = [a + b] + [c] = [(a+b) + c] = [a + (b + c)] = [a] + [b + c] = [a] + ([b] + [c])$.
幺元律：$[0] + [a] = [0 + a] = [a] = [a + 0] = [a] + [0]$.
逆元律：$-[a] + [a] = [-a] + [a] = [-a + a] = [0] = [a + (-a)] = [a] + [-a] = [a] - [a]$.
交换律：$[a] + [b] = [a + b] = [b + a] = [b] + [a]$.
注释 ($\Z_n$ 的生成方式)
$\Z_n$ 既是有限交换群, 亦是循环群的一个重要例子, 因为对于 $\Z_n$ 中的任意元素总能被 $[1]$ 不断累加自身 $m, n$ 次生成 (其中 $m \in \Z, m \geq 0$), 即： $$
[m] = [\underbrace{1 + 1 + \dots + 1}_{\text{$m$ 次}}] = \underbrace{[1] + [1] + \dots + [1]}_{\text{$m$ 次}} = m \cdot [1]
$$
而循环群的具体性质与定义将于后续 2.4 节 中提及. 而当讨论群 $\Z_n$ 时, 我们当然希望研究它的元素阶数如何, 便有了以下命题.
定理 2.3.3 ($\Z_n$ 中元素的阶)
对于任意 $[m]_n \in \Z_n$, 若 $n \mid m$, 则 $|[m]_n| = 1$, 更一般地定义为： $$
|[m]_n| \coloneqq \frac{n}{\gcd(m, n)}.
$$
证明
分类讨论：
若 $n \mid m$, 那么便没有 $m, n$ 除以 $n$ 的余数 $r$, 换言之 $[m]_n = [0]_n$, 所以 $1\cdot [m]_n = [0]_n$.
若 $n \nmid m$, 那么由于 $[m]_n = m \cdot [1]_n \quad (m \in \Z, m \geq 0)$, 则可利用 引理 2.1.7, 使得有： $$
|[m]_n| = | m \cdot [1]_n | = \frac{|[1]_n|}{\gcd(m, |[1]_n|)} = \frac{n}{\gcd(m, n)}
$$ 其中由于 $n \cdot [1]_n = [0]_n$ 而 $n$ 是最小正整数, 因此 $|[1]_n| = n$.
注释 1
由上述命题观察到, 当 $m, n$ 互素时, 那么 $|[m]_n| = n$, 藉由此 $[m]_n$ 则可生成出 $\Z_n$, 所以 $\Z_n$ 亦被称为 $n$ 阶同余加法群 (additive modulo group of order $n$). 此外, $\Z_n$ 中任意群元的阶实际上均可整除群的阶数 $|\Z_n| = n$, 该处与拉格朗日定理密切相关, 将于后续章节中提到.
注释 2
对于任意 $n \in \Z^+$, $n$ 阶有限整数加群 $\Z_{n} = \lang 1 \rang = \set{0, 1, 2, \dots, n-1}$ 构成 $\Z$ 的循环子群, 例如 $\Z_7$ 中的元素便是由 $1$ 生成的, 为了方便叙述而将任意的 $[a] \in \Z_n$ 直接简记为 $a$, 即有： $$
\begin{align}
1 & = 1 \\
1 + 1 & = 2 \\
1 + 1 + 1 & = 3 \\
1 + 1 + 1 + 1 & = 4 \\
1 + 1 + 1 + 1 + 1 & = 5 \\
1 + 1 + 1 + 1 + 1 + 1 & = 6 \\
1 + 1 + 1 + 1 + 1 + 1 + 1 & = 0 \\
\end{align}
$$ 事实上生成元并不是唯一的, 例如 $3$ 亦可生成 $\Z_7$： $$
\begin{align}
3 & = 3 \\
3 + 3 & = 6 \\
3 + 3 + 3 & = 2 \\
3 + 3 + 3 + 3 & = 5 \\
3 + 3 + 3 + 3 + 3 & = 1 \\
3 + 3 + 3 + 3 + 3 + 3 & = 4 \\
3 + 3 + 3 + 3 + 3 + 3 + 3 & = 0 \\
\end{align}
$$
所以 $\Z_7 = \lang a \rang = \set{ 0, a, 2a, 3a, 4a, 5a, 6a }$, 使得 $a$ 取值为除 $0$ 以外的 $1$ 至 $6$ 时亦可生成 $\Z_7$.
那么或许会有个疑问, 即 $\Z_n$ 中的每个元素是否都能被作为生成元呢？答案是否定的, 例如考虑 $\Z_6$ 的情形, 则仅有 $1$ 与 $5$ 能够作为生成元, 因为它们均与 $7$ 互素, 便引出了以下推论.
推论 2.3.4 ($[m]_n$ 生成了 $\Z_n$ 当且仅当 $m, n$ 互素)
若设有 $m, n \in \Z^+$ 且 $1 \leq m \lt n$, 则 $\Z_n = \lang [m]_n \rang \iff \gcd(m, n) = 1$.
证明
只证充分条件, 由于 $\gcd(m, n) = 1$, 根据 定理 2.3.3, 就有 $|[m]_n| = n$, 因此所生成的群便是： $$
\Z_n = \lang [m]_n \rang = \set{ [0] = n[m], [m], 2[m], \dots, (n-1)[m] }
$$ 反之必要条件亦然, 因此 $[m]_n$ 生成了 $\Z_n$.
注释 (素数阶同余群 $\Z_p$)
上述推论虽然很简单, 但亦是非常重要的, 例如若考虑由素数 $p$ 构成的素数阶同余群 $\Z_p$ (或记为 $\Z/p\Z$), 则意味着 $\gcd(m, p) = 1$, 显然其中任意一个小于 $p$ 的非零整数 $m$ 均与 $p$ 互素, 即 $\gcd(m, p) = 1$, 也就意味着任意非零的同余类 $[m]$ 生成了 $\Z_p$.
注释 ($\Z_n^\times$ 的构造方式)
既然我们已经提及到同余类可于加法意义下构成群, 那么很自然的一个推广就是思考若二元运算为同余类的乘法时, $\Z_n$ 是否亦构成群呢？考虑到乘法单位元很自然地可以取为 $[1]_n$, 而对于群元 $[0]_n \in \Z_n$, 由于其是不存在乘法逆元的, 所以我们必须将等于 $[0]$ 的所有同余类给排除掉, 那么就得到以下这个集合： $$
\Z_n^\times \coloneqq \set{ \underbrace{ [1], [2], \dots, [n-1] }_{\text{$n-1$ 个元素}} }
$$ 并且由 推论 2.3.4 可得 $n$ 阶同余加法群可由 $[m]_n$ 所生成当且仅当 $m, n$ 互素, 我们现在将该条件再引入到集合 $\Z_n^\times$ 使得其构成了 $n$ 阶乘法同余群, 最终就引出了以下命题.
定理 2.3.5 ($\Z_n^\times$ 构成整数模 $n$ 乘法群)
对于任意 $m, n \in \Z^+$, 定义同余类的乘法运算 $\begin{align} \Z_n^\times \times \Z_n^\times & \overset{\cdot}{\to} \Z_n^\times \\ [a] \cdot [b] & \mapsto [a \cdot b] \end{align}$, 以及集合： $$
\Z_n^\times \coloneqq \set{ [m] : 1 \leq m < n, \gcd(m, n) = 1 }
$$ 则 $(\Z_n^\times, \cdot)$ 构成了交换群, 被称为 整数模 $n$ 乘法群 (additive group of integer modulo $n$) 或 $n$ 阶同余乘法群 (multiplicative modulo group of order $n$), 一般可简记为 $\Z_n^\times$ 或 $(\Z/n\Z)^\times$.
证明
首先运算符 $\cdot$ 是良定义的, 证明类似于 $\Z_n$ 所以就此略过. 那么设任意 $[a], [b], [c] \in \Z_n^\times$, 现在证明 $\Z_n^\times$ 的群公理, 其中幺元为 $[1]$ 而逆元为 $[a]^{-1} \coloneqq [a^{-1}]$, 而该逆元同余类亦被称为 模逆元 / 模倒数 / 数论倒数 (modular multiplicative inverse)：
封闭性：由于有 $\gcd(a, n) = 1$ 以及 $\gcd(b, n) = 1$, 显然 $[a] \cdot [b] = [ab]$ 就有 $\gcd(ab, n) = 1$ 使得封闭性得证.
结合律：$([a] \cdot [b]) \cdot [c] = [ab] \cdot [c] = [abc] = [a] \cdot [bc] = [a] \cdot ([b] \cdot [c])$, 并且由于有 $\gcd(ab, n) = 1$ 以及 $\gcd(c, n) = 1$, 类似于上述的封闭性显然 $\gcd(abc, n) = 1$ 可拆分为 $\gcd(a, n) = 1$ 以及 $\gcd(bc, n) = 1$, 保证了封闭性.
么元律：$[1] \cdot [a] = [1 \cdot a] = [a] = [a \cdot 1] = [a] \cdot [1]$, 且封闭性是显然的, 因为 $[1], [a]$ 都是取自 $\Z_n^\times$ 中.
逆元律：$[a]^{-1} \cdot [a] = [a^{-1}] \cdot [a] = [a^{-1}a] = [1] = [aa^{-1}] = [a] \cdot [a^{-1}] = [a] \cdot [a]^{-1}$, 且由于其中 $[a^{-1}]$ 知 $\gcd(a^{-1}, n) = 1$ 以及 $\gcd(a, n) = 1$, 显然 $\gcd(a^{-1}a, n) = \gcd(aa^{-1}, n) = 1$ 保证了封闭性.
交换律：$[a] \cdot [b] = [ab] = [ba] = [b] \cdot [a]$, 其封闭性亦是显然的, 因为 $\gcd(ab, n) = \gcd(ba, n)$.
注释
那我们为什么需要推广为 $n$ 阶同余乘法群？事实上该群于数论里是非常重要的一个基石, 许多著名的定理在该群下就可以给出十分简洁的证明, 以下便是一些例子.
例子 2.3.6 (欧拉定理, 费马小定理)
欧拉定理与费马小定理分别作为群 $\Z_n^\times$ 的具体实例, 它们被阐述为：
- 欧拉定理 (Euler's theorem)：对于任意 $a \in \Z$, 若 $\gcd(a, n) = 1$, 则 $a^{\varphi(n)} \equiv 1 \pmod{n}$, 其中 $\varphi(n)$ 为欧拉函数.
- 费马小定理 (Fermat's little theorem)：对于任意 $a \in \Z$, 以及素数 $p$, 若 $1 \leq a \leq p - 1$, 则 $a^{p-1} \equiv 1 \pmod{p}$ 成立.
由于需要使用到拉格朗日定理, 所以具体的证明部分会留到后续第三章节提及.
2.4. 循环群
注释
回顾第一章在生成部分关于循环子群的定义, 由于对任意子群 $H < G$, 只要我们任给一个生成元 $a \in H$ 透过生成的等价定义就有 $H = \lang a \rang = \set{ a^n : n \in \Z }$, 那么该群则被称为由 $a$ 生成的循环子群, 那么现在我们进一步推广并定义出关于循环群的概念.
定义 2.4.1 (循环群)
对于任意群 $G$, 若存在 $a \in G$, 使得 $G = \lang a \rang$, 则称 $G$ 是由 $a$ 所生成的 循环群 (cyclic group), 并且：
- 若 $|a| = n$, 即生成元的阶有限时称 $G$ 为 $n$ 阶有限循环群 (finite cyclic group of order $n$)
- 若 $|a| = \infin$, 则称为 无限循环群 (infinite cyclic group).
注释
注意该处关于 $n$ 阶有限循环群及无限循环群的定义, 其与 [定义 2.1.4](定义 2.1.4 (群阶, 有限群, 无限群)) 关于有限群的定义等价的, 但这里使用了生成元的阶 $|a|$ 刻画有限性, 而非使用群的阶 $|G|$.
例子 2.4.2 (二面体群, 单位根群, 整数加群)
二面体群 (dihedral group) $D_{2n}$ 是正 $n$ 边形置换群, 共有 $2n$ 个元素, 那么若我们考虑 $n$ 阶循环群 $C_n$ 时, 其中的两种操作, 即旋转对称 $\sigma$ (将正 $n$ 边形旋转 $2\pi/n$ 度) 以及镜像对称 $\begin{align} C_n & \overset{\tau}{\to} C_n \\ x & \mapsto x^{-1} \end{align}$ (实际是 $C_n$ 上的自同构) 且有 $\tau^2 = e$, 则 $D_{2n}$ 可由 $\sigma, \tau$ 所生成.
$n$ 次单位根以乘法构成 单位根群 (group of $n$ roots of unity), 并且由单位的 $n$ 次本原根 $e^{\frac{2 \pi ki}{n}}$ 所生成 (其中 $k, n$ 互素), 使得其构成 $n$ 阶循环群, 例如有： $$
\begin{align}
\text{单位的 $1$ 次根} & = \set{1} \\
\text{单位的 $2$ 次根} & = \set{1, -1} \\
\text{单位的 $3$ 次根} & = \Set{1, \frac{-1+\sqrt3i}{2}, \frac{-1-\sqrt3i}{2}} \\
\text{单位的 $4$ 次根} & = \set{1, i, -1, -i} \\
\end{align}
$$ 其中 $4$ 次单位根群就是构成了我们所熟知的 $\C$ 中关于虚数单位的运算规律.整数加群 $\Z$ 同构于任意无限循环群, 因为群内的元素均可透过不断 $+1$ 与 $-1$ 所生成, 后续将具体证明.
引理 2.4.3 (有限循环群蕴含群元互不相同)
设 $G = \lang g \rang = \set{e, g, \dots, g^{n-1}}$ 为 $n$ 阶有限循环群, 则群元互不相同.
证明
透过反证法, 我们假设群元任意群元是相同的, 即 $g^i = g^j \quad (0 \leq j < i < n)$, 而透过等式两侧右乘 $g^{-j}$ 则有 $g^{i-j} = e \quad (0 \leq i-j < n)$, 由于任意群元的指数 $i-j$ 小于 $n$, 而 $n$ 为群的阶, 所以必定是最小正整数, 这显然与假设矛盾, 即得证命题成立 (该证明类似于 引理 2.1.6 中的证明思路).
引理 2.4.4 (无限循环群中元素互不相同)
设 $G = \lang g \rang$ 为无限循环群, 对于任意 $m, n \in \Z$, 若 $m \neq n$, 则 $g^m \neq g^n$.
证明
透过反证法, 假设 $g^m = g^n \quad (n < m)$, 则有 $g^{m-n} = e$ 使得生成元 $|g| = m-n$ 为有限阶, 这显然与无限循环群的定义矛盾, 因此命题成立.
注释
该引理刻画了关于函数单射性的逆否命题, 于证明有关于循环群的单同态时十分有用.
定理 2.4.5 ($\Z$ 的子群构成循环群)
设有任意子群 $H < \Z$：
- $H = \lang 0 \rang$ 是 $\Z$ 的有限循环子群.
- $H = \lang m \rang$ 是 $\Z$ 的无限循环子群, 其中 $m$ 为任意最小正整数.
证明
该处只证明 $(2)$, 因为 $(1)$ 是类似的：
$(\Rightarrow)$ 假设有任意 $h \in H$, 那么由带余除法有 $h = qm + r \quad (0 \leq r < m)$, 其中 $q, r \in \Z$, 且由于 $m$ 为最小正整数, 若 $r$ 为正整数时不可能小于 $m$, 因此 $r$ 只能取为 $0$ 使得 $h = qm \in \Z$, 因此就有 $H \sub \lang m \rang$.
$(\Leftarrow)$ 显然有 $\lang m \rang = \set{ km : k \in \Z } \sub H$.
定理 2.4.6 (任意循环群同构于 $\Z$ 或 $\Z_n$)
- 任意的无限循环群 $G$ 都同构于整数加群 $\Z$;
- 任意的 $n$ 阶有限循环群 $G$ 都同构于 $\Z_n$.
证明
由于 $G = \lang a \rang$ 是无限循环群, 设有映射 $\begin{align} \Z & \overset{\varphi}{\to} G \\ k & \mapsto a^k \end{align}$, 现在证明：
- $\varphi$ 为单射：利用 引理 2.4.4 即可直接证明.
- $\varphi$ 为满射：因为 $\forall x \in G, \exists k \in \Z, x = \varphi(k) = a^k$, 所以其为满同态.
- $\varphi$ 为群同态：对于任意 $r, s \in \Z$ 有 $\varphi(r + s) = a^{r+s} = a^r \cdot a^s = \varphi(r) \cdot \varphi(s)$.
因此就使得 $G \cong \Z$.
由于 $G = \lang a \rang$ 是 $n$ 阶有限循环群, 那么 $|a| = n$, 其中 $n$ 为最小正整数, 现在设有映射 $\begin{align} \Z_n & \overset{\varphi}{\to} G \\ [k] & \mapsto a^k \end{align}$, 显然是一一对应的, 并且保持了群同态： $$
\varphi([r] + [s]) = \varphi([r + s]) = a^{r+s} = a^r \cdot a^s = \varphi([r]) \cdot \varphi([s]) \qquad \forall [r], [s] \in \Z_n
$$ 因此就使得 $G \cong \Z_n$.
定理 2.4.7 (循环群的同态像构成循环群)
设有任意循环群 $G$, 任意群 $H$ 以及群同态 $f : G \to H$, 则 $\operatorname{Im} f$ 构成循环群.
证明
假设 $G = \lang a \rang$, 显然对于任意 $k \in \Z$ 有 $f(a^k) = f(\overbrace{a \dots a}^{\text{$k$ 次}}) = \overbrace{f(a) \dots f(a)}^{\text{$k$ 次}} = f(a)^k$, 显然 $\operatorname{Im} f$ 中任意元素都能被表示为 $f(a)^k$ 的形式, 因此 $\operatorname{Im} f = \lang f(a) \rang$.
定理 2.4.8 (循环群的子群构成循环群)
设有元素 $g \in G$ 以及任意循环群 $G = \lang g \rang$, 且 $H < G$, 则 $H$ 为 $G$ 的循环子群.
特别地, 若 $H$ 为非平凡子群, 则存在最小的 $n \in \Z^+$ 使得 $g^n \in H$, 那么有 $H = \lang g^n \rang$.
证明
首先对 $H$ 中的元素进行分类讨论：
若 $H$ 为平凡子群, 即 $H = \lang e \rang = \set{e = e^2 = e^3 = \dots} = \set{e}$, 显然这是一个平凡的循环子群.
若 $H \neq \set{e}$, 设 $H = \set{e, h_1, h_2, \dots}$, 并且对于任意的 $h_i \in H$ 均可表示为 $(h_i)^j$ 或 $(h_i)^{-j}$ 的形式, 且 $G$ 中亦类似, 即 $G = \set{e, g, g^2, \dots}$, 那么由于 $G < H$, 则对于所有 $H$ 中的任意元素 $h$, 都存在任意的正整数 $k$ 使得 $g^k$ 等于 $h$, 使得 $g^k \in H$, 即有： $$
\forall h \in H, \exists k \in \Z^+, h = g^k \in H
$$ 那么除此之外, 根据良序公理, 则存在最小正整数 $n$ 使得 $g^n \in H$. 现在透过带余除法, 我们可以将 $k$ 分解为以下公式： $$
\exists! q,r \in \Z, \quad k = qn + r \quad (0 \leq r \lt n)
$$ 则可对 $g^k$ 分解为： $$
\left( h = g^k = g^{qn} \cdot g^r \overset{群的封闭性}{\implies} g^{qn} = (g^n)^q \in H \right) \quad 或 \quad \left( g^r = g^{-qn} \cdot g^k \overset{群的封闭性}{\implies} (g^n)^{-q} \in H \right)
$$ 并且需满足 $0 \leq r < n$, 从上述假设我们知道 $n$ 是最小正整数, 那么 $r$ 作为正整数时不可能小于 $n$, 所以只有 $r = 0$ 满足条件, 则我们有： $$
h = g^k = (g^n)^q \in H
$$ 那么即是说, 此时取 $g^n$ 作为 $H$ 的生成元时则有： $$
H = \lang g^n \rang = \set{ e, g^n, (g^n)^2, (g^n)^3, \dots (g^n)^j, \dots }
$$
使得最终命题成立.
定理 2.4.9 (循环群的生成元)
设 $G = \lang a \rang$ 为循环群：
- 若 $G$ 是无限群, 则 $a$ 与其逆元 $a^{-1}$ 为 $G$ 唯一的生成元;
- 若 $G$ 是 $n$ 阶有限群, 则 $a^k$ 是 $G$ 的生成元 $\iff$ $\gcd(k, n) = 1$.
证明
- 假设另外的生成元 $b \in G$, 由于 $G = \lang a \rang$ 或 $G = \lang b \rang$, 而从 定理 2.4.6 得 $G \cong \Z$, 显然 $\Z = \lang 1 \rang$, 即其生成元均为 $1$, 因此 $a = b$, 逆元同理.
- 由于 $G = \lang a^k \rang$, 而从 定理 2.4.6 得 $G \cong \Z_n$, 那么有 $\Z_n = \lang [k]_n \rang$, 那么利用 推论 2.3.4 即可直接证明 $\gcd(k, n) = 1$, 反之亦然.
命题 2.4.10 (无限群是循环的当且仅当其同构于它的每一个真子群)
设有无限群 $G$, 则 $G$ 是循环群 $\iff$ 对于任意真子群 $H < G$, 有 $G \cong H$.
证明
$(\Rightarrow)$ 若 $G$ 是无限循环群, 根据 定理 2.4.6, 则有 $G \cong \Z$, 那么现在对于任意真子群 $H < \Z$, 其中 $H \neq \Z$ 且 $H \neq \lang 0 \rang$, 而根据 定理 2.4.5 易见 $H$ 必然也是循环群, 并且对于任意最小正整数 $m$, 有 $H = \lang m \rang = \set{ km : k \in \Z }$, 显然我们便能建立双射 $\begin{align} \Z & \overset{\varphi}{\to} H \\ k & \mapsto km \end{align}$, 并且保持了群同态： $$
\varphi(x + y) = (x+y)m = xm + ym = \varphi(x) + \varphi(y) \qquad \forall x,y \in H
$$ 因此 $\varphi$ 是个群同构, 因此 $G \cong \Z \cong H$.
$(\Leftarrow)$ 若要证 $G$ 是无限循环群, 根据定义需证存在 $a \in G$ 使得 $G = \lang a \rang$, 而由于有群同构 $\varphi : H \to G$, 那么每一个 $H$ 必定无限, 意味着 $H$ 中每一个元素的阶都是无限的, 即对于任意 $h \in H$, 有 $|h| = \infin$, 那么则可设 $H = \lang h \rang$ 使得 $H$ 为由任意其的群元所生成的无限循环子群, 而根据 定理 2.4.7 则得知 $\operatorname{Im} \varphi = \lang \varphi(h) \rang$ 并且群同构蕴含满同态, 因此 $\operatorname{Im} \varphi = G$ 就使得 $G$ 构成循环群.
定理 2.4.11 (任意同阶循环群是同构的)
设有任二 $n$ 阶循环群 $G = \lang a \rang$ 以及 $H = \lang b \rang$, 则 $G \cong H$.
证明
根据 定义 2.4.1 (循环群) 有阶 $|a| = |b| = n$, 那么现在 $G, H$ 的集合则可表示为： $$
\begin{align}
G & = \lang a \rang = \set{ a^0 = e, a^1, a^2, \dots, a^{n-1} } \\
H & = \lang b \rang = \set{ b^0 = e, b^1, b^2, \dots, b^{n-1} }
\end{align}
$$ 因此就可以建立双射 $\begin{align} G & \overset{\varphi}{\to} H \\ a^k & \mapsto b^k \end{align}$, 其中 $k \in \Z$, 并且其能够保持群同态性： $$
\varphi(a^i a^j) = \varphi(a^{i+j}) = b^{i+j} = b^i b^j = \varphi(a^i) \varphi(a^j) \qquad \forall i,j \in \Z
$$ 因此 $\varphi$ 是个群同构, 所以 $G \cong H$ 成立.