前文从群开始讨论了抽象代数的一些基本概念，这篇文章我们完成讨论到有限域的构造。

环Ring

一个非空集合R，同时有两个二元操作符\oplus, \ast，其中对于(R, \oplus)构成一个阿贝尔群，且还满足下面的两个性质，则称(R,\oplus,\ast)是一个环(Ring):

• (R,\ast)满足结合律: \forall a,b,c \in R, (a\ast b)\ast c = a\ast (b\ast c)
• (R,\ast)封闭
• 满足分配律, \forall a,b,c \in R:
  • a\ast (b \oplus c) = (a\ast b) \oplus (a\ast c)
  • (a\oplus b)\ast c = (a\ast c)\oplus (b\ast c)

(R,\oplus)决定的阿贝尔群的identify是\mathbf{0}。如果\exists \mathbf{1} \in R, \mathbf{1} \ne \mathbf{0}, \text{且}\forall a \in R, \mathbf{1}\ast a = a\ast \mathbf{1} = a，那么我们称这个环R是a ring with unity(or a ring with identity)。如果(R,\ast)还满足交换律，那么可以称R是一个commutative ring。如果一个Ring R同时是commutative ring和a ring with unity，且还满足\forall a,b\in R, a\ast b = \mathbf{0} \implies (a=\mathbf{0}\lor b=\mathbf{0})，那么就称这个Ring R是一个integral domain。

下面定义unit的概念，然后引出division ring的概念：

• unit: a\in R, \exists! a^{-1} \in R, a\ast a^{-1} = a^{-1}\ast a = \mathbf{1}，则称a是unit
• division ring: R \text{ is a ring, } \forall a\ne \mathbf{0} \in R, a \text{ 是unit}，这时候称Ring R是division ring

A commutative division ring is called a field.

以上术语可以用下面的图来表示：

关于Rings我们看一个定理：令R是一个Ring，\forall a,b \in R，则：

• a\ast \mathbf{0} = \mathbf{0}\ast a = \mathbf{0}
• a\ast (-b) = (-a) \ast b = -(a \ast b)
• (-a)\ast (-b) = a\ast b

证明：这里的-a是元素a在(R,\oplus)这个阿贝尔群下的逆。

• a\ast \mathbf{0} = a \ast (\mathbf{0} + \mathbf{0}) = (a\ast \mathbf{0}) \oplus (a\ast \mathbf{0}) \implies \mathbf{0} =(a\ast \mathbf{0}) ，另一个同理可证。
• (a\ast b) \oplus ((-a)\ast b) = (a \oplus (-a)) \ast b = \mathbf{0} \ast b = \mathbf{0} \implies a\ast b \text{是} (-a) \ast b\text{的逆在}(R, \oplus)\text{这个阿贝尔群} ；同理我们可以证明a\ast b也是a\ast (-b)的逆。故而它们相等。
• ((-a) \ast (-b)) \oplus (a \ast (-b)) = ((-a) \oplus a) \ast (-b) = 0 \implies (a \ast (-b)) \text{是}((-a) \ast (-b))\text{的逆} ，结合上面的，得证。

多项式

一个非零m阶多项式f(x)，定义在一个field \mathbf{F}上的是如下的表达式：

f(x) = f_0 + f_1x+f_2x^2 + \dots + f_mx^m

其中f_i \in \mathbb{F}, i \in [0,m], f_m \ne 0。记作\text{deg }f(x) = m，x这里只是一个自变量的作用，它不要求x \in \mathbb{F}。f_0 \in \mathbb{F}是零阶非零多项式。

我们定义零多项式(zero polynomial)f(x) = 0，并且记它的阶数为\text{deg }0 = -\infty。所有\mathbb{F}上用x做自变量的多项式集合记为\mathbb{F}[x]。

多项式的加法、减法、乘法是逐项进行的，对于通用的域，等价于我们常见的实数域，仅仅需要主要把\oplus, \ast要用对应的\mathbb{F}上的。乘法得到的结果的新多项式的系数是由卷积决定的：

f(x)=h(x) \ast g(x) \implies f_i = \sum_{j=0}^{i} h_ig_{i-j}

\mathbb{F}[x]有很多性质：

• \mathbb{F}[x], \oplus构成一个阿贝尔群，其identity就是zero polynomial f(x) = 0
• \mathbb{F}[x]\text{在}\ast下是封闭的，且满足交换律、结合律，分配律
• \mathbb{F}[x]在\ast下有一个identify f(x) = 1，满足cancellation law

\mathbb{F}(x)很像域，但是一个非零的polynomial且阶数大于0在\ast下就没有一个逆。这就意味著\mathbb{F}[x]是一个Ring。

定义多项式的类似\mathbb{N}里的约数(divisor)概念。两个多项式f(x),g(x)，如果满足\exists q(x), f(x)=g(x)q(x)，我们称f(x)是g(x)的倍数(polynomial multiple)，称g(x)是f(x)的约数(divisor)。

存在多项式逆的多项式，是零阶的非零多项式：\beta \in \mathbb{F}^{*} = \mathbb{F} - \{\mathbf{0}\}。它们被称之为units of \mathbb{F}[x]。有下面的性质：

• u(x)\text{是一个unit多项式}, g(x)\text{是}f(x)\text{的约数} \implies u(x)g(x) \text{是}f(x)\text{的约数} \land g(x)\text{是}u(x)f(x)\text{的约数}

A Monic polynomial是一个非零多项式f(x)，假设\text{deg }f(x) = m，那么必须满足f_m = 1，即：f(x) = f_0 + f_1x+f_2x^2+\dots+x^m。任何一个非零多项式g(x)，假设阶数是m，可以被写成g(x) = g_mf(x)，其中g_m是一个unit polynomial，f(x)是m阶monic polynomial。因此，我们考虑多项式分解问题的时候，就可以集中精力在：把一个Monic polynomial分解成若干个Monic polynomials。

任何非零多项式f(x)必然有两个简单的divisor: 1, f(x)。如果一个Monic polynomialg(x), g(x)\ne 1, g(x) \ne f(x)，且g(x)是f(x)的一个divisor，则可以称g(x)是f(x)的一个factor，其阶数满足1 \le \text{deg }g(x) < \text{deg }f(x)。

如果一个非零多项式g(x)，其阶数满足\text{deg }g(x) \ne 1，且g(x)不存在任何factor，那么称g(x)是一个irreducible polynomial。A Monic polynomial如果还是an irreducible polynomial，那么称之为a prime polynomial.

我们开始看多项式的求模运算：\mod\text{-}g(x)。给定一个m阶monic polynomial g(x)，任一多项式f(x)都可以表示成f(x) = q(x) g(x) + r(x)，其中\text{deg }r(x) < \text{deg }g(x)。其这样的表示是唯一的。我们记r(x) = f(x) \mod g(x)。它所有的可能的集合是R_{\mathbb{F},m} = \{r_0+r_1x+\dots+r_{m-1}x^{m-1} | r_j \in \mathbb{F}, j\in[0,m-1]\}, 这个集合的大小是|R_{\mathbb{F},m}| = |\mathbb{F}|^m 。我们有： f(x) \mod g(x) = 0 \iff g(x) \text{ is a divisor of }f(x) 。

关于\mod\text{-}g(x)，给定r(x) = f(x) \mod g(x), s(x) = h(x) \mod g(x)则：

• (f(x) + h(x)) \mod g(x) = (r(x) + s(x))\mod g(x)
• f(x)h(x) \mod g(x) = r(x)s(x) \mod g(x)

关于多项式的因式分解的唯一性定理(Unique factorization of polynomials): 在任何一个给定的域上\mathbb{F},任何一个monic polynomial f(x) \in \mathbb{F}[x], \text{deg }f(x) \ge 1可以被写成如下形式：

f(x) = \prod_{i=1}^k a_i(x)

其中a_i(x) \in \mathbb{F}[x], i \in [1,k], 是prime polynomial。这种分解是唯一的。证明在这里省略不表。

如果在某个域\mathbb{F}_p, p\text{是素数}，给定了其上\mathbb{F}_p[x]一个prime polynomial，那么R_{\mathbb{F}_p, m}是一个域。这就给了我们构造元素个数是p^m的一般方法。证明R_{\mathbb{F}_p, m}是一个域，以及证明任何\mathbb{F}_p, p\text{是素数}都存在prime polynomial这里省略了。

参考资料

本文的参考资料同前文。