有限域入门

· · 个人记录

码字不易，求点赞+关注 qwq

全文较长，阅读时间取决于基础。

〇、写在前面

笔者以前还在 OI 圈的时候就胡思乱想过许多 trivial 的问题，比如说：为什么答案能对 p 取模？这个问题其实包含较深的内涵：\mathbb Z/p 构成域，运算的 well-definedness……只是那时数学基础尚未打起来，对这些问题限于一知半解。现在作为一个学数学的学生（自豪脸），这些问题基本上都得以解决。这篇文章旨在向（和曾经的我一样）求知欲旺盛的人们科普少量的有限域相关知识。

注：本文与 OI 没有太大关系，不保证文中内容在 OI 里有用。笔者水平不到一年级，看法粗陋浅薄，如有其他见解欢迎讨论。

前置知识：群和环相关的知识。基本上只需要知道定义、同态这些概念就可以，例如整环、理想等等概念在文中会有提到，但忽略它们不影响整体脉络。

一、域的基础概念

1.1 域的定义

定义：一个域（field）是一个三元组 (S,+,\cdot)，其中 +（称为“加法”）和 \cdot（称为“乘法”）是集合 S 上的二元运算，满足：

容易发现，域实际上就是交换幺环（含单位元的交换环）的概念中，加入了乘法逆元之后形成的结构。事实上，这导致：

命题：域一定是整环（即 ab=0 可推出 a=0 或 b=0）。

证明：若 ab=0，且 a\ne 0，则 a^{-1}ab=a^{-1}0=0，即 b=0。

例：

定义：有限域（finite field）是指元素个数有限的域。

有限域又称伽罗瓦域（Galois field），缩写 GF。用“我可以做你的有限域吗”或“你可以做我的有限域吗”表白，享受属于数学人的浪漫！亲测有效！

熟悉群、环理论的同学一定知道，我们常常研究这些结构的子结构（如：子群、理想）。但是对于域来说，相对于子域，我们更多地考虑扩域。

定义：域 E 称为域 F 的扩域，记作 E/F，若 F 作为集合是 E 的子集，且与 E 使用同样的二元运算。

例：

1.2 域同态

仅仅有域还不够，我们需要联系域的关系。（从范畴论的角度来说，需要找到对象（object）之间的态射（morphism）。）仿照环同态的概念，我们有：

定义：域 F 到域 E 的一个域同态（field homomorphism）是指一个映射 f:F\rightarrow E，满足：

若存在域同态 g:E\rightarrow F 满足 f\circ g=\text{id}_E, g\circ f=\text{id}_F（即 f 存在逆映射），则称 f 是域同构（field isomorphism）。容易证明 f 是域同构当且仅当 f 是域同态，且 f 是双射。

若 f 是单射，则称 f 是单同态（monomorphism），又称嵌入（embedding），记作 f:F\hookrightarrow E。此时可以把 E 看作 F 的扩域。

为何更多考虑扩域呢？思考正规子群和理想的概念来源，容易发现：

研究子结构的一个重点是其对应的商结构。但是对于域，我们有如下结论：

命题：域同态一定是嵌入。

证明：考虑域同态 f:F\rightarrow E，则 \text{ker} f 是 F 作为环的理想。若 \text{ker} f 非平凡，即 \text{ker} f\ne \{0\}，取 a\in \text{ker} f，a\ne 0，则根据理想的性质，1=a\cdot a^{-1}\in\text{ker} f，即 f(1)=0。而根据幺环的同态的定义，f(1) 必须是 1，矛盾。因此 \text{ker} f=\{0\}，即 f 是单射，由定义 f 是嵌入。

因此，我们较少重点考虑域的子结构，而常常考虑扩域和中间域。（我们常常重点研究域的自同构（automorphism）也是这个原因。）

1.3 域的结构

命题：域 E/F，则 E 是 F 上的线性空间（即 向量空间）。

证明：由域的定义显然。

定义：域 E 被称为 F 的有限扩张（finite extension），若 E 是 F 上的有限维线性空间。

推论：域 E 是 F 的有限扩张，则 E 作为线性空间同构于 F^n。

推论：域 E/F，且 E 和 F 是有限域，元素个数分别为 q 和 p，则存在正整数 r 使得 q=p^r。

注意到这给出了有限扩张的加法结构。

接下来给出有限域的乘法结构。

定义：F 是域，定义 F[x] 为 F 上的多项式环。

命题：F[x] 是欧几里得整环（Euclidean Domain），取 \text{deg}:F[x]\rightarrow \mathbb N。

粗略地说，欧几里得整环大致表明可以进行带余除法。

推论：F[x] 是主理想整环（Principle Ideal Domain）、唯一分解整环（Unique Factorization Domain）。

不了解这些概念不影响读者继续阅读。

定理（拉格朗日定理）：f\in F[x] 是 n 次多项式，则 f(x)=0 在 F 上至多有 n 个不同的根。

证明：n=1 显然成立。对于 n=k 的情况，任取一个根 x_0，则根据带余除法，f(x)=(x-x_0)g(x)。由归纳假设，g(x) 是 k-1 次多项式，因此至多 k-1 个不同的根，加上 x_0 至多 k 个不同的根。

下面不加证明地使用一个群论的定理。

定理（有限阿贝尔群结构定理）：G 是元素个数为 n 的有限阿贝尔群，则 G\cong C_{p_1}\times C_{p_2}\times\cdots\times C_{p_k}，其中 p_1|p_2|\cdots|p_k，p_1>1，且 p_1p_2\cdots p_k=n。这里 C_p 表示 p 阶循环群，\times 表示群的直积。

运用这个定理，我们可以证明：

定理：F 是 n 元有限域，则 F\setminus\{0\} 在乘法下构成循环群。

证明：设 F\setminus\{0\}\cong C_{p_1}\times C_{p_2}\times\cdots\times C_{p_k}，下证 k=1。

若 k\ne 1，则 p_k<n-1。易知任意元素的阶整除 p_k。考虑方程 x^{p_k}-1=0，则 F\setminus\{0\} 中的任意元素都是它的解，因此此方程有 n-1 个解。而这个方程是 p_k 次方程，p_k<n-1，矛盾。

因此 k=1，即 F\setminus\{0\}\cong C_{n-1}。得证。

推论：n 元有限域中存在 n-1 次本原单位根。

二、有限域的分类（上）

下一步是具体分类所有的有限域，唯一性分析和具体构造留到下一篇文章。

相信学习过 OI 的各位都见到过”对素数 p 取模“这样的字样，接下来我们用模 p 的同余等价类构造 p 元有限域。

定义：r 为正整数，定义 \mathbb Z 上的等价关系 \sim：a\sim b\Leftrightarrow r|(a-b)，则 \mathbb Z/r 定义为 \sim 下等价类（equivalence class）的集合，a\in \mathbb Z 对应的等价类记作 a+r\mathbb Z 或 \overline{a}。定义 \mathbb Z/r 上的运算：\overline a+\overline b:=\overline{a+b}，\overline a\cdot \overline b:=\overline{a\cdot b}。容易验证这样的运算是良定义（well-defined）的，即 a,b 的选取不同不会影响运算结果。容易证明 \mathbb Z/r 在此运算下构成交换幺环。

注：实际上 \mathbb Z/r 是 \mathbb Z/(r) 的简写，这里 (r) 指的是元素 r 生成的理想（ideal）。

例：

定理：p 是质数时 \mathbb Z/p 是域。

高端证明：易知 (p) 是极大理想，因此 \mathbb Z/p 是域。

证明：\forall \overline a\in \mathbb Z/p\setminus\{0\}，由 \gcd(a,p)=1 知 \exist b,c\in \mathbb Z，使得 ab+pc=1，则 \overline b 是 \overline a 的乘法逆元。得证。

本质上还是在说任意其他理想与极大理想互素，和上面那个高端证明是一个意思。

接下来我们揭示每个有限域都可以视作 \mathbb Z/p 的扩域。

定义：域 F 的特征（characteristic）为最小的正整数 p 使得 p\cdot 1=0，记作 \text{char} F=p。若不存在，则称 \text{char} F=0。

例：

命题：特征只能是零或质数。

证明：假设 F 的特征为合数 r=mn，其中 m,n>1。则 r\cdot 1=(m\cdot 1)\cdot (n\cdot 1)=0（分配律），由域的性质知 m\cdot 1=0 或 n\cdot 1=0，与 r 的最小性矛盾。得证。

定理：对任意有限域 F，设 F 的特征是 p，则存在一个嵌入 f:\mathbb Z/p\hookrightarrow F。因此，F 可以看成 \mathbb Z/p 的扩域。

证明：令 f(\overline a)=a\cdot 1，则容易验证 f 是良定义的，且是域同态。

以下是一个重要的推论。

推论：任意有限域 F 的元素个数必定是 p^n，其中 p=\text{char} F。

证明：由 F 是 \mathbb Z/p 的扩域以及有限扩张的加法结构可得。

一个常见误区：认为 p^n 元域同构于 \mathbb Z/{p^n} 或 (\mathbb Z/p)^n。实际上上述结构都不是域（而是交换幺环），有限域的结构要复杂许多。限于篇幅，有限域的具体构造以及唯一性的证明，还有一些其他必要知识，我们留到下篇文章。