【A-1】 域(field)的概念.
域(field) 是一个集合 F (至少含有2个元素) 连同其上两个运算: 加法(addition)＋ 和乘法(multiplication)· 满足:
(1) 对于任意 a, b ∈ F, 都有 a+b ∈ F,
对于任意 a, b ∈ F, 都有 a·b ∈ F.
(2) 加法交換律(commutativity of addition): 对于任意 a, b ∈ F, 都有 a+b = b+a,
乘法交換律(commutativity of multiplication): 对于任意 a, b ∈ F, a·b=b·a.
(3) 对于任意 a, b, c ∈ F, 都有 a+(b+c) = (a+b)+c ,
对于任意 a, b, c ∈ F, 都有 a·(b·c)=(a·b)·c.
(4) 对于任意 a, b, c ∈ F, 都有 a·(b+c) = (a·b)+(a·c).
(5) 存在加法单位元(additive identity element) 0 使得 对于任意 a ∈ F, 都有 a+0=a.
存在乘法单位元(multiplicative identity element) 1 使得对于任意 a ∈ F 都有 a·1=a.
(6) 对于任意 a ∈ F, 都有 -a ∈ F, 使得 a+(-a)=0. -a称为a的加法逆元(additive inverse).
对于任意 a ∈ F, a ≠ 0, 都有 a^(-1) ∈ F, 使得 a·a^(-1)=1. a^(-1)称为a的乘法逆元(multiplicative inverse).
在域F中, 由于对于任意 a ∈ F, 都有 -a ∈ F, 所以不需要另行定义减法. 在域F中, 由于对于任意 a ∈ F, a ≠ 0, 都有 a^(-1) ∈ F, 所以不需要另行定义除法.
设 F 是上述定义中的域, K 是 F的一个子集. 如果 K 也符合上述定义, 则称 K 为 F 的子域(subfield).
设 F 是一个域. 如果 F 的子域(subfield)只能是 F 本身, 称 F 为 素域(prime field).
(待续)

【A-2-1】 域(field)的例子.
例1 (无限多个元素的域)
有理数(rational numbers)的集合 Q 连同有理数的加法, 乘法, 构成域.
实数(real numbers)的集合 R 连同实数的加法, 乘法, 构成域.
集合 K={a+b√5 | a, b ∈ Q} 连同实数的加法, 乘法, 构成域.
Q是K的子域(subfield), K是R的子域(subfield). Q是素域(prime field)
(待续)

【A-2-2】 域(field)的例子.
例2 (有限多个元素的域)
F={0, 1, a, b} 连同其上两个运算: 加法 ＋ 和乘法 · 构成 4 阶域.
其中 ＋ 和 · 的实施由下表给出:
+ | 0 1 a b
--+--------
0 | 0 1 a b
1 | 1 0 b a
a | a b 0 1
b | b a 1 0
· | 0 1 a b
--+--------
0 | 0 0 0 0
1 | 0 1 a b
a | 0 a b 1
b | 0 b 1 a
上面的是加法表, 下面的是乘法表.
F的子集 K={0, 1} 连同这样的 加法 ＋ 和乘法 · 构成 2 阶域.
K是F的子域(subfield). K是素域(prime field)
(4 阶域构造原理 - 待续)
(待续)

【A-3-2】 有限域(finite field or Galois field)的概念
Lemma 2 有限域 的特征(characteristic)必为素数.
证: 设 有限域F 的特征 为p . 以下用反证法(proof by contradiction)证明: p是素数. 假设相反: 则 p=st, 此处 s,t 是正整数 而且 1＜s＜p, 1＜t＜p.
此处用e代表K的乘法单位元(multiplicative identity element). 由于 pe=0 所以 ste=0, 所以 (se)·(te)=0.
所以必有 se=0 或 te=0. 但是 se=0 与 特征(characteristic)的定意义矛盾. 所以 se ≠ 0. 同理 te ≠ 0. 由于 F 是域, 所以 (se)·(te)≠ 0
这就与 (se)·(te)=0 矛盾. 矛盾证明了"假设相反"是错的. 所以 p是素数.
(Lemma 2 证完)
Lemma 3 设 有限域F 的特征 为p. 则 对于任意 a ∈ F 都有pa=0.
证: 此处用e代表F的乘法单位元(multiplicative identity element). 由于 pe=0. 对于任意的 a ∈ F, 等式 pe=0 两端同乘 a, 得到 pa=0.
(Lemma 3 证完)
(待续)

【A-4-1】 素域(prime field)的性质
Lemma 4 设F为有限域, 其特征(characteristic) 为 p. 此处用e代表F的乘法单位元(multiplicative identity element). 记 L={0, e, 2e, ..., (p-1)e}. 则 L是F的子域.
证: 由于 F 的特征(characteristic) 为 p, 所以 pe=0. 注意到, 任意整数n 可表为: n=tp+r, 此处 t, r 是整数 而且 0≤r≤p-1.
于是, 对于任意整数n, 都有整数r, 0≤r≤p-1 使得 ne=re. 以下证明 集合L连同两个运算 ＋ 和 · 构成p阶有限域. 【A-1】 中的条件其中 (1), (2), (3), (4), (5) 容易验证. 以下验证(6).
对于任一整数 r, 0 ≤ r ≤ p-1, re+(p-r)e=pe=0. 所以 (p-r)e=-re. 对于任一 整数 r, 1 ≤ r ≤ p-1, 由于p 是素数, 则当 i 取遍 1, ... , p-1, (ie)·(re)=ire 不可能有重复, 因此取遍 e, 2e, ..., (p-1)e.
所以存在唯一的整数 s, 1 ≤ s ≤ p-1 使得 (se)·(re)=sre=e, 所以 se=(re)^(-1). 于是, L 连同连同F中的两个运算 ＋ 和 · 满足 (6). 这就证明了集合L连同F中的两个运算＋ 和 · 构成p阶有限域. 所以 L是F的子域.
(Lemma 4 证完)
(待续)

【A-4-2】 素域(prime field)的性质
Lemma 5 如果 F 是素域, 则 F 的阶数等于其特征(characteristic).
证: 设F的特征(characteristic) 为 p. 此处用e代表F的乘法单位元(multiplicative identity element). 记 L={0, e, 2e, ..., (p-1)e}. 据 Lemma 4, L是F的子域. 由于 F 是素域, 所以, L就是F, 所以 F 的阶数等于 p.
(Lemma 5 证完)
以下是 Lemma 5 的逆 (converse):
Lemma 6 设F为有限域. 如果 F 的阶数等于其特征(characteristic), 则 K 是素域.
证: 设F的特征(characteristic) 为 p. K为 F的子域. 此处用e代表K的乘法单位元(multiplicative identity element). 记 L={0, e, 2e, ..., (p-1)e}. 据 Lemma 4, L是F的子域. 由于 e ∈ K, 显然L 也是K的子域.
综合上述, L ⊆ K ⊆ F. 由于 F 的阶数等于其特征(characteristic) p, 所以 L就是F, 所以 K就是F. 就证明了 K 是素域.
(Lemma 6 证完)
综合 Lemma 5 和 Lemma 6, 得到
Theorem 1 设F为有限域. 则 F 是素域 当且仅当 F 的阶数等于其特征(characteristic).
(待续)

【A-6】 素域(prime field)更多的性质
Corollary 1 设F为有限域. 如果 F 的阶数是素数, 则 F 是 素域.
证: 回顾 Theorem 2 的证明. 由于 已知: F 的阶数是素数, 所以 n=1, 所以 F 就是 K (n, K 出现在 Theorem 2 的证明), 所以 F 是 素域.
(Corollary 1 证完)
以下是 Corollary 1 的逆 (converse):
Lemma 7 如果 F是 素域, 则 F 的阶数是素数.
证: 依据 Lemma 5, 素域 F 的阶数等于其特征(characteristic). 依据 Lemma 2, F 的特征(characteristic)必为素数. 所以 F 的阶数是素数.
(Lemma 7 证完)
综合 Corollary 1 和 Lemma 7, 得到
Theorem 3 设F为有限域. 则 F 是素域 当且仅当 F 的阶数是素数.
(待续)

【A-8-1】 最简单的同余关系(congruence relation)
记 Z 为 整数的集合.
设a, b 为整数. 如果a-b 是 正整数 m 的整数倍, 记为 a ≡ b (mod m). 称a与b关于模 m 同余(congruent modulo m).
例如: 13 ≡ 4 (mod 3), -5 ≡ 17 (mod 11), 23 ≡ 62 (mod 13), 36 ≡ 0 (mod 12), 9 ≡ 9 (mod 5)
(待续)

【A-9-2】 剩余类(residue class)
记 Z 为 整数的集合.
Lemma 10 对于给定的正整数m, 总共有 m 个模 m 的剩余类: [0], [1], ... , [m-1].
证: 只需证明: 对于任一 n∈Z, 都有 r∈Z, 0 ≤ r ≤ m-1 使得 [n]=[r].
这是因为任一n∈Z 都能唯一的表为 n=sm+r, 其中 s∈Z, r∈Z, 0 ≤ r ≤ m-1. 所以 n ≡ r (mod m). 依据 Lemma 9, [n]=[r].
(Lemma 10 证完)
(待续)

【A-10】 同余关系(congruence relation) 更多的性质
记 Z 为 整数的集合.
Lemma 11 如果 a ≡ b (mod m), c ≡ d (mod m) 则
(1) a+c ≡ b+d (mod m).
(2) ac ≡ bd (mod m).
证: (1) 由已知条件, 存在 s∈Z 使得 a-b=sm, 存在 t∈Z 使得 c-d=tm. 所以 (a+c)-(b+d)=(s+t)m, 所以 a+c ≡ b+d (mod m).
(2) 由于 a=b+sm, c=d+tm. 这两个等式左右相乘, 得 ac=bd+(bt+ds+stm)m, 即 ac-bd=(bt+ds+stm)m. 所以 ac ≡ bd (mod m).
(Lemma 11 证完)
(待续)

【A-14-1】 剩余类(residue class)的加法和乘法的一个具体的例子
记 Z 为 整数的集合.
例 1 延用 【A-12】 中的例. 对于给定的 正整数 6, 定义 [a]={k | k∈Z, k ≡ a (mod 6)}.
依据 Lemma 10, 总共有 6 个模 6 的剩余类: [0], [1], [2], [3], [4], [5].
(待续)

【A-14-2】
按定义,
[2]+[3]=[2+3]=[5].
[2]+[4]=[2+4]=[6], 由于 6 ≡ 0 (mod 6), 依据 Lemma 9, [6]=[0], 所以 [2]+[4]=[0]
[4]+[5]=[4+5]=[9], 由于 9 ≡ 3 (mod 6), 依据 Lemma 9, [9]=[3], 所以 [4]+[5]=[3]
类似的, 可以计算更多的结果, 列表如下.
以下是加法+运算表:
+ |[0][1][2][3][4][5]
---+------------------
[0]|[0][1][2][3][4][5]
[1]|[1][2][3][4][5][0]
[2]|[2][3][4][5][0][1]
[3]|[3][4][5][0][1][2]
[4]|[4][5][0][1][2][3]
[5]|[5][0][1][2][3][4]
(待续)

【A-14-3】
按定义,
[2]·[2]=[2·2]=[4].
[3]·[4]=[3·4]=[12]. 由于 12 ≡ 0 (mod 6), 依据 Lemma 9, [12]=[0], 所以 [3]·[4]=[0]
[4]·[5]=[4·5]=[20]. 由于 20 ≡ 2 (mod 6), 依据 Lemma 9, [20]=[2], 所以 [4]·[5]=[2]
类似的, 可以计算更多的结果, 列表如下.
以下是乘法·运算表:
· |[0][1][2][3][4][5]
---+------------------
[0]|[0][0][0][0][0][0]
[1]|[0][1][2][3][4][5]
[2]|[0][2][4][0][2][4]
[3]|[0][3][0][3][0][3]
[4]|[0][4][2][0][4][2]
[5]|[0][5][4][3][2][1]
(待续)