Entrance to finite fields有限体ゆうげんたい

A finite field有限体ゆうげんたい is a field体たい with only finitely many elements. The important point is that division is possible even though the set is finite. Such fields体たい appear in coding theory and cryptography.

The first example is

for a prime number $$p$$p.

1Why prime numbers are necessary

For $$\mathbb{Z}/n\mathbb{Z}$$\mathbb Z/n\mathbb Z to be a field体たい, every nonzero residue class must have an inverse.

The condition for $$\left[a\right]$$[a] to have an inverse is

If $$n=p$$n=p is prime, then $$\left[a\right]\ne \left[0\right]$$[a]\ne[0] means $$p\nmid a$$p\nmid a. Therefore $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,p)=1$$\gcd(a,p)=1, so an inverse exists.

On the other hand, if $$n$$n is composite and $$n=ab$$n=ab with $$1<a,b<n$$1<a,b<n, then

while neither $$\left[a\right]$$[a] nor $$\left[b\right]$$[b] is 0. Since zero divisors零因子れいいんし exist, the structure is not a field体たい.

2Concrete example: F_5

$$F_5=\left\{\right[0],[1],[2],[3],[4\left]\right\}$$\mathbb F_5=\{[0],[1],[2],[3],[4]\}.

The inverse of $$\left[2\right]$$[2] is $$\left[3\right]$$[3] because

In this way, in a finite field有限体ゆうげんたい, addition and multiplication can be completely described by finite tables.

3Theorem: the order of a finite field is a prime power

The number of elements, or order位数いすう, of a finite field $$K$$K is always of the form

where $$p$$p is prime and $$m\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$m\ge1.

Proof. Since $$K$$K is finite, two terms in the sequence $$0,1,1+1,1+1+1,\dots$$0,1,1+1,1+1+1,\ldots are equal. Subtracting them gives a positive integer $$n$$n such that $$n·1=0$$n\cdot1=0. The least such $$n$$n is called the characteristic標数ひょうすう of $$K$$K.

If $$n=ab$$n=ab with $$1<a,b<n$$1<a,b<n, then

By the minimality of $$n$$n, both $$a·1$$a\cdot1 and $$b·1$$b\cdot1 are nonzero, contradicting the fact that a field has no zero divisors. Thus $$n$$n is a prime $$p$$p.

Define $$\iota :F_p\to K$$\iota:\mathbb F_p\to K by $$\iota \left(\right[r\left]\right)=r·1$$\iota([r])=r\cdot1. If $$r\equiv s\text{[PARSE ERROR: Undefined("Command("pmod")")]}p$$r\equiv s\pmod p, then $$(r-s)·1$$(r-s)\cdot1 is an integer multiple of $$p·1=0$$p\cdot1=0, so the map is independent of representatives. Suppose $$\iota \left(\right[r\left]\right)=0$$\iota([r])=0, so $$r·1=0$$r\cdot1=0. By integer division, write $$r=qp+t$$r=qp+t with $$0\text{[PARSE ERROR: Undefined("Command("le")")]}t<p$$0\le t<p. Then

Because $$p$$p is the least positive integer $$n$$n satisfying $$n·1=0$$n\cdot1=0, the inequality $$0\text{[PARSE ERROR: Undefined("Command("le")")]}t<p$$0\le t<p forces $$t=0$$t=0. Hence $$p\mid r$$p\mid r and $$\left[r\right]=\left[0\right]$$[r]=[0], so $$\iota$$\iota is injective. Moreover,

and $$\iota \left(\right[1\left]\right)=1$$\iota([1])=1. Thus $$\iota$$\iota preserves addition, multiplication, and the identity. Moreover, if $$\left[r\right]\ne \left[0\right]$$[r]\ne[0], then

and injectivity gives $$\iota \left(\right[r\left]\right)\ne 0$$\iota([r])\ne0. Hence the image is a subfield of $$K$$K: it is closed under addition, subtraction, multiplication, and multiplicative inverses of nonzero elements. We identify this subfield with $$F_p$$\mathbb F_p.

Use the addition of $$K$$K as vector addition. Since $$K$$K is a field, it is an abelian group under this addition. For $$\lambda \in F_p$$\lambda\in\mathbb F_p and $$x\in K$$x\in K, define scalar multiplication by

Even after identifying the subfield with $$F_p$$\mathbb F_p, we keep $$\iota$$\iota in this formula to display the embedding explicitly. Because $$\iota$$\iota preserves addition, multiplication, and the identity, the field laws in $$K$$K give, for $$\lambda ,\mu \in F_p$$\lambda,\mu\in\mathbb F_p and $$x,y\in K$$x,y\in K,

Thus $$K$$K is a vector space over $$F_p$$\mathbb F_p. Since the finite set $$K$$K spans itself, removing redundant elements produces a finite basis; let its size be $$m$$m. Since $$1\ne 0$$1\ne0, the basis is nonempty and $$m\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$m\ge1.

Every element has a unique expression as a linear combination of the $$m$$m basis elements, and each coefficient has $$p$$p choices. Therefore

4What changes and what is preserved

A finite field is a field restricted by the additional requirement that its set of elements be finite. All field axioms—addition, multiplication, and division by nonzero elements—remain in force. Finiteness makes these fields easy to handle computationally and useful in cryptography and error correction.

5Proof supplement: every finite integral domain整域せいいき is a field体たい

A finite integral domain整域せいいき $$R$$R is a field体たい.

Proof. Take $$a\in R$$a\in R with $$a\ne 0$$a\ne0. To show that $$R$$R is a field体たい, it is enough to show that $$a$$a has a multiplicative inverse. Consider the map

If $${\mu }_a\left(x\right)={\mu }_a\left(y\right)$$\mu_a(x)=\mu_a(y), then $$ax=ay$$ax=ay. Since $$a\ne 0$$a\ne0 and $$R$$R is an integral domain整域せいいき, cancellation gives $$x=y$$x=y. Therefore $${\mu }_a$$\mu_a is injective単射たんしゃ.

Because $$R$$R is a finite set, every injective単射たんしゃ map from $$R$$R to $$R$$R is surjective全射ぜんしゃ. Hence for $$1\in R$$1\in R, there exists $$x\in R$$x\in R such that $$ax=1$$ax=1. This means that $$x$$x is the inverse of $$a$$a.

Finiteness is used exactly at the step where injective単射たんしゃ implies surjective全射ぜんしゃ. For a finite set, injectivity means the image has as many elements as the domain, and the target has the same size as the domain, so every target element is reached. For infinite sets, that inference is not valid in general.

6Example: a finite field有限体ゆうげんたい with 4 elements

The ring $$\mathbb{Z}/4\mathbb{Z}$$\mathbb Z/4\mathbb Z is not a field, but a finite field with 4 elements does exist. In $$F_2\left[x\right]$$\mathbb F_2[x], consider

Since $$f\left(0\right)=1$$f(0)=1 and $$f\left(1\right)=1+1+1=1$$f(1)=1+1+1=1, the polynomial has no root over $$F_2$$\mathbb F_2. If a quadratic factors into two nonconstant polynomials, it has a linear factor and hence a root. Thus $$f$$f is irreducible既約きやく, meaning that it cannot be factored into two nonconstant polynomials.

The set of all polynomial multiples of $$f$$f,

is the ideal generated by $$f$$f. Indeed, $$0=f·0$$0=f\cdot0, and if $$fq,fr\in \left(f\right)$$fq,fr\in(f), then

Moreover, for every $$s\in F_2\left[x\right]$$s\in\mathbb F_2[x], we have $$s\left(fq\right)=f\left(sq\right)\in \left(f\right)$$s(fq)=f(sq)\in(f). Thus $$\left(f\right)$$(f) is closed under differences and under multiplication by arbitrary ring elements, so it is indeed an ideal. Form the quotient ring in which $$g$$g and $$h$$h represent the same element exactly when $$g-h\in \left(f\right)$$g-h\in(f), and define

We verify directly below that this quotient is, as the notation suggests, a field with four elements. Write $$\alpha =\left[x\right]$$\alpha=[x]. From

and the identities $$-1=1$$-1=1 and $$-\alpha =\alpha$$-\alpha=\alpha in characteristic 2, we get

We verify by induction on the exponent that every class has a representative of degree at most 1. For $$n=0,1$$n=0,1, we have $${\alpha }^0=1$$\alpha^0=1 and $${\alpha }^1=\alpha$$\alpha^1=\alpha. If $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}2$$n\ge2, then in the quotient ring

and both exponents on the right are smaller than $$n$$n. Strong induction therefore gives

for the class of every monomial $$x^n$$x^n. Adding the finitely many monomials of any polynomial gives a representative of the same form. Thus every element is one of

They are distinct: the difference of any two is a nonzero polynomial of degree at most 1. On the other hand, if $$0\ne q\in F_2\left[x\right]$$0\ne q\in\mathbb F_2[x], then $$\text{[PARSE ERROR: Undefined("Command("deg")")]}\left(fq\right)=2+\text{[PARSE ERROR: Undefined("Command("deg")")]}q\text{[PARSE ERROR: Undefined("Command("ge")")]}2$$\deg(fq)=2+\deg q\ge2, so such a difference cannot be a multiple of $$f$$f. Therefore this quotient ring has exactly four elements.

The reason for checking that $$f$$f is irreducible is now visible. If $$f=gh$$f=gh were a product of nonconstant polynomials, then, because $$f$$f is quadratic, both $$g$$g and $$h$$h would be linear. By the preceding degree argument, their classes would be nonzero, but in the quotient

producing zero divisors and preventing the quotient from being a field. Irreducibility rules out this obstruction. We do not use here the general theorem that the quotient of $$F_2\left[x\right]$$\mathbb F_2[x] by an ideal generated by an irreducible polynomial is a field; for this particular quotient, we verify the field property directly by finding the inverse of every nonzero element.

The inverses of the nonzero elements are

Indeed, $$\alpha (\alpha +1)={\alpha }^2+\alpha =1$$\alpha(\alpha+1)=\alpha^2+\alpha=1. Hence every nonzero element has an inverse, so this quotient ring is a field.

7Exercise link

8Summary

A finite field is a field with finitely many elements. The ring $$\mathbb{Z}/p\mathbb{Z}$$\mathbb Z/p\mathbb Z is a finite field when $$p$$p is prime, whereas composite moduli have zero divisors. A finite field has prime characteristic $$p$$p and is a finite-dimensional vector space over $$F_p$$\mathbb F_p, so its order is $$p^m$$p^m. The four-element field $$F_4$$\mathbb F_4 is not $$\mathbb{Z}/4\mathbb{Z}$$\mathbb Z/4\mathbb Z; it can be constructed as $$F_2\left[x\right]/(x^2+x+1)$$\mathbb F_2[x]/(x^2+x+1).