Constructing finite fields

\( \newcommand{\char}{\text{char}} \)In this blog post I will be talking about finite fields, with the main goal being how to explicitly construct them. I will try to motivate some of the results through the ring of integers.

Motivation

I will assume you, the reader, knows what fields, factor rings and ideals are. The standard examples for fields are \(\mathbb{R}\) and \(\mathbb{Q}\). Both those are infinite fields. The first finite example one most likely will see is \(\mathbb{Z}_p\); the integers modulo p with the binary operations multiplication modulo p and addition modulo p. Actually \(\mathbb{Z}_n\) is a field if and only if n is prime. This should serve as our first theorem.

Theorem 1 $$\mathbb{Z}_n \text{ is a field } \iff \text{ n is a prime }$$

Proof. First assume \(\mathbb{Z}_n \) is a field. Then the congruence \(ax \equiv 1 \pmod{n} \) is solvable for all non-zero \( a \) in \(\mathbb{Z}_n \). From elementary number theory we know that such an equation is solvable if and only if \(\gcd(a,n) = 1\). Thus we must have \(gcd(a,n)=1\) for all non-zero elements in the field. This forces n to be a prime.
Conversely if n is prime the congruence is solvable for all \( a \in \mathbb{Z}_n \). Thus all non-zero elements in \( \mathbb{Z}_n \) is units and \(\mathbb{Z}_p\) is a field. \( \blacksquare \)

Our next goal is classifying all ideals of \(\mathbb{Z} \), but this is an easy task. As a reminder an ideal is an additive subgroup of a ring \(R\) such that \( ri \in I \) and \(ir \in I \) for all \(r \in R \) and \(i \in I\). Furthermore a maximal ideal \(M\) is a proper ideal (that is \( M \neq R \)), such that there are no ideals which properly contains \(M\). Knowing that all subgroups of \(\mathbb{Z}\) is on the form \(n\mathbb{Z}\), we’re done. Proving this fact is left as an exercise to the reader (hint: use the division algorithm). Now, when is an ideal of \(\mathbb{Z}\) maximal?

Theorem 2 $$n\mathbb{Z} \text{ is a maximal ideal } \iff n \text{ is prime }$$
Proof. First asumme \(n\) is prime, and lets write \(n=p\). Suppose there exists an ideal \(M\) properly containing \(p\mathbb{Z}\). Let \(a \in M \backslash p\mathbb{Z}\). Then we must have that \(\gcd(a,p)=1\) because \(p\) is a prime. Thus by Bezouts lemma we have that \(\exists x,y \in \mathbb{Z}\) such that \(ax+py=1\). Now since \(M\) is an ideal and \(a,p \in M\), then \(ax,py \in M \) (by definition of an ideal). Since an ideal is an additive subgroup of its ring, we have that \(ax+py \in M\) and thus \(1 \in M\). By the definition of an ideal then \(1n = n \in M \) for all \(n \in \mathbb{Z}\) so \(M=\mathbb{Z}\). This shows that \(p\mathbb{Z}\) is a maximal ideal. Conversely, suppose that \(n\mathbb{Z} \) is a maximal ideal. Let \(d \mid n \). Then \(d\mathbb{Z}\) is an ideal and obviously \(d\mathbb{Z} \subseteq n\mathbb{Z}\). Because \(n\mathbb{Z}\) is a maximal ideal we must have \(d\mathbb{Z} =\mathbb{Z} \) or \(d\mathbb{Z}=n\mathbb{Z}\), implying that \(d = \pm 1\) or \(d = \pm n\). Thus, since \(d \mid n\), the only positive divisors of \(n\) are \(1\) and \(n\), so \(n \) is prime. \(\blacksquare\)

By the first isomorphism theorem, we have that if \(\phi: R \to R’\) is a homomorphism, then \(R\, /\ker \phi \simeq \text{Im } \phi \). It is easy to see that \(\mu: \mathbb{Z} \to \mathbb{Z}_p\) is a surjective homomorphism, thus \(\mathbb{Z}/p\mathbb{Z} \simeq \mathbb{Z}_p \), and thus we know that \(\mathbb{Z}/p\mathbb{Z}\) is a field, and furthermore that it is a field only when \(p\) is prime. Combining theorem 1 and 2 we see that \(\mathbb{Z}/n\mathbb{Z}\) is a field if and only if \(n\mathbb{Z}\) is a maximal ideal. Motivated by this, we ask if this is true in general. This turns out to be true for all commutative rings with unity, which we will see in the end. This is a crucial theorem for our construction.

Ideal structure in \(F[x]\)

We now turn to proving some important results we need for the construction. Polynomials play an important role in this. From our work with \(\mathbb{Z}\), we know that all its ideals take the form \(n\mathbb{Z}\). In general, for any commutative ring \(R\) with unity and any \(a \in R\), its easy to see that the set \(\{ra: r \in R \}\) denoted by \(\langle a \rangle \) is an ideal. Ideals of this form is what we refer to as principal ideals. The principal ideal \( \langle a \rangle \) is the principal ideal generated by \( a\), and if \(N\) is an ideal of \(R\) such that there exists some \(b \in R\) with \(\langle b \rangle = N \), then we say that \(N\) is a principal ideal. It is easily seen that all ideals of \(\mathbb{Z}\) is principal. This turns out to also be true for \(F[x]\).

Theorem 3
Every ideal in \(F[x]\) is principal.

Proof. Let \(I\) be any ideal of \(F[x]\). If \( I  = \{0\}\) we are done because \( \langle 0 \rangle = \{0\}\). Therefore we may assume \(I \neq \{0\} \). Let \( g(x) \in I \) where \(g(x)\) is a non-zero element of minimal degree in \(I\). If \(\deg(g(x))=0\), then \(g(x)\) is an unit and then the multiplicative identity of \(F \) is also in \(I\) so \(F[x]=I\). In this case we would be done because \(F[x]=\langle 1 \rangle \), so assume \(\deg(g(x))\geq 1\). Let \(f(x) \in F[x]\). By the division algorithm for polynomials we may write \(f(x)=g(x)q(x)+r(x)\) where \(r(x)\)=0 or \(\deg(r(x)) < \deg(g(x)) \). Because \(g(x) \in I \), we must have \(g(x)q(x) \in I \), thus \(f(x)-g(x)q(x)=r(x) \in I \). Since \(g(x)\) was choosen to have minimal degree we must have \(r(x)=0\) so \(f(x)=g(x)q(x) \), and thus \(I=\langle g(x) \rangle \). \(\blacksquare \)

We say that an ideal \(I \neq R \) of a commutative ring \(R\) is a prime ideal if \(ab \in I \) implies \(a \in I \) or \( b \in I \). This haven’t got the name prime ideal for no reason. The definition is very much motivated by the primes, especially by Euclids lemma (which we used to prove theorem 1). We restate it here: if \(p\) is prime and \(p \mid ab\) then \(p \mid a \) or \( p \mid b\). See the similarity? Furthermore, every maximal ideal is a prime ideal.

Lemma 1
Let \(A\) and \(B\) be ideals of a commutative ring \(R\) with unity, and define $$A+B = \{a + b : a \in A, b \in B \}.$$ Then \(A+B\) is also an ideal of \(R\).

Proof. We first prove that \(A+B\) is an additive subgroup of \(R\), then proving it is closed under scalar multiplication. We have \((a+b)+(a’+b’)=(a+a’)+(b+b’) \in A+B\), so \(A+B\) is closed. We have \(0 \in A,B\), so \(0+0 \in A+B\), which is the identity element. Because \(A\) and \(B\) are ideals, then if \( a \in A \) we must also have \(-a \in A \). The same thing goes for \(B\). Thus \(a+b\in A+B \implies (-a)+(-b) \in A+B\) and \((a+b)+((-a)+(-b))=0+0 \), so we have inverses. Finally if \( r \in R\) then \(ar \in A\) and \(br \in B\) because \(A\) and \(B\) are ideals. Thus \((a+b)r = ar + br \in A+B\) for any \(r \in R\). \(\blacksquare\)

Theorem 4
Every maximal ideal of a commutative ring \(R\) with unity is a prime ideal.

Proof. Let \(M \) be the maximal ideal of \(R\). Assume that \(M\) is not a prime ideal, in other words assume that \(ab \in M\) but \(a,b \not \in M \). By the lemma we know that \( \langle a \rangle + M \) is an ideal. Because \(a,b \not \in M\), we have the following proper inclusion \(M \subset \langle a \rangle \). Because \(M\) is maximal we must have \( \langle a \rangle + M = R \). Thus \(1 \in \langle a \rangle + M \) so there exists \( r \in R\) and \(m \in M \) such that \(1 = ra + m \). We can do this exact same construction for another \(b \in R\), and obtain that \(\langle b \rangle + M = R \), thus \(1=sb + n \) for some \(s \in R, n \in M\). Now $$1=1\cdot 1 = (ra+m)(sb+n)=rasb+ran+msb+mn=rs(ab)+ra(n)+sb(m)+mn$$ Because \(ab,m,n\) are all in \(M\) by hypothesis, we must also have \(1 \in M\) implying \(M =R \), but that is a contradiction because \(M\) is maximal. Thus \(M\) is a prime ideal. \(\blacksquare \)

In theorem 2 we showed that \(n\mathbb{Z}\) is a maximal ideal if and only if n is prime. In \(F[x]\) there is a similar result. Recall that a polynomial in \(f(x) \in F[x]\) is irreducible if there does not exists any other polynomials \(r(x),s(x) \in F[x]\) with degree greater or equal to 1, such that \(f(x)=s(x)r(x)\). In the same sense, a number \(p\) is prime if there does not exist any two numbers both greater than 1 such that \(p=ab\). Thus the natural question is: is an ideal in \(F[x]\) maximal iff its generator is irreducible over \(F\)? The answer is yes.

Theorem 5 $$I=\langle f(x) \rangle \text{ is a maximal ideal of } F[x] \iff f(x) \text{ is irreducible over } F$$

Proof. First assume that \( \langle f(x) \rangle \neq \{0\} \) is a maximal ideal of \( F[x]\). Furthermore, assume that there are polynomials \(g(x),h(x) \in F[x]\) with \(\deg(g(x)),\deg(h(x))\geq 1 \) such that \( f(x) = g(x)h(x) \). Then \(g(x)h(x) \in \langle f(x) \rangle \). Furthermore we also have \(deg(g(x)),\deg(h(x))<\deg(f(x))\). Because every maximal ideal is a prime ideal, we must have that \( g(x) \in \langle f(x) \rangle \) or \(h(x) \in \langle f(x) \rangle \). WLOG assume \(h(x) \in \langle f(x) \rangle \). Then we must have \( \deg(h(x)) \geq \deg(f(x))\), but this is a contradiction because \(\deg(h(x))<\deg(f(x))\). Thus \(f(x)\) is irreducible.
Conversely, assume \(f(x)\) is irreducible over \(F\). Let \(M\) be a maximal ideal of \(F[x]\) such that \(\langle f(x) \rangle \subseteq M \subset F[x] \). Because every ideal of \(F[x]\) is principal, there must be some \(g(x) \in F[x]\) such that \(\langle g(x) \rangle = M \). Therefore we may write \(f(x)=q(x)g(x)\), but because \(f(x)\) is irreducible we must have that \(q(x)\) or \(g(x)\) is of degree \( 0\). If \(\deg(g(x))=0\) we must have \(g(x)=F[x]\), which contradicts that \(M\) is maximal. Therefore assume \(\deg(q(x))=0\) and write \(q(x)=c\) for some \(c \in F\), thus \(\frac1c f(x)=g(x)\) so \(\langle f(x) \rangle = \langle g(x) \rangle \), so \(\langle f(x) \rangle \) is maximal. \( \blacksquare \)

Fields as vector spaces

We continue our analysis of finite fields by looking at its characteristic. Recall that the characteristic of a ring \(R\) with unity, denoted by \( \char(R)\) is the number of times we need to add the multiplicative identity to itself until reaching the additive identity \(0\). If this never happens the ring is said to have characteristic \(0\). Let \(R\) be a ring with unity and consider \(\phi: \mathbb{Z} \to R\) defined by \(n \mapsto n\cdot 1\). By \(n \cdot 1 \) we of course mean \(1+1+\dots+1 \text{ n times}\). We have that $$\phi(m+n)=(n+m)\cdot 1 = n\cdot 1 + m \cdot 1 = \phi(n)+\phi(m)$$ as well as $$\phi(nm)=(nm)\cdot 1 = (n\cdot 1)(m\cdot 1)=\phi(n)\phi(m)$$ so \(\phi\) is a homomorphism. This homomorphism may seem trivial, but it serves as an important part of the proof of the following theorem.

Theorem 6
Let \(R\) be a ring with unity and characteristic \(n>1\). Then \(R\) contains a subring which is isomorphic to \(\mathbb{Z}_n\).

Proof. Let \(\phi:\mathbb{Z} \to R \) be the homomorphism given in the above paragraph. Because \(\char(R)=n\) we must have \(\ker \phi = n\mathbb{Z}\), so by the first isomorphism theorem we have \(\mathbb{Z}/n\mathbb{Z} \simeq \text{Im }\phi \). However, we know that \(\mathbb{Z}/n\mathbb{Z} \simeq \mathbb{Z}_n \), so we must have \(\mathbb{Z}_n \simeq \text{Im }\phi \). Because the image of a ring homomorphism is a subring for all ring homomorphism, we have that \(R\) has a subring which is isomorphic to \(\mathbb{Z}_n\).  \(\blacksquare \).

Corollary
A finite field has prime characteristic \(p\), and has a subfield which is isomorphic to \(\mathbb{Z}_p\).

Proof. Let \(F\) be a finite field with \(\char(F)=n\). Because its finite it cannot have characteristic \(0\), because by theorem 6 it would then have \(\mathbb{Z} \subset F\). Therefore \(F\) has a subring which is isomorphic to \(\mathbb{Z}_n\). Remember from the proof of theorem 1 that \(ax \equiv 1 \pmod{n}\) is solvable iff \(\gcd(a,n)=1\). Thus if n is not prime, \(F\) would have zero divisors, contradicting that \(F\) is a field. Therefore we must have \(n=p\) for a prime \(p\), so the field has prime characteristic \(p\). \(\blacksquare\)

I will now further assume that the reader know some linear algebra. We will really only use basic concepts. It can be very easily shown that a field satisfy all the vector space axioms with vector addition defined as field addition and scalar multiplication defined as field multiplication. Thus a field is a vector space. This simple observation is very powerful because it lets use all the nice machinery from linear algebra on fields. We may now associate a basis to the field. Also, a vector space is always over a field, so we can work with a field over one of its subfields. An extension field \(E\) of a field \(F\) is exactly what you think it is; a field which contains another field \(F\). The theory on such fields is rich, and beyond the scope of this post.

Theorem 7
Let \(E\) be a vector space with \(\dim(E) = n \), which is a finite extension of a field \(F\). If \(F\) has \(q\) elements, then \(E\) has \(q^n\) elements.

Proof. Let \(\{\beta_1,\beta_2,\dots,\beta_n\}\) be a basis for \(E\). From linear algebra we know that for any \(\gamma \in E\) we may write it as a unique linear combination of the basis vectors; $$\gamma = a_1\beta_1+a_2\beta_2+\dots+a_n\beta_n$$ where \(a_i \in F\). For every \(a_i \in F\) there are \(q\) possible values, thus there are \(q^n\) possible elements for \(\gamma\). \(\blacksquare\)

Corollary
Let \(F\) be a finite field with prime characteristic \(\char(F)=p\). Then \(F\) contains exactly \(p^r\) elements for some \(r \in \mathbb{N}\).

Proof. By the corollary to theorem 6 we know that \(F\) has a subfield which is isomorphic to \(\mathbb{Z}_p\). Thus, we may view \(F\) as an extension field of \(\mathbb{Z}_p\). By theorem 7 \(|F|=p^r\) for some \( r \in \mathbb{N}\). \(\blacksquare\)

Theorem 6 and 7 shows us the benefits of viewing fields as vector spaces. However, they do not say anything explicitly how we may find a basis for the fields. That is what we will look at in the final chapter.

Final steps

Earlier in the post we saw that \(\mathbb{Z}/n\mathbb{Z}\) was a field if and only if \(n\mathbb{Z}\) was a maximal ideal of \(\mathbb{Z}\). Furthermore, I said that this was true in general; namely the fact that \(R/I\) is a field iff \(I\) is an maximal. We start of by proving this.

Theorem 8 $$R/I \text{ is a field } \iff I \text{ is a maximal ideal of R} $$
Proof. First suppose \(R/I\) is a field, and suppose there is an ideal M such that \( I \subset M \subset R\). Let \(a \in M \), but \( a \not \in I \). Then \(a + I \) is certainly not the zero-element of \(R/I\). Because \(R/I\) is a field we know that there is some \(b \in R\) such that \((a+I)(b+I)=ab + I =1+I\). Because \(M\) is an ideal and \(a \in M \), then we must have \(ab \in M \), but \(ab=1+i\) for some \(i \in I\), so \(1 \in M\) and thus \(M=R\). This is a contradiction, thus \(I\) is maximal.
Conversely, suppose that \(I\) is a maximal ideal of \(R\), and let \(a + I \) be any non-zero element of \(R/I\). We need to show that there exists some \(b \in R\) such that \(ab-1 \in I \). By lemma 1 we know that \(I’ = \{ar+s: r \in R, s \in I \} \) is an ideal. By setting \(r=0\) in \(I’\), we see that \(I \subset I’ \), and because \(I\) is maximal we must then have \(I’=R\). Furthermore this implies \(1 \in I’\), thus \(1=ab+i\) for some \(b \in R \) and \(i \in I \), so \(1-ab \in I \), thus \((a+I)(b+I) = 1 + I \) and \(R/I\) is a field. \(\blacksquare\)

By theorem 5 we know that \(\langle f(x) \rangle\) is a maximal ideal of \(F[x]\) if and only if \(f(x)\) is irreducible over \(F\). Combining this with the theorem we just proved we see that if \(f(x)\in F[x]\), then \(F[x]/\langle f(x) \rangle \) is a field if and only if \( f(x) \) is irreducible over \(F\).

Theorem 9
Let \(f(x) \in \mathbb{Z}_p[x]\) be irreducible over \(\mathbb{Z}_p\) with \(\deg(f(x))=r\). Then the set \(\beta = \{1+\langle f(x) \rangle, x+ \langle f(x) \rangle, x^2 + \langle f(x) \rangle, \dots, x^{r-1} + \langle f(x) \rangle \} \) is a basis for \(\mathbb{Z}_p[x]/\langle f(x) \rangle\) over \(\mathbb{Z}_p\).

Proof. We start with proving that the set \(\beta\) is linearly independent over \(\mathbb{Z}_p\). Thus let \(a_i \in \mathbb{Z}_p\), and assume that $$a_0(1+\langle f(x) \rangle) + a_1(x+\langle f(x)  \rangle)+\dots+a_{r-1}(x^{r-1}+\langle f(x) \rangle) = a_0 + a_1x+\dots+a_{r-1}x^{r-1} + \langle f(x) \rangle = \langle f(x) \rangle$$ We see that \(a_0+a_1x+\dots+a_{r-1}x^{r-1} \in \langle f(x) \rangle\). Since all non-zero elements \(g(x)\) in \( \langle f(x) \rangle \) has \(deg(g(x))\geq \deg(f(x))\), we see that we must have \(a_0+a_1x+\dots+a_{r-1}x^{r-1} = 0 \), so \(a_i = 0\) for \(i=0,1,\dots,r-1\). This proves that the vectors in \(\beta\) are linearly independent. Now, we must prove that \( \beta \) generates \(\mathbb{Z}_p[x]/\langle f(x) \rangle \) over \(\mathbb{Z}_p\). Let \(g(x) + \langle f(x) \rangle \in \mathbb{Z}_p[x]/\langle f(x) \rangle \) be a non-zero element of \(\mathbb{Z}_p[x]/\langle f(x) \rangle\). By the division algorithm, we may write \(g(x)=h(x)f(x) + r(x)\), where \(r(x)=0\) or \(\deg(r(x)) < \deg(f(x))\). We cant have \(r(x)=0\), because that would imply that \(g(x) + \langle f(x) \rangle\) is 0 in \(\mathbb{Z}_p[x]/\langle f(x) \rangle\). Thus \(\deg(r(x))<r\), and therefore we see that \(r(x)\) is generated by \( \{1,x,\dots,x^{r-1}\). This implies that \(\langle f(x) \rangle + r(x) \) is generated by \(\beta\), and because \(\langle g(x) \in \langle f(x) \rangle + r(x)\) we must have \(g(x)+\langle f(x) \rangle \) is also generated by \(\beta\). \(\blacksquare\)

Now we have an explicit way of finding a basis for the field \(\mathbb{Z}_p[x]/(\langle f(x) \rangle\) when \(f(x)\) is irreducible with \( \deg(f(x))=r\). We see that the basis \( \beta \) here has \(r\) elements. Thus as a vector space over \(\mathbb{Z}_p\), we see that \(\dim \left(\mathbb{Z}_p[x]/\langle f(x) \rangle \right) = r \). Since this field is finite, it has prime characteristic \(p\), and thus by the corollary to theorem 7 it has \(p^r\) elements. Constructing finite fields is now reduced to finding irreducible polynomials in \(\mathbb{Z}_p[x]\). If we were asked to find a finite field with \(16\) elements, we could observe that \(x^4+x^3+x^2+x+1\) is irreducible in \(\mathbb{Z}_2[x]\). Because \(\deg(x^4+x^3+x^2+x+1)=4\), we know from all the theory that \(\mathbb{Z}_2[x]/\langle x^4+x^3+x^2+x+1\) is a field with \(2^4=16\) elements.

 

Leave a Reply

Your email address will not be published. Required fields are marked *