抽象代数基本概念

摘自 OI Wiki

---

本章节将简要介绍抽象代数的相关知识。现阶段算法竞赛的主要内容并不直接考察抽象代数的知识，但是在算法的描述或是问题的题解中常常会牵涉一些抽象函数的基本概念，这使得掌握了基础抽象代数概念的读者能够更快速理解一些算法。因此，这部分内容并不是任何选手的必修知识，而仅供那些感兴趣或者可能从中受益的读者参考使用。同时，本章节将避免过全过深的介绍抽象代数的知识，而会集中在基础概念以及与 OI 其他部分知识联系最为紧密的部分。想系统学习抽象代数知识的读者，应当参考专业的抽象代数教科书学习。

为了更好帮助读者理解阅读本部分内容可能的收获，列举一些算法竞赛中可能牵涉到抽象代数知识的例子：

• 数论和多项式的很多定理是抽象代数中结论的特例；
• 数据结构中，线段树 等结构可以维护幺半群的信息，而很多 DP 问题的递推关系可以抽象成这样的幺半群结构；
• 组合数学中，Pólya 计数原理 的严格表述和证明需要用到群论的相关概念。

基于此，本章节将着重介绍无法跳过的基础知识和与这些应用直接相关的部分。作为开始，本文介绍群、环、域的基本概念。

群

群的定义如下。

群

设 $G$ 是非空集合，其上有二元运算 $\cdot :G\times G\to G$，如果它们满足以下性质，则称 $(G,\cdot )$ 是一个 群（group）：

1. 结合律（associative property）：对于所有 $a,b,c\in G$，成立 $a\cdot (b\cdot c)=(a\cdot b)\cdot c$；
2. 有单位元：存在 $e\in G$，使得对于任意 $a\in G$，都成立 $a\cdot e=e\cdot a=a$。这里，$e$ 称为 $G$ 的 单位元（identity element），也称幺元；
3. 存在逆元：对于所有 $a\in G$，都存在相应的 $b\in G$ 使得 $a\cdot b=b\cdot a=e$。这里，$b$ 称为 $a$ 的 逆元（inverse element）。

关于定义中的封闭性条件

这里的二元运算就隐含了所谓的封闭性条件，即对于任何 $a,b\in G$，都有 $a\cdot b\in G$。有些文章会将其单独列出。

群的基本性质

1. 拓展结合律：对于任何有限长的列 $\{g_i{\}}_{i=1}^k\subseteq G$，乘积 $g_1\cdot g_2\cdot \cdots \cdot g_k$ 的运算结果与加括号的方式无关；
2. 单位元 $e$ 总是唯一的；
3. 对于任何元素 $a\in G$，它的逆 $a^{-1}$ 也是唯一的；
4. 消去律（cancellation law）：对于 $a,b,c\in G$，如果 $a\cdot c=b\cdot c$ 或 $c\cdot a=c\cdot b$，那么有 $a=b$。

群相当常见。通俗地说，所有不损失结构的变换都自动构成群。以常见的几种类型的群为例。

群的例子

• 对称群（symmetric group）：集合 $M$ 上的所有 置换，即自 $M$ 到 $M$ 自身的双射，就在映射的复合下构成群 $S_M$。单位元是恒等变换，逆元是逆映射（双射必然存在逆映射）。如果集合 $M$ 有限，大小为 $n$，也常记作 $S_n$，称作 $n$ 次对称群。
• 空间对称群（symmetry group）：对于一个几何图形，能够使其与自身重合的变换全体也在映射的复合下构成群。这描述了该几何图形的空间对称性。
• 整数的加法群：整数集 $\mathbf{Z}$ 在加法 $+$ 运算下构成群 $(\mathbf{Z},+)$。单位元是 $0$，逆元是相反数。
• 整数模 $n$ 乘法群（multiplicative group of integers modulo $n$）：对于一个模数 $n$，所有与 $n$ 互质的整数对应的 同余类，在乘法运算下构成群 $((\mathbf{Z}/n\mathbf{Z}{)}^{\times },\times )$。单位元是 $\overline{1}$，逆元就是模 $n$ 的 乘法逆元（对应的同余类），其存在性由 裴蜀定理 保证。
• 一般线性群（general linear group）：数域 $F$ 上的 $n$ 维的全体可逆方阵在乘法运算下构成群 $G{L}_n(F)$。单位元是单位矩阵，逆元是逆矩阵。

但是，想要更好地理解群的定义，不妨对比着看几个不属于群的例子。

不是群的例子

• 所有 $M$ 到自身的映射（不一定是双射），并不构成群。因为那些不是双射的映射不存在逆元。
• 整数在乘法下并不构成群，因为 $2$ 在整数范围内没有乘法逆元。
• 正整数在加法下也不构成群，因为正整数没有加法单位元。
• 模 $n$ 的所有非零同余类在乘法意义下往往不构成群。比如说 $(\mathbf{Z}/6\mathbf{Z})\setminus \{\bar{0}\}$ 中，$\bar{2}\times \bar{3}=\bar{0}$ 不属于这个集合，这意味着乘法都不是这个集合上良定义的二元运算（或者说，它不满足封闭性）。

但有时，也需要讨论这些更不完善的结构的性质。因此，可以定义如下概念，它们比群更宽泛。

• 半群
  • 对于非空集合 $G$ 和其上的二元运算 $\cdot$，如果该运算满足结合律，则称 $(G,\cdot )$ 是一个 半群（semigroup）。
• 幺半群
  • 对于半群 $(G,\cdot )$，如果它还存在单位元，则称 $(G,\cdot )$ 是一个 幺半群（monoid）。

在上面的例子中，$({\mathbf{N}}_{+},+)$ 是半群，而 $(\mathbf{Z},\times )$ 是幺半群。

最后，很多熟悉的群上的运算除了满足结合律外，还满足交换律。这类群的结构相对简单，它们称作 Abel 群，也称作交换群。

Abel 群

对于群 $(G,\cdot )$，如果运算 $\cdot$ 还满足交换律（commutative property），即对于所有 $a,b\in G$，都成立 $a\cdot b=b\cdot a$，则称 $(G,\cdot )$ 是一个 Abel 群（Abelian group）或 交换群（communicate group）。

Abel 群和非 Abel 群的例子

• 整数加法群 $(\mathbf{Z},+)$ 就是一个 Abel 群。
• 当 $n\ge 3$ 时，对称群 $S_n$ 并不是 Abel 群。

这些就是群论的基本定义与部分相关概念。

---

环

环的定义如下。

环

对于非空集合 $R$ 和其上的两个二元运算 $+:R\times R\to R$ 和 $\cdot :R\cdot R\to R$，如果它们满足以下性质，则称 $(R,+,\cdot )$ 是一个 环（ring）：

1. $(R,+)$ 构成 Abel 群，其单位元记作 $0$，元素 $a\in R$ 在 $+$ 下的逆元记作 $-a$。
2. $(R,\cdot )$ 构成半群，即 $\cdot$ 满足结合律。
3. 分配律（distributive property）：对于所有 $a,b,c\in R$，成立 $a\cdot (b+c)=a\cdot b+a\cdot c$ 和 $(a+b)\cdot c=a\cdot c+b\cdot c$。

为表述方便，这两个二元运算 $+$ 和 $\cdot$ 常称作该环的加法和乘法，相应地，加法单位元称作 零元（zero），乘法单位元（如果存在）称作 幺元（identity）。应避免和具体的数集中的加法、乘法，以及自然数 $0$ 和 $1$ 产生混淆。

关于定义中是否要求乘法单位元

在有的定义中，环必须存在乘法单位元；相对地，不存在乘法单位元的则被称为 伪环（rng 或 pseudo-ring）。遇到的时候需根据上下文加以判断。 维基百科采用的就是这种定义。

---

环的加法结构相当简单，但是乘法结构十分原始。因而如果类比群，在乘法上做更多要求，可以得到如下相关定义。

幺环

• 对于环 $(R,+,\cdot )$，如果它含幺，即存在乘法单位元，记作 $1$，则称 $(R,+,\cdot )$ 是一个 幺环（ring with identity）。

除环

• 对于非零幺环 $(R,+,\cdot )$，如果对于所有非 $0$ 元素 $a\in R$，都存在乘法逆元（记作 $a^{-1}$），则称 $(R,+,\cdot )$ 是一个 除环（division ring）。

交换环

• 对于环 $(R,+,\cdot )$，如果它的乘法满足交换律，则称 $(R,+,\cdot )$ 是一个 交换环（commutative ring）。

NOTE

这里除环的定义中有趣的一点是，它将 $0$ 视为乘法结构中的特殊元素。这是因为 $0=0\cdot a=a\cdot 0$。也就是说，环中加法单位元乘以任何元素都得到其自身。这样，它自然不会存在乘法逆元，除非它本身就是乘法单位元。这样的环只有零环（见下面的例子）。

这里的启示是，理解一般的环的乘法结构时，要去除加法单位元的影响，考察 $R\setminus \{0\}$。基于这一想法，有如下定义。

零因子

• 对于环 $(R,+,\cdot )$，如果存在 $b\in R$，成立 $a\cdot b=0$ 或 $b\cdot a=0$，则称非零元素 $a$ 为一个 零因子（zero divisor）。

可逆元（单位）

• 对于环 $(R,+,\cdot )$，如果元素 $a$ 有乘法逆元，即存在 $b\in R$，成立 $a\cdot b=b\cdot a=1$，则称元素 $a\in R$ 是一个 可逆元，或称 单位（unit）。

WARNING

「单位」与「单位元」

请不要混淆这两个概念。为避免混淆，抽象代数部分将使用「可逆元」的名称代替「单位」。

CAUTION

零因子不可能是可逆元，可逆元不可能是零因子。但是，一个非零元素可以既不是零因子，也不是可逆元。

如果一个环没有零因子，就说明所有非零元素的集合在乘法运算下封闭，即 $(R\setminus \{0\},\cdot )$ 构成半群。进一步地，如果还要求它成为交换幺半群，就可以得到整环的定义。

整环

对于非零环 $(R,+,\cdot )$，如果它是交换环，有乘法单位元，且无零因子，则称它为整环（integral domain）。

环的例子

• 零环（zero ring）：集合 $\{0\}$ 在通常意义的加法 $+$ 和乘法 $\times$ 下构成环，称为零环。它是唯一的只有一个元素的环，也是唯一的加法单位元和乘法单位元相等的环。

• 整数环：整数集 $\mathbf{Z}$ 和其上通常定义的加法 $+$ 和乘法 $\times$ 构成了环 $(\mathbf{Z},+,\times )$。实际上，这是一个整环，但是它不是除环。

• 多项式环：对于一个环 $R$，可以在上面定义多项式环 $R[x]$。如果 $R$ 是整环，则该多项式环必然是整环。

• 四元数（quaternion）：类比复数，可以考虑集合 $\mathbf{H}=\{a+b\mathrm{i}+c\mathrm{j}+d\mathrm{k}:a,b,c,d\in \mathbf{R}\}$，并且定义其上的加法和乘法，这里，$\mathrm{i},\mathrm{j},\mathrm{k}$ 的乘法运算满足

  $${\mathrm{i}}^2={\mathrm{j}}^2={\mathrm{k}}^2=-1,\mathrm{i}\mathrm{j}=-\mathrm{j}\mathrm{i}=\mathrm{k},\mathrm{j}\mathrm{k}=-\mathrm{k}\mathrm{j}=\mathrm{i},\mathrm{k}\mathrm{i}=-\mathrm{i}\mathrm{k}=\mathrm{j}.$$

  那么可以验证，$\mathbf{H}$ 构成环，而且，它是一个非交换的除环。

• 整数集的子集 $2\mathbf{Z}$，在通常意义的加法和乘法下构成环，它是交换环，没有零因子，但是并不含幺。

• 整数模 $n$ 同余类 $\mathbf{Z}/n\mathbf{Z}$ 在同余类的加法和乘法运算下构成环，它是交换环，含幺（即 $\overline{1}$）。这样的环含有零因子，当且仅当 $n$ 是合数。所以，当 $n$ 是素数时，环 $(\mathbf{Z}/n\mathbf{Z},+,\times )$ 是整环；而且，此时它也是除环，所以它实际构成为了一个域。

• 矩阵环：环 $R$ 上的全体 $n$ 维方阵在矩阵的加法和乘法下构成一个环 $M_n(R)$。一般地，这个环有零因子，且不是交换环。

• 对于一个集合 $A$ 的全体子集 $\mathcal{P}(A)$，如果定义集合的对称差 $\mathrm{△}$ 和交 $\cap$ 分别为其加法和乘法运算，则 $(\mathcal{P}(A),\mathrm{△},\cap )$ 构成环。一般地，这个环含幺，有零因子，且是交换环。

域

域是一个比环性质更强的代数结构。具体地，域是交换除环。当然也可以写出它完整的定义。

域

对于非空集合 $F$ 和其上的两个二元运算 $+:F\times F\to F$ 和 $\cdot :F\times F\to F$，如果它们满足以下性质，则称 $(F,+,\cdot )$ 是一个 域（field）：

1. $(F,+)$ 构成 Abel 群，其单位元记作 $0$，元素 $a\in F$ 在 $+$ 下的逆元记作 $-a$。
2. $(F\setminus \{0\},\cdot )$ 构成 Abel 群，其单位元记作 $1$，元素 $a\in F\setminus \{0\}$ 在 $\cdot$ 下的逆元记作 $a^{-1}$。

换句话说，域是对加、减、乘、除四则运算都封闭的代数结构。

常见的域的例子如下。

域的例子

• 数域：有理数集 $\mathbf{Q}$，实数集 $\mathbf{R}$ 和复数集 $\mathbf{C}$ 在通常意义的加法和乘法下都构成域。

• 有限域（finite field）：以质数 $p$ 为模的整数同余类的集合 $\mathbf{Z}/p\mathbf{Z}$ 在同余类的加法和乘法下构成域。当然，除此之外还有其他的有限域，它们的结构由其大小唯一确定，且大小必然是质数幂的形式。

• 分式域（fraction field）：设 $(R,+,\cdot )$ 为整环，可以考虑形如 $a{b}^{-1}$ 的元素构成的集合 $Q$。严格地说，在集合 $R\times (R\setminus \{0\})$ 上定义等价关系：$(a_1,b_1)\sim (a_2,b_2)$ 当且仅当 $a_1{b}_2=a_2{b}_1$。那么，集合 $Q$ 就是这一关系下的等价类构成的集合 $R\times (R\setminus \{0\})/\sim$，其中，$(a,b)$ 所在等价类就记作 $a{b}^{-1}$。如果定义它上面的运算为

  $$\begin{array}{rl}{a}_1{b}_1^{-1}+a_2{b}_2^{-1}& =(a_1\cdot b_2+a_2\cdot b_1)(b_1\cdot b_2{)}^{-1},\\ (a_1{b}_1^{-1})\cdot (a_2{b}_2^{-1})& =(a_1\cdot a_2)(b_1\cdot b_2{)}^{-1}\end{array}$$

  则 $(Q,+,\cdot )$ 构成域，称为 $R$ 的分式域。例如，有理数域 $(\mathbf{Q},+,\times )$ 就是整数环 $(\mathbf{Z},+,\times )$ 的分式域。

• 二次域（quadratic field）：它是在有理数域 $\mathbf{Q}$ 中添加了 $\sqrt{d}$ 而扩张成的，这里 $d\ne 0,1$ 且没有平方因子。

---

域相较于环，拥有着非常简单的加法和乘法结构。所以，域本身的结构往往很简单。这使得域的研究和环的研究大不相同，通常会转而研究域的扩张，以及相应的 Galois 理论。在算法竞赛中，有时会需要在有理数域或者有限域的扩域上进行计算。域论的相关内容，可以参考域论或相关书籍。