为了后面要讨论的Finite Projective Plane的构造算法中用到的Finite Prime Field，我们需要做一些抽象代数的回归。完整的抽象代数教材和课程固然好，但不适合突击。我找到了一份不错的小件一点儿的资料Introduction to finite fields (是Stanford CS250/EE387的补充阅读)。基于这份资料，我们列出所有需要弄清楚的问题，然后一一整理明白。
脉络、概念和问题
Group的定义和案例SubGroup的定义和案例group of unitsCyclic Group的定义和案例- 有限群
Cosets- 拉格朗日定理
- 欧拉定理
- 费马小定理
- 同态概念和案例
- 同构概念和案例
- 域的定义和案例
- 素数域的定义和性质
抽象代数复习
Group的定义和案例
一个集合\text{S}和定义在集合上的二元操作符\circ，如果同时满足下面几个条件，则称\text{S}是一个以\circ为操作符的Group：
- Closure: \forall a,b \in S, a \circ b \in S
- Associative: \forall a,b,c \in S, (a \circ b) \circ c = a \circ (b \circ c)
- Identity: \exists! \mathbf{1} \in S, \forall a \in S, a \circ \mathbf{1} = a \land \mathbf{1} \circ a = a. \mathbf{1} is called the identity.
- inverse: \forall a \in S, \exists b \in S, a\circ b = b \circ a = \mathbf{1} . a is b‘s inverse (vice versa).
群(Group)的二元操作符不需要满足交换律。如果一个群(Group)的二元操作符恰好也满足了交换律，我们就称之为阿贝尔群(Abelian Group)。
- \mathbb{Z}, +: 全体整数集合和整数的加法，构成一个阿贝尔群。其中的
Identity是数字0。 - \forall n > 0, S_n=\{0,1,2, \dots n-1\}, \circ = \lambda\ x\ y: (x + y) \mod n是一个阿贝尔群:
- S_n = \{ i \in \mathbb{N} | 0 \le i < n \}
- \forall a, b \in S_n, ((a + b) \mod n) \in [0, n) = S_n
- \forall a,b,c \in S_n, (a\circ b) \circ c = (((a+b) \mod n) + c) \mod n = (a\mod n + b\mod n + c\mod n)\mod n = (a \mod n + (b \mod n + c \mod n)) \mod n = (a + ((b+c)\mod n) \mod n = a \circ (b \circ c)
- \forall a \in S_n, (0 + a) \mod n = (a + 0) \mod n \implies 0 是
identify. - \forall a \in S_n, b = ((n-a)\mod n) \in [0, n) = S_n, a \circ b = (a+b) \mod n = (a+((n-a)\mod n)) \mod n = 0
我们现在来看一个很有意思的群: Symmetric Group. 考虑一个S_n=\{\text{all permutations of \{1,2,3,\dots,n\}}\}。显然|S_n| = n!。其中S3=\{(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2),(3,2,1)\}。对于其中任何一个元素，我们考虑赋予映射的含义：P=(p_1,p_2,\dots,p_n) \in S_n \implies P = \lambda \ i: p_i, i \in [1,n]，那么Symmetric Group的二元运算符就是算子(映射)的复合操作。
关于群的性质的证明略去，这里的identity是\mathbf{1}_n = (1,2,3,\dots,n)。
SubGroup的定义和案例
给定G, \circ是一个Group, 这时候有另一个集合S \subset G，于此同时，我们把运算符\circ的定义域(还写作\circ)，限定到S，如果S,\circ还满足Group的全部条件，那么我们称S是G的一个SubGroup。显然，如果S=\{\mathbf{1}_G\}，也就是只包含identify的时候，也是一个SubGroup，只不过没什么研究意义，称之为trivial subgroup。如果]S \text{ 是}G\text{的一个subgroup且} S \subsetneqq G，我们称之为proper subgroup。
下面研究一个案例：general linear group和special linear group。定义\mathbb{M}_n(\mathbb{R})为所有大小为n \times n实矩阵。集合\text{GL}_{n} = \{\mathbf{M} \in \mathbb{M}_n(\mathbb{R})) | \mathbf{M} \text{ is invertible} \}，即所有可逆的n \times n大小的实矩阵集合。定义这里的二元运算符\circ是n \times n的矩阵乘法。那么 \mathbf{GL}_n, \circ 是一个Group，其identity就是n\times n的单位矩阵，我们称之为general linear group。那么special linear group的集合就是\mathbf{SL}_n \subsetneqq \mathbf{GL}_n = \{\mathbf{M} \in \mathbf{GL}_n | \text{det}(\mathbf{M}) = 1 \}。我们称之为special linear group: \text{SL}_n ，它是\text{GL}_n的proper subgroup。
group of units
\mathbb{Z}_n = \{0,1,2,\dots,n-1\}, \circ = \lambda \ x \ y: (x+y) \mod n是一个group。\forall k \ne 0 \in \mathbb{Z}_n, \exists a \in \mathbb{Z}_n, (ka) \equiv 1 (\bmod n)。最后的二元运算法ak是乘法。
证明上面的命题，需要用到扩展欧几里得算法。\exists, x, y \in \mathbb{Z}, kx+ny = \text{gcd}(k,n)=1 \implies ny = 1-kx \implies kx \equiv 1 (\bmod n)。
这样，给定任何一个\mathbb{Z}_n，构造集合U(n) = \{k | k \in \mathbb{Z}_n, k \ne 0, k \perp n\}。这个集合称之为the group of units of \mathbb{Z}_n。可以验证，这也是一个group，对应的二元运算符是\circ = \lambda \ x\ y: (xy)\mod n。
Cyclic Group的定义和案例
给定一个Group G, \circ，我们选择其中一个元素a \in G, 复用这个二元运算符circ，用下面的办法构造一个G的SubGroup C:
- G‘s
identity\mathbf{1}_G \in C - a \in C
- \forall c \in C \implies \text{ the inverse of } c, c^{-1} \in C
故而这样的集合形态为： C = \{\dots, a^{-3}, a^{-2}, a^{-1}, \mathbf{1}_G, a, a^2, a^3, \dots \} , 其中\forall n > 0, a^n = \underbrace{a \circ a \circ a ... \circ a}_{n \text{ 个 } a}; a^{-n} \text{ is the inverse of } a^n。
可以证明C, \circ一起，是G, \circ的一个SubGroup。我们称之为Cyclic Group。我们把C记作\langle a \rangle。更进一步，有\langle a \rangle是G的所有subgroup里，包含a的最小的。
a \in G, 满足a^n=\mathbf{1}_G最小的正整数n，称之为the order of a，写作:|a|=n。若n不存在，则记为|a|=\infty。
关于Cyclic Group有很多有趣的性质和定理，我们略去证明，罗列如下：
- C是一个
Cyclic Group\implies C是一个阿贝尔群。 - C是一个
Cyclic Group, \forall S, S \text{ 是 }C\text{的subgroup} \implies S \text{是Cyclic的} - 整数集合\mathbb{Z}, \circ = + 的
SubGroups就是n\mathbb{Z}, \text{for }n = 0,1,2,3,\dots - G=\langle a \rangle是一个由a生成的
Cyclic Group，|a|=n。则a^k=\mathbf{1}_G \iff k \equiv 0 (\bmod n) 。 - G=\langle a \rangle是一个由a生成的
Cyclic Group，|a|=n。则b=a^k \implies |b| = \frac{n}{\text{gcd}(n,k)}. - n,r \in \mathbb{N}^{+}, 1 \le r < n, \text{gcd}(n,r)=1 \implies \langle r \rangle = \mathbb{Z}_n。
对于上面的最后一个结论，我们尝试证明一下。
Proof: 根据扩展欧几里得算法，我们可以找到整数x,y满足:rx + yn = \text{gcd}(n,r)=1。那么对于i \in [1,n), irx+iyn = i，则此时ir = r^i \equiv i (\bmod n) ；对于i=n,ir=r^n \equiv 0 (\bmod n)。故而\langle r \rangle = \mathbb{Z}_n。
有限群
一个群对应的集合只有有限多个元素的话，称之为有限群finite group。G,\circ是一个有限群，则|G|=n表示该群集合里的元素数目，称之为the order of G。
定理: G , \circ 是有个有限群，\forall g \in G, g^{|G|} = \mathbf{1}_G。
证明: \forall g \in G, C = \langle g \rangle是G的一个cyclic subgroup。则必然有g^{|C|} = \mathbf{1}_G。再结合后面的拉格朗日定理，有|C|整除|G|。那么g^{|G|} = (g^{|H|})^k = \mathbf{1}_G。
Cosets
H \text{ 是 } G的一个subgroup, 二元运算符是\circ，则给定g\in G时left coset的定义如下：
同理可定义出right coset：
下面看一个重要的性质：给定H \text{ 是 }G\text{ 一个subgroup }, g_1, g_2 \in G，则下面的所有命题互相等价：
- g_1H = g_2H
- Hg_1^{-1} = Hg_2^{-1}
- g_1H \subset g_2 H
- g_2 \in g_1H
- g_1^{-1}g_2 \in H
我们选择几个来证明：
Proof 1 \implies 2: \forall g_1h \in g_1H, \exists h' \in H, g_1h = g_2h'. 我们对这个等式两边同时取逆, (g_1h)^{-1} = (g_2h')^{-1} \implies h^{-1}g_1^{-1} = h'^{-1}g_2^{-1}。根据group的性质，上面最后的式子，实际上意味着 \forall h^* \in H, h^*g_1^{-1} \in Hg_2^{-1}，这就是Hg_1^{-1} \subset Hg_2^{-1}。同理可以证明 Hg_2^{-1} \subset Hg_1^{-1} 。这就证明了2。
下面讨论一个重要的定理：H \text{是}G\text{的一个subgroup}，那么left cosets of H划分了G。
Proof: 先证明\forall g_1, g_2 \in G, g_1H \cap g_2H = \emptyset \lor g_1H = g_2H 。这个需要证明的命题，等价于\forall g_1,g_2 \in G, g_1H \cap g_2H \ne \emptyset \implies g_1H = g_2H。
g_1H \cap g_2H \ne \emptyset \implies \exists h, h' \in H, g_1 \circ h = g_2 \circ h' \implies g_1 \circ h \circ h'^{-1} = g_2 \implies g_2 = g_1 \circ (h \circ h') \implies g_2 \in g_1H。这时候根据上面互相等价的几个命题4 \iff 1，我们知道g_1H=g_2H。
因此给定H,G, H是G的subgroup，left cosets of H构成一系列等价类。等价类的数目，定义为Index of G \text{ in } H，记作[G:H]。这里的Index也可以用right cosets来定义，是一样的，证明略去。
拉格朗日定理
这是一个非常重要的定理，Lagrange’s Theorem。在此之前，先看一个引理： 给定一个group G, \circ，H是G的subgroup，给定g\in G，定义一个映射\phi: H \mapsto gH为\phi(h)=g\circ h。则H中元素数目和gH中元素数目一样多, \phi是一个双射。
引理证明：假设\phi(h_1) = \phi(h_2), h_1,h_2\in H，这意味着 \phi(h_1) = g \circ h_1 = \phi(h_2) = g \circ h_2 \implies h_1 = h_2，故而]\phi是单射。满射很显然。故而\phi是一个双射。那么引理也就得证了。
Lagrange’s Theorem: G,\circ是一个元素数目有限多的group，H是G的subgroup。则 |G| = [G:H] * |H| 。
拉格朗日定理的证明：只需要证明每一个left coset的元素数目都是|H|即可。这只需要用到我们刚刚的引理即可。
基于Lagrange’s Theorem还有一些引理和定理，有趣且重要：
- G是一个有限的
Group，并且g \in G。则g的order可以整除|G|。- 证明的办法是构造一个H=\langle g \rangle，然后利用Lagrange’s Theorem。
- 令g的
order是n，则g^n=\mathbf{1}_G - 则 \langle g \rangle = \{\mathbf{1}_G, g, g^2, g^3, \dots, g^{n-1}\}
- G是一个
Group且|G|=p是一个素数，那么G是一个cyclic group并且\forall g \in G, g \ne \mathbf{1}_G \implies G = \langle g \rangle- 利用上一条引理，1不是素数，所以\exists g \in G, g \ne \mathbf{1}_G。然后我们对所有这样的元素，\forall g \in G, g \ne \mathbf{1}_G, \langle g \rangle 是G的一个
subgroup，则\langle g \rangle整除|G|=p - \langle g \rangle 中至少存在两个元素g, \mathbf{1}_G，故而 | \langle g \rangle| = p
- 即 \langle g \rangle = G
- 利用上一条引理，1不是素数，所以\exists g \in G, g \ne \mathbf{1}_G。然后我们对所有这样的元素，\forall g \in G, g \ne \mathbf{1}_G, \langle g \rangle 是G的一个
欧拉定理
集合\{0,1,2,\dots,n-1\}里，有多少个数字是和n互素？欧拉定义里一个函数\phi来表示这个问题。并规定了\phi(1) = 1。显然，\forall p \text{ 是一个素数}, \phi(p) = p-1，以及\forall n \text{ 不是素数, } \phi(n) < n-1 。
回顾之前的the group of units of \mathbb{Z}_n的定义，有|U(n)| = \phi(n)。
欧拉定理：a,n\in\mathbb{Z}, n > 0, a \perp n, \text{ then } a^{\phi(n)} \equiv 1 (\bmod n)。根据有限群的性质和上面的引理，容易证明。
费马小定理
费马小定理就是欧拉定理的一个情况。即n是素数时候的U(n), \mathbb{Z}_n，这时候\phi(n) = n-1。
同态概念和案例
同态(Homomorphisms)定义为：有两个Group, (G, \cdot),(H, \circ)若映射\phi : G \mapsto H，满足如下性质，则称它是a Homomorphism between (G, \cdot), (H, \circ):
令G=\mathbf{GL}_2(\mathbb{R})。另一个Group是(\mathbb{R}, \circ = \times)即实数集合和乘法(对应的identity就是0)。那么行列式算子\text{det}就是一个G, \mathbb{R}之间的一个Homomorphism: \text{det}: G \mapsto \mathbb{R}, \forall A,B \in G, \text{det}(AB) = \text{det}(A) \times \text{det}(B)。
同态还具有下面的性质。\phi: G_1 \mapsto G_2是一个G_1,G_2之间的同态，那么：
- \mathbf{1}_{G_2} = \phi(\mathbf{1}_{G_1})
- \forall g \in G_1, \phi (g^{-1}) = [\phi(g)]^{-1}
- H_1 \text{ is a subgroup of } G_1 \implies \phi(H_1) \text{ is a subgroup of } G_2
- H_2 \text{ is a subgroup of } G_2 \implies \phi^{-1}(H_2) = \{g \in G_1 | \phi(g) \in H_2\} \text{ is a subgroup of } G_1
\phi: G \mapsto H是一个Homomorphism，则\phi^{-1}(\mathbf{1}_{H}) =\{g \in G | \phi(g) = \mathbf{1}_{H}\}称为kernel of \phi，记作: \text{ker } \phi，它是G的一个subgroup。
同构概念和案例
两个Group, (G,\bullet), (H, \circ)同构，需要满足：\exists \text{ a bijective map }\phi: G \mapsto H，使得\forall a,b \in G, \phi(a \bullet b) = \phi(a) \circ \phi(b)。这时候我们记作G\cong H，并且称 \phi 为一个isomorphism。
案例：(\mathbb{R},+)是实数集合上的加法作为二元操作符的群，(\mathbb{R}^{+}, *)是正实数集上的乘法作为二元操作符的群。构造一个一一映射\phi : \mathbb{R} \mapsto \mathbb{R}^{+}, \phi(x) = e^{x}。容易验证\forall x,y \in \mathbb{R}, \phi(x+y)=e^{x+y} =e^xe^y = \phi(x) \phi(y)。所以这两个群同构。
关于同构，我们研究下面的定理：G \cong H, \phi: G \mapsto H是这两个群的isomorphism。则下面的命题全部都是真的(证明略去)：
- \phi^{-1}: H \mapsto G也是一个
isomorphism - |G|=|H|
- G \text{是阿贝尔群} \implies H \text{是阿贝尔群}
- G\text{是cyclic的} \implies H\text{是cyclic的}
- G\text{存在order是}n\text{的subgroup} \implies H\text{存在order是}n\text{的subgroup}
继续看一些关于同构的定理。
定理: 任意的有无限多元素的cyclic group都和\mathbb{Z}同构。
证明：任意一个无限的cyclic group可以表示为\langle a \rangle，可以构造一个双射\phi: \mathbb{Z} \mapsto G, \phi (n) = a^n,\phi (m+n) = a^{(m+n)} = a^ma^n=\phi(m) \phi(n)。由于|a| = \infty ，容易验证\phi是双射。
定理: 任何cyclic group \langle a \rangle, |a| = n \implies \langle a \rangle \cong \mathbb{Z}_n。
证明：构造映射\phi: \mathbb{Z}_n \mapsto \langle a \rangle, \phi(k) = a^k, k \in [0,n) 。
- \forall x,y \in \mathbb{Z}_n, x + y \in [0, 2n-2]:
- 当x+y \in [0,n-1]时, \phi( (x+y) \mod n) =\phi(x+y) = a^{x+y} = a^x a^y = \phi(x) \phi(y)
- 当x+y \in [n, 2n-2]时, \phi((x+y)\mod n) = \phi(x+y-n) = \phi(x+y-n) \mathbf{1}_G = \phi (x+y-n) a^n = a^{x+y-n} a^n = a^{x+y} = a^xa^y = \phi(x) \phi(y)
- \phi是满射容易证明
- \forall x,y \in \mathbb{Z}_n, \phi(x) = \phi(y) \implies a^x=a^y \implies a^{x-y} = \mathbf{1}_G \implies x-y = 0 ，故而是单射。
引理：如果一个有限群G，元素个数p是素数，那么G \cong \mathbb{Z}_p。
Cayley定理: Every group is isomorphic to a group of permutations.
域的定义和案例
域, field，是一个集合\mathbb{F}，其至少含有两个元素，同时还有两个二元运算符：\oplus, \ast，同时满足下面的性质：
- \mathbb{F}, \oplus 构成一个阿贝尔群(对应的
identify是0) - 记集合\mathbb{F}^* = \mathbb{F} - \{0\}，即原来的集合去掉上述阿贝尔群里的
identity的集合，\mathbb{F}^*, \ast构成一个阿贝尔群(对应的identify是1) - 分配律： \forall a,b,c\in \mathbb{F}, (a \oplus b) \ast c = (a \ast c) \oplus (b \ast c)。
我们常见的 \mathbb{R}, \mathbb{C}, \mathbb{Q} 在加法和乘法下，都是field。
命题：\mathbb{F} \text{ 是一个 field, } \forall a \in \mathbb{F}, a \ast 0 = 0。
证明：只需要证明a \ast 0是\mathbb{F}, \oplus的identify即可。即证明\forall a,b \in \mathbb{F}, a \oplus (a \ast 0) = a \land (a \ast 0) \oplus a = a。(a \ast 0) \oplus a = (a \ast 0) \oplus (a \ast 1) = (1 \oplus 0) \ast a = 1 \ast a = a 。
素数域的定义和性质
定理：\forall p \text{ 是一个素数, } R_p = \{0, 1, 2, \dots, p-1\}构成一个field，\oplus = \lambda \ x\ y: (x + y) \mod p; \ \ \ \ast = \lambda \ x\ y: (xy) \mod p。
证明：先看它的R_p, \oplus，这就是 \mathbb{Z}_p，故而是一个阿贝尔群。由于\forall a \in R_p, a \perp p \implies \langle a \rangle = \mathbb{Z}_p。其中0是这个阿贝尔群的identify。
再看R_p^{\ast} = \{1,2,3,\dots, p-1\}, \ast。我们需要验证它是一个阿贝尔群，它就是U(p)是一个阿贝尔群，其中1是它的identify。
再看分配律：需要证明\forall a,b,c \in R_p, (a\oplus b)\ast c = (a\ast c) \oplus (b \ast c)，即 ((a+b)\mod p)c\mod p = ((ac\mod p) + (bc\mod p))\mod p ，即可 ((a+b)\mod p)c \equiv ((ac\mod p) + (bc\mod p)) (\bmod p)。
根据具体数学里的公式(3.23) c(x\mod y) = (cx) \mod (cy)。故而：
((a+b)\mod p)c = c(a+b) \mod cp = (ac+bc) \mod cp最后只需要证明 (ac+bc) \mod cp \equiv ((ac\mod p) + (bc\mod p)) (\bmod p) ：
(ac+bc) \mod cp - ((ac\mod p) + (bc\mod p)) = (ac+bc) - \lambda (cp) - (ac -\mu p + bc - \gamma p)= (\mu + \gamma - c\lambda)p，故而得证。
有限素数域只有一个参数，就是那个素数p，给定了它，我们记这个有限素数域是\mathbb{F}_p。
引入域的同构概念后，如果一个有限域有p个元素，且p是素数，则它和\mathbb{F}_p同构。
两个域\mathbb{F}\text{和}\mathbb{G}\text{同构} \iff \exists h: \mathbb{F} \mapsto \mathbb{G}, h \text{是双射}, \forall a,b \in \mathbb{F}, h(a\oplus b) = h(a) \oplus h(b) \land h(a\ast b) = h(a) \ast h(b)。
任何一个域\mathbb{F}，若它的元素个数是素数p的话，只看\oplus的group，根据之前的定理，知道 (\mathbb{F}, \oplus) \cong \mathbb{Z}_p 。我们记录\mathbf{0}是域\mathbb{F}_p的\oplus下的identity；\mathbf{1}是域\mathbb{F}_p的\oplus下的identity。那么(\mathbb{F}_p, \oplus)\text{的group}=\langle \mathbf{1} \rangle。
注意：当n不是素数的时候，\mathbb{Z}_n不是一个域。因为当n不是素数的时候，必定存在a,b\in \mathbb{Z}_n, ab=n，那么a\ast b = (ab) \mod n = 0，这就是\mathbb{Z}_m - \{\mathbf{0}\}对\ast不封闭了。
再注意: 存在元素数目不是素数的有限域。（需要重新定义加法和乘法）。
subfield的概念和subgroup概念类似。给定了一个field，元素选取这个域的元素的子集，然后用同样的\oplus, \ast只不过限定到子集上，这个子集如何还是一个field，那就称它为subfield。我们要证明一个重要定理：
(\mathbb{F}_q, \oplus)对应的identity是\mathbf{0}；(\mathbb{F}_q-\{\mathbf{0}\}, \ast)对应的identity是\mathbf{1}。考虑(\mathbb{F}_q, \oplus)的group(阿贝尔群)，它必定有一个cyclic subgroup \langle \mathbf{1} \rangle，假设n=|\langle \mathbf{1} \rangle|，可以知道 \langle \mathbf{1} \rangle \cong \mathbb{Z}_n 。
接着，根据分配律，\forall i,j \in \langle \mathbf{1} \rangle, i \ast j可以看成是\underbrace{\mathbf{1} \oplus \mathbf{1} \oplus \mathbf{1} ... \oplus \mathbf{1}}_{n \text{ 个 } \mathbf{1}}，根据cyclic模式，\underbrace{\mathbf{1} \oplus \mathbf{1} \oplus \mathbf{1} ... \oplus \mathbf{1}}_{n \text{ 个 } \mathbf{1}} \in \langle \mathbf{1}\rangle 。由于\mathbb{F}_q是一个field，那么\forall i,j \in \mathbb{F}_q, i\ast j \ne \mathbf{0}。故而由于同构，我们可以知道\forall i,j \ne 0 \in \mathbb{Z}_n, ij \mod n \ne n，唯一的可能就是n是素数。
上面的这个素数称为characteristic of \mathbb{F}_q。综上，我们可以给出素数子域的定理：
\text{The integers }\{\mathbf{1}, \mathbf{1}\oplus \mathbf{1}, \dots, \} = \langle \mathbf{1} \rangle of any finite field \mathbf{F}_q，forms a subfield \mathbb{F}_p \subset \mathbb{F}_q，and q is a prime called characteristic of \mathbb{F}_q。
Pingback: 环、域、多项式和有限域的构造 | Thoughts on Computing