群

对于一个集合 $G$，若一个二元运算 $\circ$ 满足以下条件：

• 封闭性：$\forall x, y \in G, x \circ y \in G$。
• 结合律：$\forall x, y, z \in G, (x \circ y) \circ z = x \circ (y \circ z)$。
  • 因此我们可以省略括号，直接记为 $x \circ y \circ z$。
  • 同理我们可以定义 $\circ$ 对应的巨运算符 $\prod$，比如 $\prod_{i=1}^3 x_i = x_1 \circ x_2 \circ x_3$。
  • 同一元素 $x$ 作 $n$ 次连续运算，可以记作幂 $x^n = \prod_{i=1}^n x$。
• 有单位元 $e$：$\exists e \in G, \forall x \in G, x \circ e = e \circ x = x$。
• 任意元素 $x$ 有逆元 $y$：$\forall x \in G, \exists y \in G, x \circ y = y \circ x = e$。

则称 $G$ 对 $\circ$ 构成群（Group），记为群 $(G, \circ)$ 或直接简称为群 $G$。

群 $G$ 的元素个数 $\lvert G \rvert$ 被称为群的阶（Order）。若群的元素个数有限则称 $G$ 为有限群，反之称为无限群。

注意群的定义不要求 $\circ$ 有交换律（即 $\forall x, y \in G, x \circ y = y \circ x$）。若 $\circ$ 真的有交换律，为了纪念 Abel，称 $G$ 为阿贝尔群（Abelian group） 或交换群（Commutative group）。

注：为了减少篇幅，我们使用了一个较强的群的定义。理论上，四条中的后两条可以简化为单侧的 $e \circ x = x$ 和 $y \circ x = e$，而另一侧的可以被证明出来。

一些例子

整数 $\mathbb Z$ 对 $+$ 构成无限 Abel 群：

• 封闭性显然；结合律显然。
• 单位元：$0$ 是加法单位元。
• 逆元：任意整数的逆元为其相反数。

去除 $0$ 的有理数 $\mathbb Q$ 对 $\times$ 构成无限 Abel 群：

• 封闭性显然；结合律显然。
• 单位元：$1$ 是乘法单位元。
• 逆元：任意非 $0$ 有理数的逆元为其倒数。

对于质数 $p$，去除 $0$ 的 $\bmod p$ 剩余系对 $\bmod p$ 乘法构成有限 Abel 群，记作 $(\mathbb Z / p \mathbb Z)^\times$：

• 封闭性显然；结合律显然。
• 单位元：$1$ 是模乘法单位元。
• 逆元：根据扩展 Euclid 算法，任意元素 $x$ 有逆元。

非奇异的 $n$ 维实矩阵对矩阵乘法构成无限群，称为一般线性群（General Linear Group），记作 $GL_n(\mathbb R)$：

• 封闭性显然；结合律显然。
• 单位元：单位矩阵 $\mathbf I$ 是矩阵乘法单位元。
• 逆元：任意非奇异矩阵都能求逆。
• 注意该群不是 Abel 群。

证明：单位元唯一性

我们猜测群的单位元唯一。

使用反证法，假设有两个不同的单位元 $e_1 \ne e_2$，考虑 $e_1 \circ e_2$ 的值。

由于 $e_1$ 是单位元：

由于 $e_2$ 是单位元：

因此 $e_1 = e_2$，矛盾，证毕。

证明：逆元唯一性

我们猜测群中任意元素逆元唯一。

使用反证法，假设 $x$ 有两个不同的逆元 $y_1, y_2$：

考虑 $y_1 \circ x \circ y_2$ 的值：

矛盾，证毕。

任意元素逆元唯一，因此逆元 $y$ 是原元素 $x$ 的函数，可以直接记作 $x^{-1}$。进一步地，可以记 $x^{-n} = (x^{-1})^n = (x^n)^{-1}$，不难验证这满足幂函数的运算法则。

$(x \circ y)^{-1}$

一堆作用起来的元素一起求逆元，则展开时需要反着展开。

群的直积

对于两个群 $(G, \circ)$ 和 $(H, *)$，其直积（Direct product） $G \times H$ 也是一个群，为直接打包处理这两个群。

具体来说，其元素为直接合并的二元组：

其运算为：

重排定理

回忆 $(\mathbb Z / p \mathbb Z)^\times$ 的 Fermat 小定理

在证明该定理的过程中，核心结论是

事实上，这个结论对任意群（不论有限群还是无限群）都是成立的，称为重排定理：

设群 $G = {x_1, \cdots, x_n}$。

令 $a \circ G := {a \circ x_1, \cdots, a \circ x_n}$，有

令 $G \circ a := {x_1 \circ a, \cdots, x_n \circ a}$，有

证明

仿照 Fermat 小定理的证明。我们希望证明 $x \mapsto a \circ x$ 是一个双射，即它又是单射又是满射。

单射：若 $a \circ x = a \circ y$ 则

因此构成单射。

满射：对于任意 $x$，

因此 $a^{-1} \circ x$ 被映射到 $x$，构成满射。

因此构成双射，证毕。

另一侧结论证明同理，略去。

子群

有一个群 $(G, \circ)$。若子集 $H \subseteq G$ 对 $\circ$ 依然构成群，则称群 $H$ 是群 $G$ 的子群（Subgroup），记作 $H \le G$。

例：考虑 $\bmod 12$ 剩余系的加法群 $\mathbb Z_{12} = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}$，它的一些子群有 ${0, 3, 6, 9}, {0, 4, 8}$ 等。

不难发现，对于有限群，子群的大小似乎总是原群的大小的因数。

如何理解这一点？考虑 $\mathbb Z_{12}$ 的一个划分：

$\mathbb Z_{12}$ 可以由子群和其“平移”的不交并得到，由于这些“平移”集的大小都相同，子群的大小当然是原群大小的因数。

陪集

根据“平移”的启发，我们定义陪集（Coset）：令 $H = {h_1, \cdots, h_m}$，

（根据重排定理，$a \circ h_i \ne a \circ h_j$，所有元素不重）

$a \circ H$ 和 $H \circ a$ 分别称为左陪集（Left coset）和右陪集（Right coset）。注意陪集不一定是群。

陪集定理

$H$ 的任意两个不相等的（左）陪集不交，即陪集要么相等要么不交。

证明

假设 $a \circ H \cap b \circ H \ne \varnothing$，即存在 $a \circ h_1 = b \circ h_2$。

既然已经算出了 $a$ 的表达式，考虑 $a \circ H$ 的一个任意元素 $a \circ h$：

注意 $h_2 \circ h_1^{-1} \circ h \in H$，因此 $a \circ h = b \circ (h_2 \circ h_1^{-1} \circ h) \in b \circ H$。$a \circ H$ 的任意元素都属于 $b \circ H$，因此 $a \circ H \subseteq b \circ H$。

同理可证 $b \circ H \subseteq a \circ H$，因此 $a \circ H = b \circ H$，证毕。

Lagrange 定理

最后一步：$H$ 的所有陪集的不交并共同组成了 $G$，即 $G$ 的每个元素都落在某个陪集中。这个证明有点简单了：$\forall g \in G, g \circ e \in g \circ H$，证毕。

因此，$G$ 的子群 $H$ 的所有陪集等大且不重不漏地组成了整个 $G$。这一结论即为 Lagrange 定理。

定义指数（index）$[G : H]$ 为不同陪集的个数，显然指数若有限则必为正整数。

对于有限群 $G$，我们就得到了 $\lvert H \rvert$ 是 $\lvert G \rvert$ 的因数这一结论。