一、回顾：幂运算
1.1 元素幂次的定义
设 $(G, \cdot)$ 是一个群，$a \in G$，则 $a$ 的幂运算如下定义：
- 正整数幂（递归定义）：$a^1 = a$，$a^{k+1} = a^k \cdot a$
- 零次幂：$a^0 = e$（幺元）
- 负整数幂：$a^{-k} = (a^k)^{-1}$（即 $a^k$ 的逆）
由此，群中任意元素的整数次幂都已定义完毕。
1.2 幂运算的基本性质
对任意整数 $m, n$：
- $a^m \cdot a^n = a^{m+n}$
- $(a^m)^n = a^{mn}$
这些性质对于数的乘法（指数运算）是大家熟悉的，在一般群中同样成立。
二、由一个元素生成的子群
2.1 命题
设 $(G, \cdot)$ 是群，$a \in G$，则由 $a$ 生成的子群为：
\[\langle a \rangle = \{a^i \mid i \in \mathbb{Z}\}\]2.2 证明思路
需要说明两点：
(1) ${a^i \mid i \in \mathbb{Z}}$ 是 $G$ 的子群。
利用幂运算的基本性质：
- 对运算封闭：$a^i \cdot a^j = a^{i+j}$，仍在集合中。
- 对求逆封闭：$(a^i)^{-1} = a^{-i}$，仍在集合中。
因此它是 $G$ 的子群。
(2) 对任意子群 $H$，若 $a \in H$，则 $\langle a \rangle \subseteq H$。
因为 $H$ 是子群，$a \in H$，所以：
- $a^2 = a \cdot a \in H$，$a^3 = a^2 \cdot a \in H$，…，由归纳法知所有正整数次幂 $a^k \in H$；
- $a^0 = e \in H$（子群包含大群的幺元）；
- 对负整数次幂，因 $a^k \in H$ 且 $H$ 对求逆封闭，故 $a^{-k} = (a^k)^{-1} \in H$。
因此 ${a^i \mid i \in \mathbb{Z}} \subseteq H$，即 $\langle a \rangle$ 是包含 $a$ 的最小子群。$\blacksquare$
三、群元素的阶
3.1 定义
设 $(G, \cdot)$ 是群，$a \in G$。
-
有限阶元：若存在正整数 $n$ 使得 $a^n = e$，则称 $a$ 是有限阶元。使得 $a^n = e$ 的最小正整数 $n$ 称为 $a$ 的阶，记为 $o(a) = n$（或 $ a = n$）。 - 无限阶元：若对任意正整数 $n$，$a^n \ne e$，则称 $a$ 是无限阶元，记 $o(a) = \infty$。
注意：$a^0 = e$ 对任何元素都成立，这是平凡的。阶的定义要求是正整数。
3.2 例子
考虑非零复数乘法群 $(\mathbb{C}^*, \cdot)$：
(1) $-1$ 生成的子群：
\[\langle -1 \rangle = \{1, -1\}\]因为 $(-1)^0 = 1$，$(-1)^1 = -1$，$(-1)^2 = 1$，$(-1)^3 = -1$，…，不断循环。所以 $-1$ 是二阶元，$o(-1) = 2$。
(2) $i = \sqrt{-1}$ 生成的子群：
\[\langle i \rangle = \{1, i, -1, -i\}\]因为 $i^0 = 1$，$i^1 = i$，$i^2 = -1$，$i^3 = -i$，$i^4 = 1$，之后开始循环。所以 $i$ 是四阶元，$o(i) = 4$。
(3) $2$ 生成的子群：
\[\langle 2 \rangle = \{\ldots, 2^{-2}, 2^{-1}, 1, 2, 4, 8, \ldots\}\]对任意非零整数 $k$，$2^k \ne 1$，所以 $2$ 是无限阶元，$o(2) = \infty$。
四、无限阶元的基本性质
命题：设 $a$ 是群 $G$ 中的无限阶元，则：
- 对任意非零整数 $n$，$a^n \ne e$ 且 $a^{-n} \ne e$。
- 对任意整数 $i \ne j$，$a^i \ne a^j$（不同幂次对应不同元素）。
- $\langle a \rangle = {a^i \mid i \in \mathbb{Z}}$ 是一个无限集合。
证明：
(1) 由无限阶元的定义，对任意正整数 $n$，$a^n \ne e$。又 $a^{-n} = (a^n)^{-1}$，若 $a^{-n} = e$，则 $a^n = e^{-1} = e$，矛盾。故 $a^{-n} \ne e$。
(2) 若 $a^i = a^j$，两边同时左乘 $a^{-i}$，得 $e = a^{j-i}$。由 (1)，当 $j - i \ne 0$ 时 $a^{j-i} \ne e$，故必须 $j - i = 0$，即 $i = j$。
(3) 由 (2) 直接得出。$\blacksquare$
五、有限阶元的基本性质
命题：设 $a$ 是群 $G$ 中的有限阶元，$o(a) = n$，则：
- 对任意整数 $m$，$a^m = e$ 当且仅当 $n \mid m$（$n$ 整除 $m$）。
- 对任意整数 $i, j$，$a^i = a^j$ 当且仅当 $i \equiv j \pmod{n}$。
-
$\langle a \rangle = {e, a, a^2, \ldots, a^{n-1}}$，且这 $n$ 个元素两两不同，即 $ \langle a \rangle = n$。
与整数加法群子群的联系：记 $H = {i \in \mathbb{Z} \mid a^i = e}$，可以验证 $H$ 是 $(\mathbb{Z}, +)$ 的子群，而 $n$ 是 $H$ 中最小的正整数。根据之前讲过的整数加法群子群的结构定理，$H = n\mathbb{Z}$，即 $H$ 恰好由 $n$ 的所有整数倍组成。下面的证明本质上是用带余除法直接重复了该论证。
5.1 证明
(1) 这是核心步骤，使用带余除法。
设 $m = qn + r$，其中 $0 \le r \le n - 1$。
因为 $a^n = e$，所以 $a^{qn} = (a^n)^q = e^q = e$。
从而 $a^m = a^{qn + r} = a^{qn} \cdot a^r = e \cdot a^r = a^r$。
- 充分性：若 $n \mid m$，则 $r = 0$，$a^m = a^0 = e$。
- 必要性：若 $a^m = e$，则 $a^r = e$。若 $r \ne 0$，则 $r$ 是一个满足 $1 \le r \le n - 1$ 的正整数且 $a^r = e$，这与 $n$ 是使得 $a^n = e$ 的最小正整数矛盾。故 $r = 0$，即 $n \mid m$。$\blacksquare$
这个证明与之前证明”整数加法群的子群一定形如 $n\mathbb{Z}$”的方法完全一致：对阶做带余除法，再利用最小性得到余数为零。
(2) 由群的消去律：$a^i = a^j$ 两边同时左乘 $a^{-i}$，得 $e = a^{j-i}$。由 (1)，$a^{j-i} = e$ 当且仅当 $n \mid (j - i)$，即 $i \equiv j \pmod{n}$。
(3) 需说明两点：
- 两两不同：设 $0 \le i, j \le n - 1$ 且 $a^i = a^j$，由 (2) 知 $i \equiv j \pmod{n}$。但 $i, j$ 都在 $0$ 到 $n - 1$ 之间，模 $n$ 同余则必相等。
- 遍历性：对任意整数 $m$，对 $n$ 做带余除法 $m = qn + r$（$0 \le r \le n - 1$），则 $a^m = a^r$，而 $r \in {0, 1, \ldots, n - 1}$。
因此 $\langle a \rangle$ 恰好由 $n$ 个不同元素组成。$\blacksquare$
一个元素的阶为 $n$，它生成的子群恰好含有 $n$ 个元素。因此群元素的阶与其生成子群的阶（元素个数）是一致的。
六、元素幂次的阶
命题：设 $a$ 是群 $G$ 中的有限阶元，$o(a) = n$，$m$ 为正整数，则：
\[o(a^m) = \frac{n}{\gcd(m, n)}\]6.1 例子
设 $o(i) = 4$（其中 $i = \sqrt{-1}$）。
- $m = 2$：$o(i^2) = o(-1) = \frac{4}{\gcd(2, 4)} = \frac{4}{2} = 2$。
- $m = 3$：$o(i^3) = o(-i) = \frac{4}{\gcd(3, 4)} = \frac{4}{1} = 4$。
6.2 证明
记 $d = \gcd(m, n)$。需证 $o(a^m) = \frac{n}{d}$。
第一步：证明 $(a^m)^{n/d} = e$。
\[(a^m)^{n/d} = a^{mn/d}\]因为 $d \mid m$，所以 $\frac{m}{d}$ 是整数，从而 $\frac{mn}{d} = n \cdot \frac{m}{d}$ 是 $n$ 的倍数。由于 $o(a) = n$，故 $a^{mn/d} = e$。
第二步：证明 $\frac{n}{d}$ 是最小的。
设正整数 $k$ 满足 $(a^m)^k = e$，即 $a^{mk} = e$。由 $o(a) = n$ 知 $n \mid mk$。
由整除的性质：$n \mid mk$ 且 $d = \gcd(m, n)$，则 $\frac{n}{d} \mid k$。
这里用到的关键性质是：若 $n \mid mk$，则 $\frac{n}{\gcd(m,n)} \mid k$。证明方法是在 $n \mid mk$ 两边同时除以 $d = \gcd(m,n)$，得 $\frac{n}{d} \mid \frac{m}{d} \cdot k$，而 $\frac{n}{d}$ 与 $\frac{m}{d}$ 互素，故 $\frac{n}{d} \mid k$。
因此满足 $(a^m)^k = e$ 的最小正整数 $k$ 就是 $\frac{n}{d}$，即 $o(a^m) = \frac{n}{d}$。$\blacksquare$
这个公式非常基本：$o(a^m) = \dfrac{n}{\gcd(m, n)}$，其中 $n = o(a)$。
七、循环群的具体例子
7.1 模 $n$ 加法群
\[(\mathbb{Z}_n, +_n) = (\{0, 1, 2, \ldots, n - 1\}, +_n)\]这是一个 $n$ 阶循环群，$1$ 是它的一个生成元。这在之前已经验证过。
7.2 $n$ 次单位根群
设 $n$ 为正整数，令：
\[\mu_n = \{z \in \mathbb{C}^* \mid z^n = 1\}\]即所有 $n$ 次单位根组成的集合。$\mu_n$ 是非零复数乘法群 $(\mathbb{C}^*, \cdot)$ 的子群，且是一个 $n$ 阶循环群。
| 几何解释：在复平面上，$n$ 次单位根恰好是单位圆周 $ | z | = 1$ 上等分的 $n$ 个点。 |
一个生成元为：
\[\omega = \cos\frac{2\pi}{n} + i\sin\frac{2\pi}{n} = e^{2\pi i / n}\]则 $\omega$ 的 $k$ 次幂为：
\[\omega^k = \cos\frac{2k\pi}{n} + i\sin\frac{2k\pi}{n} = e^{2k\pi i / n}\]对应于单位圆上辐角为 $\frac{2k\pi}{n}$ 的点。当 $k$ 从 $0$ 取到 $n - 1$ 时，恰好得到 $n$ 个不同的点；$k = n$ 时回到 $\omega^0 = 1$，开始新的一周。
乘法对应旋转：乘以 $\omega$ 就是逆时针旋转 $\frac{2\pi}{n}$ 角度。$n$ 次旋转后回到原点，所以 $\omega^n = 1$。
例：$n = 6$ 时，$\omega = e^{i\pi/3} = \frac{1}{2} + \frac{\sqrt{3}}{2}i$，6 次单位根是单位圆上等分的 6 个点。$\omega^3 = -1$，$\omega^6 = 1$。
7.3 模 $n$ 乘法
定义
设 $n$ 为正整数。在 ${0, 1, 2, \ldots, n - 1}$ 上定义模 $n$ 乘法：
\[a \otimes_n b = (a \cdot b) \mod n\]与模 $n$ 加法类似：先做普通乘法，再取模。
基本性质
$({0, 1, \ldots, n - 1}, \otimes_n)$ 构成一个半群，且 $1$ 是其幺元。
- 结合律：由同余的性质（若 $a \equiv b \pmod{n}$，$c \equiv d \pmod{n}$，则 $ac \equiv bd \pmod{n}$）可验证。
- 交换律：由整数乘法的交换律得出。
- 多元素乘法：$a_1 \otimes_n a_2 \otimes_n \cdots \otimes_n a_k = (a_1 \cdot a_2 \cdots a_k) \mod n$。
实际计算时，应逐步取模（每乘一次就取模一次），以控制中间结果的大小，避免数值过大。
不一定构成群
一般来说，$({0, 1, \ldots, n - 1}, \otimes_n)$ 不构成群：
- $0$ 没有逆元（$0$ 与任何数的模 $n$ 乘积都是 $0$）。
- 即使去掉 $0$，剩下的 ${1, 2, \ldots, n - 1}$ 也不一定构成群。
反例：$n = 6$ 时，$2 \otimes_6 3 = 0$，运算不封闭。逐一验证 $2$ 与 $1, 2, 3, 4, 5$ 的模 $6$ 乘积分别为 $2, 4, 0, 2, 4$，均不等于 $1$，所以 $2$ 没有逆元。
本质原因：$2$ 是偶数，$6$ 也是偶数，$2$ 与任何数的乘积都是偶数，模 $6$ 后仍是偶数，不可能等于 $1$。
八、模素数乘法群
8.1 命题
设 $p$ 为素数，则 $({1, 2, \ldots, p - 1}, \otimes_p)$ 构成一个 $p - 1$ 阶循环群。
例：$p = 7$ 时，${1, 2, 3, 4, 5, 6}$ 在模 $7$ 乘法下构成群。每个元素的逆元为：
| 元素 $a$ | 逆元 $a^{-1}$ | 验证 |
|---|---|---|
| $1$ | $1$ | $1 \times 1 = 1$ |
| $2$ | $4$ | $2 \times 4 = 8 \equiv 1 \pmod{7}$ |
| $3$ | $5$ | $3 \times 5 = 15 \equiv 1 \pmod{7}$ |
| $6$ | $6$ | $6 \times 6 = 36 \equiv 1 \pmod{7}$ |
8.2 素数的定义
定义：正整数 $m \ge 2$ 称为素数，若 $m$ 的正整数因子只有 $1$ 和 $m$ 本身。等价地，对任意 $2 \le d \le m - 1$，$d \nmid m$。
8.3 素数的关键性质
命题：设 $p$ 为素数，$n$ 为整数，则以下两种情形恰有一个成立：
- $p \mid n$（$p$ 整除 $n$）；
- $\gcd(p, n) = 1$（$p$ 与 $n$ 互素）。
证明：设 $d = \gcd(p, n)$，则 $d$ 是 $p$ 的正整数因子。由 $p$ 是素数，$d = 1$ 或 $d = p$。
- 若 $d = p$，则 $p \mid n$。
- 若 $d = 1$，则 $\gcd(p, n) = 1$，由裴蜀定理，存在整数 $u, v$ 使得 $pu + nv = 1$。$\blacksquare$
8.4 验证构成群
利用上述素数的性质，可以验证 ${1, 2, \ldots, p - 1}$ 在模 $p$ 乘法下构成群：
- 封闭性：若 $1 \le a, b \le p - 1$，需证 $a \otimes_p b \ne 0$。否则 $p \mid ab$，由 $p$ 是素数且 $p \nmid a$、$p \nmid b$，矛盾。
- 结合律：由同余乘法的性质保证。
- 幺元：$1$ 是幺元。
- 逆元：对 $1 \le a \le p - 1$，$\gcd(a, p) = 1$，由裴蜀定理存在整数 $u, v$ 使得 $au + pv = 1$，即 $au \equiv 1 \pmod{p}$，取 $u \mod p$ 即为 $a$ 的逆元。
至于为什么它还是循环群（即存在生成元），这与域上多项式的根的个数不超过次数有关，后面讲域的时候会详细说明。
九、密码学应用的简要提及
不同的循环群虽然抽象结构相同（同阶的循环群彼此同构），但具体运算的计算复杂度不同。例如：
- 模 $n$ 加法运算简单
- 模 $n$ 乘法稍复杂
- 某些循环群中的”逆运算”（如离散对数问题）计算困难
在密码学中，会选取”正向运算容易、逆向运算困难”的循环群来构建加密方案。