【A-15-1】
讨论 【A-14】 中的例.
记 Z 为 整数的集合.
延用 【A-14】 的例. 对于给定的 正整数 6, 定义 [a]={k | k∈Z, k ≡ a (mod 6)}.
依据 Lemma 10 总共有 6 个模 6 的剩余类: [0], [1], [2], [3], [4], [5].
定义加法+ [a]+[b]=[a+b]. 定义乘法· [a]·[b]=[a·b].
记 R={[0], [1], [2], [3], [4], [5]}
注意到, 集合 R 连同 剩余类的加法+ 和 乘法· 构不成域(field).
最简单的解释是: 依据 Theorem 2, 如果有限域存在, 其阶数=p^n, 此处p为素数, n是正整数. 而这里的R 由 6 个元素组成, 不符合Theorem 2 的条件.
但是 集合 R 连同 剩余类的加法+ 和 乘法· 构成 环(ring). 环(ring)比域(field)条件弱: 域一定是环, 但环不一定是域 (待续).
(待续)

【A-15-2】
注意到, 在【A-14】 的例中, [3]·[4]=[0]. 于是, 非零元素相乘等于零元素.
在这种情况下, [3], [4] 都称为非零的零因子(nonzero zero divisor). 另外还有, [2]·[3]=[0]. 所以[2]也是非零的零因子.
由于域(field)的每一非零元素都有乘法逆元(multiplicative inverse), 所以域(field)不可能有非零的零因子(nonzero zero divisor).
这就从另一方面证明了: 集合 R 连同 剩余类的加法+ 和 乘法· 构不成域(field).
(待续)

【A-16-1】 用剩余类(residue class)构造素域(prime field)
依据 Theorem 2, 如果有限域存在, 其阶数=p^n, 此处p为素数, n是正整数.
当 n=1, GF(p^n) 特殊化为 GF(p). 依据 Theorem 3, GF(p) 是素域.
这里构造素域.
设 p 是任一素数. 依据 Lemma 10 总共有 p 个模 p 的剩余类: [0], [1], ... , [p-1].
记 F={[0], [1], ... ,[p-1]}
定义加法+ [a]+[b]=[a+b]. 定义乘法· [a]·[b]=[a·b].
(待续)

【A-16-2】
Theorem 4 对于给定的任一素数p. 上述集合 F 连同运算 加法＋ 和 乘法· 构成 p 阶有限域, 也就是 GF(p).
证: 这就是要验证 集合 F 连同两个运算 ＋ 和 · 满足 【A-1】 中的条件 (1), (2), (3), (4), (5), (6). 其中 (1), (2), (3), (4)容易验证.
以下验证条件 (5) 和 (6).
容易验证 [0]∈F 是加法单位元, [1]∈F 是 乘法单位元. 所以 F 连同两个运算 ＋ 和 · 满足 条件(5).
对于任一 r∈Z, 0 ≤ r ≤ p-1, [r]+[p-r]=[p]=[0]. 所以 [p-r]=-[r].
对于任一 r∈Z, 1 ≤ r ≤ p-1, 由于p 是素数, 则当 x 取遍 1, ... , p-1, [x·r] 不可能有重复, 也不可能取[0]. 因此[x·r]取遍 [1], ... , [p-1].
所以存在唯一的 s∈Z, 1 ≤ s ≤ p-1 使得 [s·r]=[1], 即 [s]·[r]=[1], 所以 [s]=[r]^{-1}. 于是, F 连同两个运算 ＋ 和 · 满足 条件(6).
(Theorem 4 证完)
(待续)

【A-17】 2阶域 GF(2)
记 Z 为 整数的集合.
按照 【A-5】, 定义 [a]={k | k∈Z, k ≡ a (mod 2)}.
依据 Lemma 10, 恰好有2个模2的剩余类: [0], [1].
记 F = {[0], [1]}. 依据 Theorem 4, F 连同加法+和乘法· 构成 GF(2).
以下是加法+运算表:
+ |[0][1]
---+------
[0]|[0][1]
[1]|[1][0]
以下是乘法·运算表:
· |[0][1]
---+------
[0]|[0][0]
[1]|[0][1]
素域 GF(2) 是元素最少的有限域.
(待续)

【A-18】 3阶域 GF(3)
记 Z 为 整数的集合.
按照 【A-5】, 定义 [a]={k | k∈Z, k ≡ a (mod 3)}.
依据 Lemma 10, 恰好有3个模3的剩余类: [0], [1], [2].
记 F = {[0], [1], [2]}. 依据 Theorem 4, F 连同加法+和乘法· 构成 GF(3).
以下是加法+运算表:
+ |[0][1][2]
---+---------
[0]|[0][1][2]
[1]|[1][2][0]
[2]|[2][0][1]
以下是乘法·运算表:
· |[0][1][2]
---+---------
[0]|[0][0][0]
[1]|[0][1][2]
[2]|[0][2][1]
依据 Theorem 3, GF(3)是素域
(待续)

【A-19】 5阶域 GF(5)
记 Z 为 整数的集合.
定义 [a]={k | k∈Z, k ≡ a (mod 5)}.
依据 Lemma 10, 恰好有5个模5的剩余类: [0], [1], [2], [3], [4].
记 F = {[0], [1], [2], [3], [4]}. 依据 Theorem 4, F 连同加法+和乘法· 构成 GF(5).
以下是加法+运算表:
+ |[0][1][2][3][4]
---+---------------
[0]|[0][1][2][3][4]
[1]|[1][2][3][4][0]
[2]|[2][3][4][0][1]
[3]|[3][4][0][1][2]
[4]|[4][0][1][2][3]
以下是乘法·运算表:
· |[0][1][2][3][4]
---+---------------
[0]|[0][0][0][0][0]
[1]|[0][1][2][3][4]
[2]|[0][2][4][1][3]
[3]|[0][3][1][4][2]
[4]|[0][4][3][2][1]
依据 Theorem 3, GF(5)是素域.
(待续)

【A-21-1】 以多项式为模的同余关系
根据 【A-5】 中的 Theorem 2, 如果存在有限域 F, 则 其阶数=p^n. 此处p为素数, n是正整数.
根据 【A-16-2】 中的 Theorem 4, 对于给定的任一素数p, 存在 p 阶有限域 GF(p). GF(p)称为素域.
以下推广Theorem 4, 最终证明: 对于给定的任一素数p和任意给定的正整数n, 存在p^n阶有限域GF(p^n).
用 GF(p)[X] 表示 GF(p)上的多项式的集合(即以GF(p)中的元素为系数的多项式的集合).
设 m(x) ∈ GF(p)[X] 是一个非零多项式.
设 f(x), g(x)∈ GF(p)[X]. 如果 f(x)-g(x) 能被m(x)整除, 记为 f(x) ≡ g(x) (mod m(x)). 称f(x)与g(x)关于模 m(x)同余 (f(x) is congruent to g(x) modulo m(x))
(待续)

【A-21-2】 以多项式为模的同余关系
Lemma 14 同余关系有如下性质:
(1) f(x) ≡ g(x) (mod m(x)) 当且仅当 g(x) ≡ f(x) (mod m(x)).
(2) 如果 f(x) ≡ g(x) (mod m(x)), g(x) ≡ h(x) (mod m(x)), 则 f(x) ≡ h(x) (mod m(x)).
(3) f(x) ≡ f(x) (mod m(x)).
(证法同 Lemma 8)
Lemma 15 如果 f(x) ≡ g(x) (mod m(x)), h(x) ≡ k(x) (mod m(x)) 则
(1) f(x)+h(x) ≡ g(x)+k(x) (mod m(x)).
(2) f(x)·h(x) ≡ g(x)·k(x) (mod m(x)).
(证法同 Lemma 11)
(待续)

【A-22-1】 以多项式为模的剩余类
取定 非零多项式 m(x) ∈ GF(p)[X]: m(x)=a_0 + a_1x + ··· + a_n^n, 此处x 为未定元(indeterminate), 每一个 a_j ∈ GF(p), a_n ≠ 0. 称 m(x)为n次多项式, 记为 deg(m)=n.
( deg(0)需要单独定义, 通常定义为 -∞)
记 [f]={g(x) | g(x) ∈ GF(p)[X], g(x) ≡ f(x) (mod m(x))}. 每一个 [f] 称作 模m(x)的一个剩余类(residue class modulo m(x)).
Lemma 16 [f_1]=[f_2] 当且仅当 f_1(x) ≡ f_2(x) (mod m(x)).
(证法同 Lemma 9)
(待续)

【A-22-2】 以多项式为模的剩余类
Lemma 17 对于给定的n(≥0)次多项式f(x) ∈ GF(p)[X], 存在 r(x) ∈ GF(p)[X], deg(r) < n 使得 [f]=[r].
证: 因为f(x) 能表为 f(x)=h(x)m(x)+r(x), 其中 h(x), r(x) ∈ GF(p)[X], deg(r) < n. 所以 f(x) ≡ r(x) (mod m(x)). 依据 Lemma 16, [f]=[r].
(Lemma 17 证完)
(待续)

【A-22-3】 以多项式为模的剩余类
对模m(x)的剩余类 定义加法+ [f]+[g]=[f+g], 定义乘法· [f]·[g]=[f·g].
Lemma 20 以上定义的两个运算与 [f], [g] 的代表元素 f, g 的选择无关.
(证法同 Lemma 13)
(待续)

【A-23-1】 用GF(p)上的n次不可约多项式构造p^n阶有限域GF(p^n)
已知 GF(p)上的不可约多项式ρ(x), deg(ρ)=n(>1).
用 F 表示 p^n 个模ρ(x)的剩余类的集合. 由 Lemma 19, F={[r(x)] | r(x) ∈ GF(p)[X], deg(r) < n}.
以下证明 F 连同【A-22-3】定义的两个运算 ＋ 和 · 构成 p^n阶有限域, 即 GF(p^n). 这就是要验证 F 连同【A-22-3】定义的两个运算 ＋ 和 · 满足 【A-1】 中的条件 (1), (2), (3), (4), (5), (6).
其中条件 (1), (2), (3), (4) 容易验证. 用 0 表示 GF(p) 加法单位元, 则[0]就是 F 的加法单位元. 用 1 表示 GF(p) 乘法单位元, 则[1]就是 F 的乘法单位元. 于是, 条件(5)得以验证. 为了验证条件(6), 需要以下予备结果.
Lemma 21 设 f_1(x), f_2(x) ∈ GF(p)[X], 而且 [f_1]≠[0], [f_2]≠[0]. 则 [f_1]·[f_2]≠[0].
证: 用反证法(proof by contradiction). 假设[f_1]·[f_2]=[0]. 根据 Lemma 17, 存在 r_ 1(x), r_2(x) ∈ GF(p)[X], deg(r_1)< n, deg(r_2) < n, 使得 [f_1]=[r_1], [f_2]=[r_2].
由于 [f_1]·[f_2]=[0], 所以 [r_1]·[r_2]=[0], [r_1·r_2]=[0], 所以 r_1(x)·r_2(x) 能被ρ(x)整除. 由于 ρ(x) 是 GF(p)上的不可约多项式, 所以ρ(x) 整除 r_1(x) 或整除 r_2(x). 注意到r_1(x), r_2(x)均为非零多项式, 并且 deg(r_1)<n, deg(r_2)< n 但是 deg(ρ)=n, 所以 ρ(x)不可能整除 r_1(x), 也不可能整除r_2(x). 这是一个矛盾. 矛盾证明了假设[f_1]·[f_2]=[0]是错的. lemma 得证.
(Lemma 21 证完)
(待续)

【A-23-2】 用GF(p)上的n次不可约多项式构造p^n阶有限域GF(p^n)
Lemma 22 设 f(x) ∈ GF(p)[X], 而且 [f] ≠ [0]. 令 [h] 取遍 p^n 个模ρ(x)的剩余类F, 则 [f]·[h] 取遍取遍 p^n 个模ρ(x)的剩余类F.
证: 如果 [h_1] ≠ [h_2], 即 [h_1]-[h_2]=[h_1-h_2] ≠ [0]. 根据 Lemma 21, [f]·[h_1-h_2] ≠ [0], 即 [f]·[h_1] ≠ [f]·[h_2]. 所以, 当 [h] 取遍 p^n 个模ρ(x)的剩余类F, 则 [f]·[h] 不可能有重复, 因此 当[h] 取遍 p^n 个模ρ(x)的剩余类, [f]·[h] 取遍 p^n 个模ρ(x)的剩余类F.
(Lemma 22 证完)

【A-23-3】 用GF(p)上的n次不可约多项式构造p^n阶有限域GF(p^n)
容易验证p^n 个模ρ(x)的剩余类F满足【A-1】 的条件(6)中 与加法 ＋ 有关的内容. 现在验证条件(6)中 与乘法 · 有关的内容. 设 f ∈ GF(p)[X], 而且 [f] ≠ 0. 根据 Lemma 22, 令[h] 取遍 p^n 个模ρ(x)的剩余类F, 则 [f]·[h] 取遍取遍 p^n 个模ρ(x)的剩余类F. 特别的, 存在 唯一的一个模ρ(x)的剩余类 [h_1] 使得 [f]·[h_1] = [1]. 于是 [h_1]=[f]^(-1), 条件(6)的乘法部分得到验证.
综合起来, p^n 个模ρ(x)的剩余类的集合 F 连同【A-22-3】定义的两个运算 ＋ 和 · 符合 【A-1】 中的条件 (1), (2), (3), (4), (5), (6), 所以是一个p^n阶有限域.
(待续)