一、模 $n$ 加法群的群公理验证
回顾：设 $n$ 为正整数，在集合 ${0, 1, \ldots, n-1}$ 上定义运算
\[i \oplus j := (i + j) \mathbin{\%} n\]1.1 结合律
目标：证明 $(i \oplus j) \oplus k = i \oplus (j \oplus k)$。
方法：只需说明两边都同余于 $i + j + k \pmod{n}$。因为两边的值都在 ${0, \ldots, n-1}$ 中，且都与 $i + j + k$ 模 $n$ 同余，由同余的基本性质（在 ${0, \ldots, n-1}$ 中模 $n$ 同余则相等）即得两边相等。
具体地：
- 由定义，$i \oplus j \equiv i + j \pmod{n}$
- 故 $(i \oplus j) \oplus k \equiv (i + j) + k = i + j + k \pmod{n}$（利用同余式两边加同一个数不变）
类似地，$i \oplus (j \oplus k) \equiv i + (j + k) = i + j + k \pmod{n}$。
因此两边都同余于 $i + j + k$，又都在 ${0, \ldots, n-1}$ 中，故相等。$\blacksquare$
实际上，对任意 $m$ 个元素 $a_1, \ldots, a_m \in {0, \ldots, n-1}$，有 \(a_1 \oplus a_2 \oplus \cdots \oplus a_m = (a_1 + a_2 + \cdots + a_m) \mathbin{\%} n\) 即可以先做普通加法再取余。
从计算角度看，逐步做模 $n$ 加法（左边）比先全部加完再取余（右边）更高效，因为每步数字大小被 $n$ 控制住，不会溢出。
1.2 幺元
$0$ 是幺元：对任意 $i \in {0, \ldots, n-1}$，
\[i \oplus 0 = (i + 0) \mathbin{\%} n = i \mathbin{\%} n = i\]（因为 $0 \le i \le n-1$，所以 $i$ 除以 $n$ 的余数就是 $i$ 本身。）
此外，运算 $\oplus$ 是交换的（因为 $i + j = j + i$），所以 $0 \oplus i = i$ 也成立。
1.3 逆元
- 若 $i = 0$，则 $0$ 的逆元是 $0$（因为 $0 \oplus 0 = 0$）
- 若 $1 \le i \le n - 1$，则 $i$ 的逆元是 $n - i$（因为 $n - i \in {1, \ldots, n-1}$，且 $i \oplus (n-i) = (i + n - i) \mathbin{\%} n = n \mathbin{\%} n = 0$）
二、模 $n$ 加法群的子群
2.1 子群的完全刻画
命题. 模 $n$ 加法群 $({0, \ldots, n-1}, \oplus)$ 的子群与 $n$ 的正因子一一对应：
（一） 设 $d$ 是 $n$ 的正因子（$d \mid n$），则
\[H_d = \{0, d, 2d, \ldots, (n/d - 1) \cdot d\}\]是模 $n$ 加法群的子群，元素个数为 $n/d$。
（二） 反过来，模 $n$ 加法群的任何子群 $H$ 都等于某个 $H_d$，其中 $d$ 是 $n$ 的正因子。
这与整数加法群的子群结构类似：整数加法群的子群恰好是 $d\mathbb{Z}$（$d \in \mathbb{N}$），模 $n$ 加法群的子群恰好是 $d$ 的倍数限制在 ${0, \ldots, n-1}$ 中（$d \mid n$）。
一般群的子群很难完全描述，循环群的子群结构之所以简单，是因为它由一个元素生成。
2.2 第一部分的证明（$H_d$ 是子群）
设 $d \mid n$。需验证：
- 非空：$0 \in H_d$（$0$ 是 $d$ 的倍数）
- 对运算封闭：设 $j, k \in H_d$，即 $d \mid j$ 且 $d \mid k$。由同余的基本性质：
- $j \oplus k \equiv j + k \pmod{n}$
- 因 $d \mid n$，故 $j \oplus k \equiv j + k \pmod{d}$
- 又 $d \mid j$ 且 $d \mid k$，故 $d \mid (j + k)$
- 因此 $j \oplus k \equiv 0 \pmod{d}$，即 $d \mid (j \oplus k)$，所以 $j \oplus k \in H_d$
- 对逆元封闭：
- 若 $j = 0$，逆元为 $0 \in H_d$
- 若 $j \ne 0$，逆元为 $n - j$。因 $d \mid n$ 且 $d \mid j$，故 $d \mid (n - j)$，所以 $n - j \in H_d$
2.3 第二部分的证明概要（任何子群都是 $H_d$）
设 $H$ 是模 $n$ 加法群的子群。构造
\[K = \{i + ln \mid i \in H,\ l \in \mathbb{Z}\}\]可以验证 $K$ 是整数加法群的子群（且 $n \in K$）。由整数加法群子群的分类定理，存在 $d \in \mathbb{N}$ 使得 $K = d\mathbb{Z}$。因为 $n \in K$，所以 $d \mid n$。最终可以证明 $H = H_d$。$\blacksquare$
这个模 $n$ 加法群实际上就是整数加法群模子群 $n\mathbb{Z}$ 的商群 $\mathbb{Z}/n\mathbb{Z}$，后面讲商群时会回到这个视角。
三、由一个元素生成的子群
3.1 回顾：子集生成的子群
设 $(G, \cdot)$ 是群，$S \subseteq G$。存在唯一的包含 $S$ 的最小子群 $H$，记作 $\langle S \rangle$，称为 $S$ 生成的子群。
构造方法：$\langle S \rangle = \bigcap {H \mid H \text{ 是 } G \text{ 的子群且 } S \subseteq H}$（所有包含 $S$ 的子群之交）。
3.2 单元素生成的子群
若 $S = {a}$，简记 $\langle a \rangle = \langle {a} \rangle$。
$\langle a \rangle$ 由 $a$ 的所有幂次组成（下一讲给出完整描述）。
四、半群和群中的幂运算
4.1 半群中的幂（正整数指数）
设 $(G, \cdot)$ 是半群（即运算满足结合律），$a \in G$。对正整数 $n$，定义
\[a^n = \underbrace{a \cdot a \cdots a}_{n}\]等价的递归定义：$a^1 = a$，$a^{k+1} = a^k \cdot a$。
因为结合律保证括号可以任意添加，所以上述定义是清楚的。
4.2 幂运算的基本性质
命题. 设 $(G, \cdot)$ 是半群，$a \in G$，$i, j$ 为正整数。则：
- $a^{i+j} = a^i \cdot a^j$
- $(a^i)^j = a^{ij}$
性质1的证明（对 $j$ 归纳）：
- $j = 1$：$a^{i+1} = a^i \cdot a = a^i \cdot a^1$（定义）
- 归纳步：设对 $j$ 成立，则 \(a^{i+(j+1)} = a^{(i+j)+1} = a^{i+j} \cdot a = (a^i \cdot a^j) \cdot a = a^i \cdot (a^j \cdot a) = a^i \cdot a^{j+1}\) 其中用到了结合律和归纳假设。$\blacksquare$
性质2的证明（对 $j$ 归纳）：
- $j = 1$：$(a^i)^1 = a^i = a^{i \cdot 1}$（定义）
- 归纳步：设对 $j$ 成立，则 \((a^i)^{j+1} = (a^i)^j \cdot a^i = a^{ij} \cdot a^i = a^{ij+i} = a^{i(j+1)}\) 其中第二步用归纳假设，第三步用性质1。$\blacksquare$
如果觉得抽象，可以把 $a$ 想成实数、把运算想成乘法来理解——严格证明是完全一样的。
4.3 幺半群中的幂（自然数指数）
若 $(G, \cdot)$ 是幺半群（有幺元 $1_G$），额外定义
\[a^0 := 1_G\]此时性质1和性质2对所有自然数 $i, j$ 成立。
$a^0 = 1_G$ 是一个规定，目的是使幂运算的性质能平滑地从正整数推广到自然数。例如 $a^{0+j} = a^j = 1_G \cdot a^j = a^0 \cdot a^j$。
4.4 群中的幂（整数指数）
若 $(G, \cdot)$ 是群，对正整数 $n$ 定义
\[a^{-n} := (a^{-1})^n = (a^n)^{-1}\]这两种定义给出相同的元素（先取逆再求幂 = 先求幂再取逆），类似于 $(1/a)^n = 1/a^n$。此时性质1和性质2对所有整数 $i, j$ 成立（留作思考）。
五、快速幂算法（平方求幂法）
5.1 问题
输入半群元素 $a$ 和正整数 $n$，计算 $a^n$，使得半群运算次数尽量少。
5.2 朴素方法
逐步计算 $a, a^2, a^3, \ldots, a^n$，每步做一次乘法，共 $n - 1$ 次运算。
缺点：运算次数与 $n$ 的值成线性，而 $n$ 的值关于其位数是指数级的。
5.3 快速幂
核心思想：利用二进制展开和性质 $(a^i)^2 = a^{2i}$，反复平方。
例：计算 $a^8$，只需 $3$ 次运算： \(a \xrightarrow{\text{平方}} a^2 \xrightarrow{\text{平方}} a^4 \xrightarrow{\text{平方}} a^8\)
一般方法：将 $n$ 做二进制展开
\[n = \sum_{i \in I} 2^i \quad (a_i \in \{0, 1\},\ I = \{i : a_i = 1\})\]则
\[a^n = \prod_{i \in I} a^{2^i}\]- 先通过反复平方计算 $a, a^2, a^4, \ldots, a^{2^k}$（$k$ 次运算）
-
再将对应的项乘起来（$ I - 1$ 次运算）
总运算次数：约 $2\log_2 n$，即 $O(\log n)$。
朴素方法需要 $O(n)$ 次运算，快速幂只需 $O(\log n)$ 次——输入 $n$ 的位数级别。这在密码学、矩阵幂等实际计算中非常重要。