Finite Fields

回顧一下所謂 F 是一個 finite field 就是說 F 是一個 field 且 F 的元素個數 (通常我們用 $\left\vert\vphantom{ F}\right.$ F $\left.\vphantom{ F}\right\vert$ 來表示) 是有限多個. 由這個定義我們馬上知若 F 是 finite field, 則 F 的 characteristic 一定是一個質數 p (Lemma 9.2.3). 當初我們定 characteristic 是利用一個 ring homomorphism $\phi$ : $\mathbb {Z}$ $\to$ F, 其中對任意 n $\in$ $\mathbb {N}$ 我們定 $\phi$ (n) = n1, 而 $\phi$ (- n) = n(- 1). F 的 characteristic 是 p 表示 ker( $\phi$ ) = $\bigl($ p $\bigr)$ . 因此由 ring 的 1st Isomorphism Theorem 我們知 $\mathbb {Z}$ / $\bigl($ p $\bigr)$ $\simeq$ im( $\phi$ ) $\subseteq$ F. 別忘了 p 是質數, 故知 $\bigl($ p $\bigr)$ 會是 $\mathbb {Z}$ 的一個 maximal ideal, 因此 $\mathbb {Z}$ / $\bigl($ p $\bigr)$ 是一個 field. 又因 $\left\vert\vphantom{\mathbb{Z}/\bigl({p}\bigr)}\right.$ $\mathbb {Z}$ / $\bigl($ p $\bigr)$ $\left.\vphantom{\mathbb{Z}/\bigl({p}\bigr)}\right\vert$ = p, 我們得 F 中存在一個 subfield 和 $\mathbb {Z}$ / $\bigl($ p $\bigr)$ 這個 p 個元素的 finite field 是 isomorphic 的. 為了方便我們將這個 p 個元素的 finite field 記為: $\mathbb {F}$ _p.

既然 F 是 $\mathbb {F}$ _p 的一個 extension, 我們當然就可以把 F 看成是一個 vector space over $\mathbb {F}$ _p. 那麼 F 會不會是 finite dimensional over $\mathbb {F}$ _p 呢? 大家可能都會猜想會, 但是怎麼證呢? 一般來說我們要證明一個 vector space V 是 finite dimensional over 一個 field K, 我們只要證明 V 中可以找到有限多個元素 span V over K. 畢b由於 F 是 finite field, 就假設 $\left\vert\vphantom{ F}\right.$ F $\left.\vphantom{ F}\right\vert$ = n 吧, 那麼 F 中所有的元素當然 span F over $\mathbb {F}$ _p 了 (因為每個 a $\in$ F 都可以看成是 a = 1^.a). 所以由 Lemma 9.3.4 (1) 知 dim_{_p}(F) $\le$ n. 當然我們這個估計的 dimension 是非常粗略, 不過我們目前的目的只是要知道 F 是 $\mathbb {F}$ _p 的一個 finite extension. 綜合以上的結果我們可以得到以下 finite field 第一個重要的性質.

証明. 我們前面已知 F 中存在一個 subfield $\mathbb {F}$ _p 滿足 $\mathbb {F}$ _p $\simeq$ $\mathbb {Z}$ / $\bigl($ p $\bigr)$ , 而且 F 是 $\mathbb {F}$ _p 的 finite extension. 所以我們僅剩下要證: 若 [F : $\mathbb {F}$ _p] = k, 則 $\left\vert\vphantom{ F}\right.$ F $\left.\vphantom{ F}\right\vert$ = p^k.

這完全是一個線性代數的問題. 由 dim_{_p}(F) = [F : $\mathbb {F}$ _p] = k 的假設知存在 a₁,..., a_k $\in$ F 是一組 F over $\mathbb {F}$ _p 的 basis. 由 basis 的定義知對任意的 $\alpha$ $\in$ F, 存在一組唯一的 c₁,..., c_k $\in$ $\mathbb {F}$ _p 使得 $\alpha$ = c₁^.a₁ + ^... + c_k^.a_k. (這裡的存在是因為 a₁,..., a_k span F over $\mathbb {F}$ _p, 而唯一是因為 a₁,..., a_k 是 linearly independent over $\mathbb {F}$ _p.) 注意這裡的 a₁,..., a_k 是固定的一組 basis, 而 c₁,..., c_k $\in$ $\mathbb {F}$ _p 會隨著 $\alpha$ $\in$ F 的改變而改變. 換言之 F 中的任一個元素都由唯一的一組 c₁,^..., c_k 所決定. 但由於這些 c_i 皆在 $\mathbb {F}$ _p 中而 $\left\vert\vphantom{\mathbb{F}_p}\right.$ $\mathbb {F}$ _p $\left.\vphantom{\mathbb{F}_p}\right\vert$ = p, 因此對每個 i $\in$ {1,..., k}, c_i 都有 p 個選擇, 故知這些 c₁,..., c_k 共有 p^k 個選擇. 也就是說 F 中共有 p^k 個元素. $\qedsymbol$

Theorem 10.4.1 簡單來說就是告訴我們每一個 finite field 其元素的個數應該是 p^k 個這種形式. 所以不可能有 finite field 有 6 個元素; 不過 Theorem 10.4.1 也沒有告訴我們到底有沒有 finite field 有 9 個元素或 16 個元素等等. 馬上我們就要回答這個問題, 不過在此之前我們先談談 finite field 的乘法結構.

假設 F 是一個 finite field, 因為 F 是 field, 由 Corollary 9.1.2 知 F^* = F $\setminus$ {0} 在乘法之下是一個 abelian group. 又因為 F 只有有限個元素, 所以我們知道 F^* 是一個 finite abelian group. 既然 F^* 是一個 finite group, 利用 Lagrange's Theorem 我們有以下之結果.

証明. 首先我們考� F^* 這個 order 為 p^k - 1 的 finite group. 利用 Lagrange's Theorem (Corollary 2.3.4), 我們知對任意 a $\in$ F^*, 皆有 a^{p^k - 1} = 1 (注意 1 是 F^* 的 identity). 等式兩邊乘上 a 得 a^{p^k} = a, 故知 f (a) = 0. 另� 當 a = 0 時自然有 f (a) = 0, 所以我們得到對任意的 a $\in$ F 皆符合 f (a) = 0. 然而由 Theorem 10.3.3 我們知道 f (x) 在 F 中最多只能有 deg(f (x)) = p^k 個根. 所以 F 中的元素剛好就是 f (x) 所有的根. 因此 f (x) 可以完全分解成

f (x) = $\displaystyle \prod_{a\in F}^{}$ (x - a),

也就是說 f (x) splits linear factors in F. $\qedsymbol$

要注意 Lagrange's Theorem 是對一般的 finite group 都對的, 所以 Proposition 10.4.2 並沒有用到 F^* 是 abelian 的性質. 接下來我們要用到 finite abelian group 的重要性質來證明事實上 F^* 是一個 cyclic group. 回顧一下 finite abelian group 的 fundamental theorem (Theorem 3.3.11) 是說任意的 finite abelian group 都可寫成一些 cyclic groups 的 direct product. 另� 要注意的是若 C_n 表示是一個 cyclic group of order n, 則 C_n×C_m 不見得會 isomorphic to C_nm, 除非 n 和 m 是互質的 (Proposition 3.2.2).

証明. 由 Theorem 3.3.11 知存在 n₁,..., n_r $\in$ $\mathbb {N}$ 使得

F^* $\displaystyle \simeq$ C_n₁×^...×C_{n_r},

其中 C_{n_i} 是一個 cyclic group of order n_i. 若我們能證明這些 n_i 都是兩兩互質的, 則重複運用 Proposition 3.2.2 可得

C_n₁×^...×C_{n_r} $\displaystyle \simeq$ C_{n₁^...n_r},

換言之 F^* 是 cyclic group.

我們利用反證法, 為了方便就假設 n₁ 和 n₂ 不互質好了 (其他的狀況都是用相同的證明). 這表示存在一質數 q 是 n₁ 和 n₂ 的公因數. 因為 q | n₁ 且 q 是質數, Cauchy's 定理 (Theorem 3.3.2 或 Theorem 4.2.1) 告訴我們存在 a $\in$ C_n₁ 滿足 ord(a) = q. 也就是說 a, a²,..., a^{q - 1}, a^q = e₁ 是 C_n₁ 中 q 個相異的元素 (這裡我們用 e_i 來表示 C_{n_i} 的 identity). 同理我們知在 C_n₂ 中存在 b $\in$ C_n₂ 滿足 ord(b) = q. 畢瓞

$\displaystyle \alpha$ = (a, e₂,..., e_r), $\displaystyle \beta$ = (e₁, b,..., e_r) $\displaystyle \in$ C_n₁×C_n₂×^...×C_{n_r}.

當 i, j $\in$ {1,..., q} 且 i $\ne$ j 時, 我們知

$\displaystyle \alpha^{i}_{}$ = (aⁱ, e₂,..., e_r) and $\displaystyle \alpha^{j}_{}$ = (a^j, e₂,..., e_r),

故由於 aⁱ $\ne$ a^j, 我們知 $\alpha^{i}_{}$ $\ne$ $\alpha^{j}_{}$ . 同理 $\beta^{i}_{}$ $\ne$ $\beta^{j}_{}$ . 另� 對任意的 i, j $\in$ {1,..., q - 1}, 由於 aⁱ $\ne$ e₁ 且 b^j $\ne$ e₂, 我們也知

$\displaystyle \alpha^{i}_{}$ = (aⁱ, e₂,..., e_r) $\displaystyle \ne$ (e₁, b^j,..., e_r) = $\displaystyle \beta^{j}_{}$ .

換句話說

$\displaystyle \alpha$ , $\displaystyle \alpha^{2}_{}$ ,..., $\displaystyle \alpha^{q-1}_{}$ , $\displaystyle \beta$ , $\displaystyle \beta^{2}_{}$ ,..., $\displaystyle \beta^{q-1}_{}$

以及

$\displaystyle \alpha^{q}_{}$ = $\displaystyle \beta^{q}_{}$ = (e₁, e₂,..., e_r)

是 C_n₁×^...×C_{n_r} 中相異的 2q - 1 個元素. 由於 a^q = e₁ 且 b^q = e₂, 這 2q - 1 個元素 $\alpha^{i}_{}$ 以及 $\beta^{j}_{}$ 都符合

( $\displaystyle \alpha^{i}_{}$ )^q = ( $\displaystyle \beta^{j}_{}$ )^q = (e₁, e₂,..., e_r).

(10.2)

別忘了 (e₁,..., e_r) 是 C_n₁×^...×C_{n_r} 中的 identity, 所以 C_n₁×^...×C_{n_r} 和 F^* 間的 isomorphism 會將 (e₁,..., e_r) 送到 F^* 的 identity 1. 而且這個 isomorphism (因為是一對一) 也會將 $\alpha^{i}_{}$ 和 $\beta^{j}_{}$ 這 2q - 1 個相異的元素送到 F^* 中 2q - 1 個相異的元素. 由式子 (10.2) 我們知這 2q - 1 個 F^* 中的元素都符合 x^q - 1 = 0. 但是 Theorem 10.3.3 告訴我們 x^q - 1 在 F 中至多只能有 q 個根, 因此得到矛盾. 也就是說 F^* $\simeq$ C_n₁×^...×C_{n_r} 中的 n₁,..., n_r 都兩兩互質, 故得證 F^* 是一個 cyclic group. $\qedsymbol$

F^* 是 cyclic 表示存在 a $\in$ F^* 使得所有 F^* 中的元素都是 aⁱ 這種形式, 所以我們有以下這個重要的性質.

証明. 令 a $\in$ F^* $\subseteq$ F 產生 F^* 這一個 cyclic group. 回顧一下 $\mathbb {F}$ _p(a) 是 F 中包含 a 和 $\mathbb {F}$ _p 最小的 filed, 因此我們自然有 $\mathbb {F}$ _p(a) $\subseteq$ F. 另一方面任取 b $\in$ F, 如果 b = 0, 則自然 b $\in$ $\mathbb {F}$ _p(a); 如果 b $\ne$ 0, 表示 b $\in$ F^*, 故存在 i $\in$ $\mathbb {N}$ 使得 b = aⁱ. 由於 $\mathbb {F}$ _p(a) 是一個 field, 故此時 b = aⁱ $\in$ $\mathbb {F}$ _p(a). 因此證得 F $\subseteq$ $\mathbb {F}$ _p(a), 故知 F = $\mathbb {F}$ _p(a).

由於已知 $\left\vert\vphantom{ F}\right.$ F $\left.\vphantom{ F}\right\vert$ = p^k, 故利用 Theorem 10.4.1 知 [ $\mathbb {F}$ _p(a) : $\mathbb {F}$ _p] = [F : $\mathbb {F}$ _p] = k. 因此由 Corollary 10.1.7 知 a over $\mathbb {F}$ _p 的 minimal polynomial 的 degree 為 k, 故由定義知 a over $\mathbb {F}$ _p 的 degree 為 k. $\qedsymbol$

接下來我們要證 finite field 的存在性, 即給定任一質數 p 以及 k $\in$ $\mathbb {N}$ , 我們要找到一個 finite field F 其元素個數剛好是 p^k. 首先注意當 k = 1 時 $\mathbb {Z}$ / $\bigl($ p $\bigr)$ 就是一個元素個數為 p 的 finite filed, 為了方便我們將此 filed 記為 $\mathbb {F}$ _p. Theorem 10.4.1 告訴我們一個元素個數為 p^k 的 finite filed F 若存在, 則 F 一定會是 $\mathbb {F}$ _p 的一個 extension. 另� Proposition 10.4.2 告訴我們在此情形 x^{p^k} - x 在 F 中必定 splits into linear factors. 因此要尋找 F 必須從這兩個觀點出發.

証明. 考� x^{p^k} - x $\in$ $\mathbb {F}$ _p[x], Theorem 10.3.6 告訴我們存在一個 filed L 是 $\mathbb {F}$ _p 的一個 finite extension 使得 x^{p^k} - x 在 L 中 splits into linear factors. 畢b考�

F = {a $\displaystyle \in$ L | a^{p^k} = a},

也就是說 F 是 L 中 x^{p^k} - x 所有的根所成的集合.

我們首先證明 F 是一個 filed. 利用 Lemma 9.1.4, 我們只要檢查對任意 a, b $\in$ F 且 b $\ne$ 0 皆有 a - b $\in$ F 以及 a/b $\in$ F 即可. a - b 以及 a/b 當然都是 L 的元素, 再加上由 Lemma 9.2.5 我們有

(a - b)^{p^k} = a^{p^k} - b^{p^k} and (a/b)^{p^k} = a^{p^k}/b^{p^k},

故因 a, b $\in$ F (即 a^{p^k} = a 且 b^{p^k} = b) 得知 (a - b)^{p^k} = a - b 以及 (a/b)^{p^k} = a/b. 也就是說 a - b 以及 a/b 都是 F 的元素.

接下來要證明 $\left\vert\vphantom{ F}\right.$ F $\left.\vphantom{ F}\right\vert$ = p^k. 要注意由假設 x^{p^k} - x splits into linear factors in L, 我們只能知 F 的元素個數至多有 p^k 個, 除非能證得 x^{p^k} - x 沒有重根. 要證明 x^{p^k} - x 沒有重根, 我們先任取 a $\in$ L 是 x^{p^k} - x 的一個根, 由 Lemma 10.3.1 知存在 h(x) $\in$ L[x] 使得 x^{p^k} - x = (x - a)^.h(x). 若得 h(a) $\ne$ 0, 則知 a 不是重根. 然而利用 Lemma 9.2.6, 我們知道 (x - a)^{p^k} - (x - a) = x^{p^k} - a^{p^k} - x + a. 由於 a^{p^k} = a (因假設 a 是 x^{p^k} - x 的一個根), 故得

x^{p^k} - x = (x - a)^{p^k} - (x - a) = (x - a)^.h(x),

其中 h(x) = (x - a)^{p^k - 1} - 1. 因為 h(a) = - 1 $\ne$ 0, 故知任意 x^{p^k} - x 的根都不是重根. 因此得證 F 是一個有 p^k 個元素的 finite field. $\qedsymbol$

利用 finite field 的存在性以及Corollary 10.4.4, 我們馬上有以下的應用.

接下來我們來看在 $\mathbb {F}$ _p[x] 中的 irreducible element 的特性.

証明. 由於 deg(g(x)) = k, 利用 Theorem 10.3.4 知存在一個 $\mathbb {F}$ _p 的 extension L 滿足 [L : $\mathbb {F}$ _p] = k 且 a $\in$ L 滿足 g(a) = 0. 換言之, L 是一個 finite field 且 $\left\vert\vphantom{ L}\right.$ L $\left.\vphantom{ L}\right\vert$ = p^k. 然而 Proposition 10.4.2 告訴我們 L 中的元素都會是 f (x) = x^{p^k} - x 的根, 因此由 a $\in$ L 知 f (a) = 0. 要注意事實上 g(x) 會和 a over $\mathbb {F}$ _p 的 minimal polynomial h(x) associates. 這是因為 g(a) = 0 故利用 Lemma 10.1.1 (1) 知 h(x) | g(x), 但 g(x) 又假設是 irreducible, 故得 h(x) 和 g(x) associates (注意 h(x) 不可能是 unit). 又由於 f (a) = 0, 再利用一次 Lemma 10.1.1 (1) 知 h(x) | f (x) (即 f (x) $\in$ $\bigl($ h(x) $\bigr)$ ). 故由 g(x) 和 h(x) associates 知 $\bigl($ g(x) $\bigr)$ = $\bigl($ h(x) $\bigr)$ , 因此得證 f (x) $\in$ $\bigl($ g(x) $\bigr)$ 即 g(x) | f (x). $\qedsymbol$

最後我們來看有關 finite field 的唯一性. 我們將證明若 K 和 L 都是 finite field 且 $\left\vert\vphantom{ K}\right.$ K $\left.\vphantom{ K}\right\vert$ = $\left\vert\vphantom{ L}\right.$ L $\left.\vphantom{ L}\right\vert$ 則 K $\simeq$ L. 首先要強調的是這裡的 isomorphic 指的是 ring 的 isomorphism. 大家或喧記得在線性代數中兩個 vector space 若 dimension 相同, 則它們之間是 isomorphic. 不過這裡的 isomorphic 是指 vector space 間的 isomorphism, 要求的函數是 linear transformation, 僅保持加法的結構. 另� K^* 和 L^* 是元素個數相同的 cyclic group, 從 Theorem 3.1.1 知 K^* 和 L^* 也是 isomorphic. 不過這裡的 isomorphic 指的是 group 的 isomorphism, 僅保持乘法的結構. 這兩種 isomorphic 都不能保證 K 和 L 間存在著 ring isomorphism. 我們的證明不是真的找到 K 的 L 的 ring isomorphism. 而是想找到一個 field F 滿足 K $\simeq$ F 且 F $\simeq$ L, 則利用 isomorphism 的 transitivity 性質得證 K $\simeq$ L.

証明. 首先觀察當 $\left\vert\vphantom{ K}\right.$ K $\left.\vphantom{ K}\right\vert$ = $\left\vert\vphantom{ L}\right.$ L $\left.\vphantom{ L}\right\vert$ = p 時, 由 Theorem 10.4.1 知 K 存在一個 subfield 和 $\mathbb {Z}$ / $\bigl($ p $\bigr)$ isomorphic. 不過由於 $\left\vert\vphantom{ K}\right.$ K $\left.\vphantom{ K}\right\vert$ = $\left\vert\vphantom{\mathbb{Z}/\bigl({p}\bigr)}\right.$ $\mathbb {Z}$ / $\bigl($ p $\bigr)$ $\left.\vphantom{\mathbb{Z}/\bigl({p}\bigr)}\right\vert$ = p, 故得知 K $\simeq$ $\mathbb {Z}$ / $\bigl($ p $\bigr)$ . 同理得 L $\simeq$ $\mathbb {Z}$ / $\bigl($ p $\bigr)$ , 故知 K $\simeq$ L.

畢b看一般 $\left\vert\vphantom{ K}\right.$ K $\left.\vphantom{ K}\right\vert$ = $\left\vert\vphantom{ L}\right.$ L $\left.\vphantom{ L}\right\vert$ = p^k 的情形. 由於所有元素個數為 p 的 finite field 皆 isomorphic, 所以我們可以假設 K 和 L 都是 $\mathbb {F}$ _p 的 extension, 其中 $\mathbb {F}$ _p 就是元素個數為 p 的 finite field. 由於 $\left\vert\vphantom{ K}\right.$ K $\left.\vphantom{ K}\right\vert$ = p^k, 利用 Corollary 10.4.4 知存在 a $\in$ K 使得 $\mathbb {F}$ _p(a) = K 且 a over $\mathbb {F}$ _p 的 minimal polynomial g(x) 的 degree 是 k. 因此由 Corollary 10.1.7 得

K = $\displaystyle \mathbb {F}$ _p(a) $\displaystyle \simeq$ $\displaystyle \mathbb {F}$ _p[x]/ $\displaystyle \bigl($ g(x) $\displaystyle \bigr)$ .

或袈學們會想對 L 如法泡製得到 L $\simeq$ $\mathbb {F}$ _p[x]/ $\bigl($ g(x) $\bigr)$ . 事實上這是不行的, 因為雖然 Corollary 10.4.4 告訴我們存在 a' $\in$ L 使得 L = $\mathbb {F}$ _p(a'), 不過 a' over $\mathbb {F}$ _p 的 minimal polynomial 不見得就是 g(x). 要克服這個困難我們得利用 Lemma 10.4.7. 首先, 由於 $\left\vert\vphantom{ L}\right.$ L $\left.\vphantom{ L}\right\vert$ = p^k, Proposition 10.4.2 告訴我們 x^{p^k} - x splits into linear factors in L. 不過由於 g(x) 在 $\mathbb {F}$ _p[x] 中是 irreducible (Lemma 10.1.1), 因此由 Lemma 10.4.7 得知 g(x) | x^{p^k} - x. 所以 g(x) 也 splits into linear factors in L. 換言之在 L 中存在 b $\in$ L 滿足 g(b) = 0. 當然了 g(x) 是 b over $\mathbb {F}$ _p 的 minimal polynomial. 原因是 b over $\mathbb {F}$ _p 的 minimal polynomial 一定是 g(x) 的 divisor (Lemma 10.1.1) 但 g(x) 是 irreducible 且兩者皆為 monic polynomial, 故得證 g(x) 是 b over $\mathbb {F}$ _p 的 minimal polynomial. 因此由 Corollary 10.1.7 知

$\displaystyle \mathbb {F}$ _p[x]/ $\displaystyle \bigl($ g(x) $\displaystyle \bigr)$ $\displaystyle \simeq$ $\displaystyle \mathbb {F}$ _p(b).

不過由於 $\mathbb {F}$ _p(b) $\subseteq$ L 且 [L : $\mathbb {F}$ _p] = [ $\mathbb {F}$ _p(b) : $\mathbb {F}$ _p] = k, 我們得證 L = $\mathbb {F}$ _p(b). 故知

L $\displaystyle \simeq$ $\displaystyle \mathbb {F}$ _p[x]/ $\displaystyle \bigl($ g(x) $\displaystyle \bigr)$ $\displaystyle \simeq$ K.

$\qedsymbol$

關於大學基礎代數中 field 的性質, 我們就介紹至此. 我們並沒有觸及所謂的 Galois Theory, 不過已有足夠的預備知識. 若同學們對本講義中的 field 理論很清楚了, 應該可以更進一步的去了解 Galois Theory.