Chapter 6. Finite fields¶

Back to Course Home

Fields¶

Def 6.1 Field: A field is a communicative ring with the multiplicative identity \(1\) in which every nonzero element is invertible.
- Examples: \(\mathbb{Q}, \mathbb{R}, \mathbb{C}\)
- Cor:
  - \(\mathbb{Z}/(p)\) is a field \(\iff p\) is a prime.
  - \(F[x]/(q(x))\) is a field \(\iff q(x)\) is irreducible.
Def 6.2 Characteristic: The characteristic of a field \(F\) is defined by the smallest positive integer \(p\) s.t.

\[ p \cdot 1 = \underbrace{1 + \cdots + 1}_p = 0 \]

Denote the characteristic of a field \(F\) by \(\mathrm{char}(F)\). If there is no such \(p\), then \(\mathrm{char}(F) = 0\).
Thm 6.3: The characteristic of a field \(F\) is either \(0\) or a prime.
Proof
- Suppose \(\mathrm{char}(F) = m > 0\) is a composite number. Then there exist \(1 < a, b < m\) such that \(m = ab\). Then
  
  \[ 0 = m \cdot 1 = (ab) \cdot 1 = (a \cdot 1)(b \cdot 1) \implies a \cdot 1 = 0 \text{ or } b \cdot 1 = 0 \]
  
  Thus contradicts the minimality of \(m\). Therefore, \(\mathrm{char}(F)\) must be a prime.
Def 6.4 Subfield and Field extension: Let \(E\) be a field and \(F \subseteq E\). If \(F\) is a field under the same addition and multiplication as \(E\), then \(E/F\) is called a field extension and \(F\) is called a subfield of \(E\).
Thm 6.5: If \(E/F\) is a field extension, then \(E\) can be viewed as a vector space over \(F\) with
- Vector addition：the addition of \(F\).
- Scalar multiplication：\(\forall \lambda \in F, \alpha \in F \implies \lambda \cdot \alpha\) is multiplication in \(F\).
Def 6.6 Prime field: The prime field of a field \(F\) is the smallest subfield of \(F\) containing \(1\).
Thm 6.7: The prime field of a field \(F\) is either \(\mathbb{Q}\) or \(\mathbb{Z}_p\) for a prime \(p\).
Def 6.8 Extension degree: If \(E/F\) is a field extension, then the extension degree of \(E/F\) is defined to be the dimension \(\dim_F E\), denoted by \([E : F]\). The extension \(E/F\) is called finite if \([E : F]\) is finite, otherwise \(E/F\) is called infinite.

Example

\[ [\mathbb{C},\mathbb{Q}] = +\infty, \quad [\mathbb{C},\mathbb{R}] = 2 \]
Thm 6.9 Properties of Extension Degrees: Let \(E/F, F/K\) be field extension. Then
- \([E : K] = [E : F][F : K]\)
- \(E/K\) is a finite extension \(\iff\) Both \(E/F\) and \(F/K\) and finite extensions.
Def 6.10 Ring generation: Let \(E/F\) be a field extension, \(\alpha\) be an element of \(E\). Then the smallest subring of \(E\) containing both \(F\) and \(\alpha\) is called the ring generated by \(\alpha\) over \(F\), denoted by \(F[\alpha]\).

\[ F[\alpha] = \{f(\alpha) : f \in F[x]\} \]
Def 6.11 Field generation: Let \(E/F\) be a field extension, \(\alpha\) be an element of \(E\). Then the smallest subfield of \(E\) containing both \(F\) and \(\alpha\) is called the field generated by \(\alpha\) over \(F\), denoted by \(F(\alpha)\).

\[ F(\alpha) = \{\frac{f(\alpha)}{g(\alpha)} : f, g \in F[x], g(\alpha) \ne 0\} \]
Thm 6.12: Let \(m(x)\in F[x]\) be an irreducible polynomial with \(\deg(m) = d\) and let \(\theta\) be a root of \(m(x)\). Then

\[ F(\theta) = F[\theta] = \left\{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\right\} = \{f(\theta) : f \in F[x], \deg(f) \le d-1\} \]

Furthermore, \([F(\theta) : F] = d\).
Proof
1. \(F[θ]=\{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\} = \{f(\theta) : f \in F[x], \deg(f) \le d-1\}\):
  - \(\forall f(\theta) \in F[\theta]\), since we can write \(f(x) = m(x)q(x) + r(x)\) with \(\deg(r) < \deg(m) = d\), thus \(f(\theta) = 0 \cdot q(\theta) + r(\theta) = r(\theta) \in \{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\}\), thus \(F[\theta] \subseteq \{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\} \subseteq \{f(\theta) : f \in F[x]\} = F[\theta]\).
  - Thus \(F[\theta] = \{\sum_{i=0}^{d-1} a_i\theta^i : a_i \in F\}\) = \(\{f(\theta) : f \in F[x], \deg(f) \le d-1\}\).
2. \(F(\theta) = F[\theta]\):
  - Obviously, \(F[\theta] \subseteq F(\theta)\). It is sufficient to show that \(F[\theta]\) is a field. Consider nonzero element \(r(\theta) \in F[\theta]\).
  - \(\forall r(x) = \sum_{i=0}^{d-1} a_i\theta^i \neq 0\), we have not all \(a_i\) are zero. Thus \(\gcd(r(x), m(x)) = 1\), then by Bézout's identity, there exist \(u,v \in F[x]\) s.t. \(u(x)r(x) + v(x)m(x) = 1\). Thus \(u(\theta)r(\theta) = 1\) since \(m(\theta) = 0\), thus \(r(\theta)\) is a unit. Therefore, \(F[\theta]\) is a field, thus \(F[\theta] = F(\theta)\).
3. \([F(\theta) : F] = d\): Since \(\{1, \theta, \ldots, \theta^{d-1}\}\) is a basis of \(F(\theta)\) over \(F\), we have \([F(\theta) : F] = d\).
Thm 6.13: Let \(m(x)\in F[x]\) be an irreducible polynomial with \(\deg(m) = d\) and let \(\theta\) be a root of \(m(x)\). Then

\[ F[x]/(m) \simeq F(\theta) = F[\theta] \]
Proof
- The first isomorphism theorem: Let \(R, S\) be rings and \(\pi : R \to S\) be a ring homomorphism. Then \(\ker(\pi) = \{r \in R : \pi(r) = 0\}\) is an ideal of \(R\) and \(\mathrm{Im}(\pi) = \{\pi(r) : r \in R\}\) is a subring of \(S\). Moreover, \(R/\ker(\pi) \simeq \mathrm{Im}(\pi)\).
- Consider the homomorphism
  
  \[ \begin{aligned} \pi : F[x] &\to F(\theta) \\ f(x) &\mapsto f(\theta) \end{aligned} \]
  
  Then \(\pi\) is a ring homomorphism and \(\ker(\pi) = \{f(x) \in F[x] : \pi(f) = f(\theta) = 0\} = \{f(x) \in F[x] : m(x) \mid f(x)\} = (m) = m(x)F[x]\). Thus by the first isomorphism theorem, we have
  
  \[ F[x]/(m) \simeq \mathrm{Im}(\pi) = F[\theta] = F(\theta) \]
Example
1. \(x^2+1 \in \mathbb{R}[x]\) is irreducible, \(i\) is a root of \(x^2+1\). Thus
  
  \[ \mathbb{R}[x]/(x^2+1) \simeq \mathbb{R}[i] = \{a+bi : a,b \in \mathbb{R}\} = \mathbb{C} \]
2. \(x^2+x+1 \in \mathbb{Z}_2[x]\) is irreducible, since \(0,1\) are not roots. Let \(\theta\) be a root of \(x^2+x+1\). Then
  
  \[ \mathbb{Z}_2[x]/(x^2+x+1) \simeq \mathbb{Z}_2[\theta] = \{0, 1, \theta, 1+\theta\} \]
  
  Since \(\theta(\theta+1) = \theta^2 + \theta = -1 \equiv 1\), we have \(\theta^{-1} = \theta + 1\).

Finite fields¶

Def 6.14 Finite field: A field with finitely many elements is called a finite field or Galois field.
Thm 6.15 Properties of finite fields: Let \(F\) be a finite field of \(q\) elements, then
1. \(\mathrm{char}(F)\) is a prime \(p\).
2. \(\forall a, b \in F, (a+b)^p = a^p + b^p\).
3. \(\forall a \in F, a^q = a\).
Proof
1. Since \(F\) is a field, \(\mathrm{char}(F)\) is either \(0\) or a prime. If \(\mathrm{char}(F) = 0\), then the prime field of \(F\) is \(\mathbb{Q}\), which is infinite. Thus \(\mathrm{char}(F)\) must be a prime \(p\).
2. \(\forall a, b \in F\), we have
  
  \[ (a+b)^p = \sum_{i=0}^p \binom{p}{i} a^i b^{p-i} = a^p + b^p \]
  
  since \(p \mid \binom{p}{i} = \frac{p!}{i!(p-i)!}\) for \(1 \le i \le p-1\).|
3. If \(a = 0\), done. If \(a \ne 0\), label \(q-1\) elements of \(F^*\) as \(F^* = \{a_1, a_2, \ldots, a_{q-1}\}\). Then \(\forall i, a_i^{q-1} = 1\), thus \(a_i^q = a_i\). Thus \(\forall a \in F, a^q = a\).
Thm 6.16 Structure of finite fields: Let \(F\) be a finite field of \(q\) elements, then
1. \(q = p^n\) for some prime \(p\) and integer \(n \ge 1\).
2. \(F^* = F \setminus \{0\}\) is a cyclic group of order \(p^n-1\).
Proof
1. Since \(\mathrm{char}(F) = p\) is a prime, the prime field of \(F\) is \(\mathbb{Z}_p\). Thus \(F/\mathbb{Z}_p\) is a field extension. Since \(F\) is finite, \([F : \mathbb{Z}_p] = n < +\infty\). Thus \(|F| = p^n\).
2. Since \(F^*\) is a finite subgroup of the multiplicative group of a field, \(F^*\) is cyclic.
Thm 6.17: There exists a finite field of \(q\) elements \(\iff q = p^n\) for some prime \(p\) and integer \(n \ge 1\).
Proof
- \(\implies\): has been proved in Thm 6.16.
- \(\impliedby\): Let \(m(x) \in \mathbb{Z}_p[x]\) be an irreducible polynomial with \(\deg(m) = n\). Then \(\mathbb{Z}_p[x]/(m) = \{\sum_{i=0}^{n-1} a_i x^i : a_i \in \mathbb{Z}_p\}\) is a field with \(p^n\) elements.
Def 6.18 Algebraically closed field: A field \(\Omega\) is called algebraically closed if \(\forall f(x) \in \Omega[x]\) with \(\deg(f) \ge 1\) has at least one root in \(\Omega\).
Thm 6.19 Property of algebraically closed fields: A field \(\Omega\) is algebraically closed \(\iff \forall f(x) \in \Omega[x]\) with \(\deg(f) \ge 1\), \(f(x)\) has all roots in \(\Omega\).
Proof
- \(\implies\): Let \(f(x) \in \Omega[x]\) with \(\deg(f) \ge 1\). We will show that \(f(x)\) has all roots in \(\Omega\) by induction on \(\deg(f)\).
  - If \(\deg(f) = 1\), then \(f(x)\) has a root in \(\Omega\) since \(\Omega\) is algebraically closed.
  - If \(\deg(f) > 1\), then \(f(x)\) has a root \(\alpha\) in \(\Omega\). Thus \(f(x) = (x-\alpha)g(x)\) for some \(g(x) \in \Omega[x]\) with \(\deg(g) = \deg(f)-1\). By the induction hypothesis, \(g(x)\) has all roots in \(\Omega\). Thus \(f(x)\) has all roots in \(\Omega\).
- \(\impliedby\): Obvious.
Thm 6.20: For any field \(F\), there exists an algebraically closed field \(\Omega\) containing \(F\).
Thm 6.21: Let \(p\) be a prime and let \(n \ge 1\), then there exists a unique finite field of \(p^n\) elements.
- Notation: We denote the unique finite field of \(q\) elements by \(\mathbb{F}_q\) or \(\mathrm{GF}_q\).
Proof
- Existence: has been proved in Thm 6.17.
- Uniqueness: Let \(E, F\) be two finite fields with \(q=p^n\) elements. Then \(\forall a \in E, a^q = a\), i.e. \(a\) is a root of \(x^q - x\), thus \(E = \{a : a^q = a\} \in \Omega\). Similarly, \(F = \{a : a^q = a\} \in \Omega\). Thus \(E = F\).
Example
- \(x^3 + x + 1 \in \mathbb{Z}_2[x]\) and \(x^3 + x^2 + 1 \in \mathbb{Z}_2[x]\) are irreducible. Let \(\alpha\) be a root of \(x^3 + x + 1\) and \(\beta\) be a root of \(x^3 + x^2 + 1\). Then \(\mathbb{Z}_2[x]/(x^3 + x + 1) \simeq \mathbb{Z}_2(\alpha)\) and \(\mathbb{Z}_2[x]/(x^3 + x^2 + 1) \simeq \mathbb{Z}_2(\beta)\) are two finite fields with \(8\) elements. By the uniqueness, we have \(\mathbb{Z}_2(\alpha) = \mathbb{Z}_2(\beta) = \mathbb{F}_8\).
Thm 6.22: \(\mathbb{F}_{p^n}\) is a field extension of \(\mathbb{F}_{p^k} \iff k \mid n\).
Proof
- \(\implies\): Let \(E = \mathbb{F}_{p^n}\) and \(F = \mathbb{F}_{p^k}\). Then \([E : F] = \frac{[E : \mathbb{Z}_p]}{[F : \mathbb{Z}_p]} = \frac{n}{k}\). Since \([E : F]\) is an integer, we have \(k \mid n\).
- \(\impliedby\): Let \(m = \frac{n}{k}\). Then \(\mathbb{F}_{p^n}\) is a field extension of \(\mathbb{F}_{p^k}\) with extension degree \(m\).
Alg 6.23: Construction of finite fields of \(p^n\) elements:
1. Find a monic irreducible polynomial \(m(x)\) with \(\deg(m) = n\) over \(\mathbb{Z}_p\).
2. Find a root \(\theta\) of \(m(x)\) in an algebraically closed field \(\Omega\) containing \(\mathbb{Z}_p\).
3. Then \(\mathbb{Z}_p[x]/(m) \simeq \mathbb{Z}_p(\theta) = \{\sum_{i=0}^{n-1} a_i \theta^i : a_i \in \mathbb{Z}_p\}\) is a finite field with \(p^n\) elements.
Example
- To construct a finite field of \(16\) elements, find an irreducible polynomial of degree \(4\) over \(\mathbb{Z}_2\).
  - The only irreducible polynomial of degree \(2\) over \(\mathbb{Z}_2\) is \(x^2+x+1\).
  - All irreducible polynomial of degree \(4\) over \(\mathbb{Z}_2\) are \(x^4+x^3+x^2+x+1, x^4+x^3+1, x^4+x+1\). We choose \(m(x) = x^4+x+1\) to construct \(\mathbb{F}_{16}\).
- Let \(\theta\) be a root of \(m(x)\), thus we have
  
  \[ \mathbb{F}_{16} = \mathbb{Z}_2[x]/(m) \simeq \mathbb{Z}_2(\theta) = \{a_0 + a_1\theta + a_2\theta^2 + a_3\theta^3 : a_i \in \mathbb{Z}_2\} \]
- And we have if \(\theta\) is a root of \(m(x)\), then \(\theta^{2^n}\) is also a root of \(m(x)\).
  - Since \(m(\theta) = \theta^4 + \theta + 1 = 0\), thus \(\theta^4 = \theta + 1\).
  - \(m(\theta^2) = (\theta^2)^4 + \theta^2 + 1 = (\theta^4)^2 + \theta^2 + 1 = (\theta^4 + \theta + 1)^2 = 0\). Thus \(\theta^2\) is a root of \(m(x)\).
  - \(m(\theta^4) = m(\theta + 1) = (\theta+1)^4 + (\theta+1) + 1 = \theta^4 + \theta + 1 = 0\). Thus \(\theta^4\) is a root of \(m(x)\).
  - \(m(\theta^8) = m((\theta^4)^2) = m((\theta+1)^2) = m(\theta^2 + 1) = (\theta^2+1)^4 + (\theta^2 + 1) + 1 = 0\). Thus \(\theta^8\) is a root of \(m(x)\).
  - Since \(\theta^{16} = \theta\), we have \(m(\theta^{2^n}) = 0\) for all \(n \ge 0\). Thus \(\{\theta, \theta^2, \theta^4 = \theta + 1, \theta^8 = \theta^2 + 1\}\) are all distinct roots of \(m(x)\).
Thm 6.24: Let \(F_q\) be a finite field of \(q=p^k\) elements, and let \(I_q(d)=\#\{g \in F_q[x] : \deg(g) = d,\text{ irr, monic}\}\) be the number of monic irreducible polynomials with \(\deg(g) = d\) over \(F_q\). Then
1. Let \(n \ge 1 \in \mathbb{Z}\), then
  
  \[ x^{q^n} - x = \prod_{d \mid n} \prod_{g \in F_q[x], \text{ monic, irr} \atop \deg(g) = d} g(x) \]
2. We have the following identity, which can help us to compute \(I_q(d)\):
  
  \[ q^n = \sum_{d \mid n} d \cdot I_q(d) \]
3. By the Möbius inversion formula, we have
  
  \[ I_q(n) = \frac{1}{n} \sum_{d \mid n} \mu(d) q^{\frac{n}{d}} \]
  
  where \(\mu(d)\) is the Möbius function defined by
  
  \[ \mu(d) = \begin{cases} 1 & d = 1 \\ (-1)^k & d = \prod_{i=1}^k p_i \text{ for distinct primes } p_i \\ 0 & \exists p \text{ s.t. } p^2 \mid d \end{cases} \]