UNIVERSITY OF DUBLIN

TRINITY COLLEGE

SCHOOL OF MATHEMATICS

Evariste Galois 1811-1832

Course 373 Finite Fields

Timothy Murphy

Contents

1 The Prime Fields  1–1
2 The Prime Subfield of a Finite Field  2–1
3 Finite Fields as Vector Spaces  3–1
4 Looking for 𝔽_{4}  4–1
5 The Multiplicative Group of a Finite Field  5–1
6 𝔽_{16}  6–1
7 Polynomials over a Finite Field  7–1
8 The Universal Equation of a Finite Field  8–1
9 Uniqueness of the Finite Fields  9–1
10 Automorphisms of a Finite Field  10–1
11 Wedderburn’s Theorem  11–1
12 Existence of 𝔽_{p^{n}}  12–1
12.1 Looking for 𝔽_{p^{n}}: 1. Among group representations . . . . . . . 12–1
12.2 Looking for 𝔽_{p^{n}}: 2. In number theory . . . . . . . . . . . . . . 12–3
12.3 Extension fields . . . . . . . . . . . . . . . . . . . . . . . . . . 12–4
12.4 Constructing 𝔽_{p^{n}} . . . . . . . . . . . . . . . . . . . . . . . . . 12–7
13 Prime Polynomials over a Prime Field  13–1
A Galois Theory  A–1
A.1 The Galois Correspondence . . . . . . . . . . . . . . . . . . . A–1
A.2 Towers of Extensions . . . . . . . . . . . . . . . . . . . . . . . A–3
A.3 Algebraic Extensions . . . . . . . . . . . . . . . . . . . . . . . A–4
A.4 Conjugacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A–5
A.5 The Correspondence Theorem . . . . . . . . . . . . . . . . . . A–6
A.6 Normal Subgroups and Galois Extensions . . . . . . . . . . . . A–11
A.7 Splitting Fields . . . . . . . . . . . . . . . . . . . . . . . . . . A–12

0–2

A The Normal Basis Theorem  A–1

0–3

Chapter 1

The Prime Fields

� OU WILL BE FAMILIAR with finite or modular arithmetic—in which an integer m > 0 is chosen as modulus, and we perform the arithmetic operations (addition, subtraction and multiplication) modulo m. These operations define the structure of a commutative ring on the set of

remainders

{0, 1, 2, …, m − 1}.

(Recall that a commutative ring is defined by 2 binary operations—addition and multiplication—satisfying the usual laws of arithmetic: addition and multiplication are both commutative and associative, and multiplication is distributive over addition.)

We denote this ring by ℤ/(m) (said: ‘the ring Z modulo m’). We can think of ℤ/(m) either as the set {0, 1, …, m − 1} of remainders; or as the set of congruence classes

ā = {…, a − 2m, a − m, a, a + m, a + 2m, … } (a = 0, 1, 2, …, m − 1).

The latter is ‘classier’; but the former is perfectly adequate, and probably preferable for our purposes.

Example 1. Let m = 6. Addition and multiplication in ℤ/(6) are given by

+ 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  \begin{matrix}× & 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 \end{matrix}

Proposition 1. Suppose p is prime. Then each non-zero element a ∈ ℤ/(p) is invertible, ie there exists an element b ∈ ℤ/(p) such that

ab ≡ 1 (mod p)

Proof. Consider the p remainders

a · 0 mod p, a · 1 mod p, …, a · (p − 1) mod p.

1–1

These are distinct. For if

a · r ≡ a · s (mod p),

where 0 ≤ r < s ≤ p − 1, then

a · (s − r) ≡ 0 (mod p).

In other words,

p | a(s − r).

Since p is prime, this implies that

p | a or p | s − r.

Both these are impossible, since 0 < a < p and 0 < s − r < p.

Since the p remainders a · i mod p above are distinct, they must constitute the full set of remainders modulo p (by the Pigeon-Hole Principle). In particular, they must include the remainder 1, ie for some b

a · b ≡ 1 (mod p).

Recall that a field is a commutative ring with precisely this property, i.e. in which every non-zero element is invertible.

Corollary 1. For each prime p, ℤ/(p) is a field.

Definition 1. We denote this field by 𝔽_{p}.

The reason for the double notation—𝔽_{p} and ℤ/(p)—is this. We shall show later that there exists a unique field 𝔽_{p^{n}} for each prime-power p^{n}. The fields 𝔽_{p} form so to speak the lowest layer in this hierarchy.

Nb: 𝔽_{p^{n}} is not the same as the ring ℤ/(p^{n}), unless n = 1. Indeed, it is easy to see that ℤ/(m) cannot be a field unless m is prime.

Finite fields are often called Galois fields, in honour of their discoverer, the French mathematician Évariste Galois. As you probably know, Galois died in a duel (not even over a woman!) at the age of 21.

The notation GF(q) is sometimes used in place of 𝔽_{q}, although 𝔽_{q} seems to be becoming standard, presumably to emphasize that finite fields should be considered on a par with the familiar fields ℚ, ℝ, ℂ. Example 2. Addition and multiplication in 𝔽_{7} are given by

+ 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5  \begin{matrix}× & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\ 3 & 0 & 3 & 6 & 2 & 5 & 1 & 4 \\ 4 & 0 & 4 & 1 & 5 & 2 & 6 & 3 \\ 5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\ 6 & 0 & 6 & 5 & 4 & 3 & 2 & 1 \end{matrix}

Summary: For each prime p the remainders modulo p form a field 𝔽_{p} containing p elements.

1–2

The Prime Subfield of a Finite Field

� SUBFIELD OF A FIELD F is a subset K ⊂ F containing 0 and 1, and closed under the arithmetic operations—addition, subtraction, multiplication and division (by non-zero elements).

Proposition 2. Suppose F is a field. Then F contains a smallest subfield P.

Proof. Any intersection of subfields is evidently a subfield. In particular, the intersection of all subfields of F is a subfield P contained in every other subfield.

Definition 2. We call the smallest subfield P of a field F the prime (or rational) subfield of F.

Definition 3. The characteristic of a field F is defined to be the smallest integer n > 0 such that

n · 1 = \overbrace{1 + 1 + ⋯ + 1}^{n times} = 0,

if there is such an integer; or 0 otherwise.

Proposition 3. The characteristic of a field is either a prime or 0. The characteristic of a finite field is always a prime.

Proof. Suppose the characteristic n of the field F is a non-prime integer, say n = rs, where 1 < r, s. Since 1 · 1 = 1, repeated application of the distributive law gives

(r · 1)(s · 1) = (\overbrace{1 + 1 + ⋯ + 1}^{r times})(\overbrace{1 + 1 + ⋯ + 1}^{s times}) = n · 1 = 0.

Since F is a field, it follows that either r · 1 = 0 or s · 1 = 0; and in either case the characteristic of F is less than n, contrary to hypothesis.

Now suppose F is finite. Then the sequence

0, 1, 1 + 1, 1 + 1 + 1, …

must have a repeat; say

r · 1 = s · 1

where r < s. Then

(s − r) · 1 = 0,

and so F has finite characteristic.

2–1

Proposition 4. If F is a field of characteristic p, then its prime subfield P ⊂ F is uniquely isomorphic to 𝔽_{p}:

char F = p ⟹ P = 𝔽_{p}.

Proof. If F has characteristic p then we can define a map

Θ : 𝔽_{p} → F

by

r ↦ r · 1 (r = 0, 1, …, p − 1).

It is readily verified that this map preserves addition and multiplication, and so is a homomorphism. (We always take ‘homomorphism’ to mean unitary homomorphism, i.e. we assume that Θ(1) = 1.)

Now a homomorphism of fields is necessarily injective. For suppose Θa = Θb, where a ≠ b. Let c = b − a. Then

Θa = Θb ⟹ Θc = 0
⟹ Θ(1) = Θ(cc^{−1}) = ΘcΘc^{−1} = 0
⟹ Θ(x) = Θ(x · 1) = Θ(x)Θ(1) = 0,

for all x.

Thus Θ defines an isomorphism between 𝔽_{p} and im Θ.

But every subfield of F contains the element 1, and so also contains r · 1 = 1 + ⋯ + 1. Hence the field im Θ is contained in every subfield of F, and so must be its prime subfield:

P = im Θ ≅ 𝔽_{p}.

Finally, the isomorphism Θ is unique, since

Θ1 = 1 ⟹ Θr = Θ(1 + ⋯ + 1) = Θ1 + … Θ1 = r · 1.

Corollary 2. 𝔽_{p} is the only field containing p elements.

Much the same argument shows that the prime subfield of a field of characteristic 0—which as we have seen must be infinite—is uniquely isomorphic to the rational field ℚ:

char F = 0 ⟹ P = ℚ.

Summary: Every finite field F contains one of the prime fields 𝔽_{p} as its smallest (or prime) subfield.

2–2

Finite Fields as Vector Spaces

� UPPOSE THAT F is a finite field of characteristic p, with prime subfield

P = 𝔽_{p}. Then we can regard F as a vector space over P. You may be more familiar with vector spaces over ℂ and ℝ. In fact the full

panoply of linear algebra—the concepts of basis, dimension, linear transformation, etc—carry over unchanged to the case of vector spaces over a finite field.

Theorem 1. Suppose F is a finite field of characteristic p. Then F contains p^{n} elements, for some n:

∥F ∥ = p^{n}.

Proof. Suppose that F, as a vector space, has dimension n over P. Then we can find a basis {e_{1}, e_{2}, …, e_{n}} for F over P. Each element a ∈ F is then uniquely expressible in the form

a = λ_{1}e_{1} + λ_{2}e_{2} + ⋯ + λ_{n}e_{n}.

There are just p choices for each coordinate λ_{i}; so the total number of elements in F is

\overbrace{p · p ⋯ p}^{n times} = p^{n}.

By convention, we usually denote the number of elements in F by q. So we have shown that

q = p^{n} :

every finite field has prime-power order.

We are going to show—this is one of our main aims—that there is in fact exactly one finite field (up to isomorphism) of each prime order p^{n}, which we shall denote by 𝔽_{p^{n}}.

Proposition 5. Suppose the finite field F contains p^{n} elements; and suppose K is a subfield of F. Then K contains p^{m} elements, where m | n.

Proof. In the proof of the Theorem above we considered F as a vector space over P, and we showed that if this space has dimension n then

∥F ∥ = ∥P ∥^{n}.

3–1

But we can equally well consider F as a vector space over K. Our argument now shows that if this space has dimension d then

∥F ∥ = ∥K∥^{d}.

If ∥F ∥ = p^{n}, it follows that ∥K∥ = p^{m}, where n = md.

Another way to prove this result is to consider the multiplicative groups

F^{×} = F − {0}, K^{×} = K − {0},

formed by the non-zero elements of F and K. These groups have orders p^{n} − 1 and p^{m} − 1. Since K^{×} is a subgroup of F^{×}, it follows by Lagrange’s Theorem that

(p^{m} − 1) | (p^{n} − 1).

We leave it to the reader to show that this is true if and only if m | n.

We shall see later that in fact 𝔽_{p^{n}} contains exactly one subfield with p^{m} elements if m | n; as we may say,

𝔽_{p^{m}} ⊂ 𝔽_{p^{n}} ⟺ m | n.

We can exploit the vector-space structure of F in other ways (apart from proving that ∥F ∥ = p^{n}). Suppose a ∈ F. Then multiplication by a defines a map

μ_{a} : F → F : x ↦ ax.

This map is evidently a linear transformation of F, regarded as a vector space over P. It follows that we can speak of its trace and determinant; and these will in turn define functions

T, D : F → P

on F with values in P:

T (a) = tr μ_{a}, D(a) = det μ_{a}.

We’ll return to these functions later, when we have finite fields to hand in which to see them at work. At present the only finite fields we know about are the prime fields 𝔽_{p} and T (a) and D(a) both reduce trivially to a in this case.

Summary: The number of elements in a finite field is necessarily a prime-power:

∥F ∥ = p^{n}.

3–2

Looking for 𝔽_{4}

� OES THERE EXIST a field with 4 elements? (This is the first case in which there could exist a non-prime field.) A bull-headed approach—with a little help from the computer—will surely succeed in such a simple case. Let’s suppose, then, that the field F has 4 = 2^{2} elements. We know that F

must have characteristic 2, so that

x + x = 0

for all x ∈ F.

Two of the elements of F are 0 and 1. Let the two others be called ⊥ and ⊤ (said: bottom and top). Thus

F = {0, 1, ⊥, ⊤}.

Consider the element ⊥ + 1. A little thought shows that it cannot be 0, 1 or ⊥. For example,

⊥ + 1 = 0 ⟹ (⊥ + 1) + 1 = 0 + 1
⟹ ⊥ + (1 + 1) = 1
⟹ ⊥ + 0 = 1
⟹ ⊥ = 1,

which contradicts our choice of ⊥ as an element of F different from 0 and 1. Now we can draw up the addition-table for F:

\begin{matrix}+ & 0 & 1 & ⊥ & ⊤ \\ 0 & 0 & 1 & ⊥ & ⊤ \\ 1 & 1 & 0 & ⊤ & ⊥ \\ ⊥ & ⊥ & ⊤ & 0 & 1 \\ ⊤ & ⊤ & ⊥ & 1 & 0 \end{matrix}

Turning to the multiplication table, let’s see what we already know:

× 0 1 ⊥ ⊤
0 0 0 0 0
1 0 1 ⊥ ⊤
⊥ 0 ⊥
⊤ 0 ⊤

4–1

Evidently it suffices to determine ⊥^{2} = ⊥ × ⊥, since the remaining products will then follow on applying the distributive law.

We have 4 choices:

⊥^{2} = 0 Since ⊥ is non-zero, it has an inverse ⊥^{−1}. Thus

⊥^{2} = 0 ⟹ ⊥^{−1}(⊥^{2}) = 0
⟹ (⊥^{−1}⊥)⊥ = 0
⟹ 1 · ⊥ = 0
⟹ ⊥ = 0,

contrary to our assumption that ⊥ differs from 0 and 1.

⊥^{2} = 1 This gives

⊥^{2} − 1 = (⊥ − 1)(⊥ + 1) = 0.

Since F is a field, this implies that

⊥ = 1 or ⊥ = −1.

In fact since F has characteristic 2, −1 = 1 and so

⊥^{2} = 1 ⟹ ⊥ = 1,

again contrary to assumption.

More simply, since F has characteristic 2,

⊥^{2} − 1 = (⊥ − 1)^{2},

the middle term −2⊥ vanishing.

⊥^{2} = ⊥ This implies that

⊥(⊥ − 1) = 0

and so either ⊥ = 0 or ⊥ = 1, both of which are excluded.

⊥^{2} = ⊤ As Sherlock Holmes said, When all other possibilities have been exhausted, the one remaining, however improbable, must be true. So in this case we conclude that we must have

⊥^{2} = ⊤.

Now we can complete our multiplication table

⊥ × ⊤ = ⊥(⊥ + 1) = ⊥^{2} + ⊥ = ⊥ + ⊤ = 1,
⊤ × ⊤ = (⊥ + 1)^{2} = ⊥^{2} + 1 = ⊤ + 1 = ⊥.

\begin{matrix}× & 0 & 1 & ⊥ & ⊤ \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & ⊥ & ⊤ \\ ⊥ & 0 & ⊥ & ⊤ & 1 \\ ⊤ & 0 & ⊤ & 1 & ⊥ \end{matrix}

So if there is a field with 4 elements, this must be it. But do these tables in fact define a field?

This is a convenient point to review exactly what we mean by a field, by listing the Field Axioms.

4–2

Definition 4. A field F is defined by giving 1. A set F with 2 distinguished elements 0 and 1;

2. Two binary operations on F, ie 2 maps

+ : F × F → F, × : F × F → F,

subject to the axioms: (F1) addition is associative: for all a, b, c ∈ F,

a + (b + c) = (a + b) + c;

(F2) addition is commutative: for all a, b ∈ F,

b + a = a + b;

(F3) for all a ∈ F,

a + 0 = a;

(F4) for each a ∈ F, there is a b ∈ F such that

a + b = 0;

(F5) multiplication is associative: for all a, b, c ∈ F,

a(bc) = (ab)c;

(F6) multiplication is commutative: for all a, b ∈ F,

ba = ab;

(F7) for all a ∈ F,

a · 1 = a;

(F8) multiplication is distributive over addition: for all a, b, c ∈ F,

a(b + c) = ab + ac.

(F9) for each a ≠ 0 in F, there is a b ∈ F such that

ab = 1; The rationals ℚ, the reals ℝ and the complex numbers ℂ are examples of fields,

as of course are the finite (or galois) fields 𝔽_{p}. Proposition 6. Suppose F is a field. Then

1. for each a, b ∈ F, the equation

a + x = b

has a unique solution;

4–3

2. for each a, b ∈ F with a ≠ 0, the equation

ay = b

has a unique solution.

Proof. By (F4) there exists a c such that

a + c = 0.

But then

a + (c + b) = (a + c) + b by (F1)
= 0 + b
= b  by (F3)

Thus x = c + b is a solution of the equation a + x = b. It is moreover the only solution, since

a + x = b = a + y ⟹ c + (a + x) = c + (a + y)
⟹ (c + a) + x = (c + a) + y by(F 1)
⟹ (a + c) + x = (a + c) + y by(F 2)
⟹ 0 + x = 0 + y
⟹ x = y  by(F 3).

The second part of the Proposition is proved in an exactly analogous way.

Returning to our prospective field F of 4 elements: to prove that this is a field we must verify that the axioms (F1–F9) hold.

This is a straighforward, if tedious, task. To verify (F1), for example, we must consider 4^{3} = 64 cases, since each of the 3 elements a, b, c can take any of the 4 values 0, 1, ⊥, ⊤.

Let’s pass the task on to the computer, by giving a little C program to test the axioms.

#include <stdio.h>
typedef enum{zero, one, bottom, top} GF4;
char *el[4] = {"0", "1", "b", "t"};
GF4 add[4][4] = {
  {zero, one, bottom, top},
  {one, zero, top, bottom},
  {bottom, top, zero, one},
  {top, bottom, one, zero}
};
GF4 mul[4][4] = {
  {zero, zero, zero, zero},
  {zero, one, bottom, top},
  {zero, bottom, top, one},
  {zero, top, one, bottom}
};

4–4

main() {
GF4 x, y, z;
/* testing (F1) */
for(x = zero; x <= top; x++)
  for (y = zero; y <= top; y++)
    for (z = zero; z <= top; z++)
      if (add[add[x][y]][z] != add[x][add[y][z]])
printf("(%s + %s) + %s != %s + (%s + %s)\n",
  el[x], el[y], el[z], el[x], el[y], el[z]);
/* testing (F2) */
for(x = zero; x <= top; x++)
  for (y = zero; y <= top; y++)
    if (add[x][y] != add[y][x])
printf("%s + %s != %s + %s\n", el[x], el[y], el[y], el[x]);
/* testing (F3) */
for(x = zero; x <= top; x++)
  if (add[x][zero] != x)
printf("%s + 0 != %s\n", el[x], el[x]);
/* testing (F4) */
for(x = zero; x <= top; x++) {
  for (y = zero; y <= top; y++)
    if (add[x][y] == 0)
break;
  if (y > top)
    printf("%s + x = 0 has no solution in x\n", el[x]);
}
/* testing (F5) */
for(x = zero; x <= top; x++)
  for (y = zero; y <= top; y++)
    for (z = zero; z <= top; z++)
      if (mul[mul[x][y]][z] != mul[x][mul[y][z]])
printf("(%s * %s) * %s != %s * (%s * %s)\n",
  el[x], el[y], el[z], el[x], el[y], el[z]);
/* testing (F6) */
for(x = zero; x <= top; x++)
  for (y = zero; y <= top; y++)

4–5

    if (mul[x][y] != mul[y][x])
printf("%s * %s != %s * %s\n", el[x], el[y], el[y], el[x]);
/* testing (F7) */
for(x = zero; x <= top; x++)
  if (mul[x][one] != x)
printf("%s * 1 != %s\n", el[x], el[x]);
/* testing (F8) */
for(x = zero; x <= top; x++)
  for (y = zero; y <= top; y++)
    for (z = zero; z <= top; z++)
      if (mul[add[x][y]][z] != add[mul[x][z]][mul[y][z]])
printf("(%s + %s) * %s != %s * %s + %s * %s\n",
  el[x], el[y], el[z], el[x], el[z], el[y], el[z]);
/* testing (F9) */
for(x = one; x <= top; x++) {
  for (y = one; y <= top; y++)
    if (mul[x][y] == 1)
break;
  if (y > top)
    printf("%s * x = 1 has no solution in x\n", el[x]);
}
}

Not a very strenuous test for the computer, admittedly. But at least it shows who is boss.

Summary: There is just one field with 4 elements, as we expected.

4–6

The Multiplicative Group of a Finite Field

� UPPOSE F is a field. The non-zero elements

F^{×} = F − {0}

form a group under multiplication. (We could even take this as the definition of a field: a commutative ring whose non-zero elements form a multiplicative group.)

If F contains q elements, then F^{×} contains q − 1 elements. It follows from Lagrange’s Theorem for finite groups that

a^{q−1} = 1

for all a ∈ F^{×}.

(There is a very simple proof of Lagrange’s Theorem for a finite abelian—or commutative—group

A = {a_{1}, a_{2}, …, a_{n}}.

Suppose a ∈ A. Consider the n products

aa_{1}, aa_{2}, …, aa_{n}.

These are distinct, since

ax = ay ⟹ x = y.

Hence they must be all the elements of A, in some order:

{aa_{1}, aa_{2}, …, aa_{n}} = {a_{1}, a_{2}, …, a_{n}}.

Multiplying together the elements on each side,

(aa_{1})(aa_{2}) … (aa_{n}) = a_{1}a_{2} … a_{n}.

In other words,

a^{n}a_{1}a_{2} … a_{n} = a_{1}a_{2} … a_{n}.

Hence

a^{n} = 1,

on dividing both sides by a_{1}a_{2} … a_{n}.)

5–1

Theorem 2. Suppose F is a finite field. Then the multiplicative group F^{×} is cyclic.

Proof. Recall that a group G is said to be of exponent e (where e is a positive integer) if

g^{e} = 1

for all g ∈ G, and there is no smaller positive integer with this property. (Another way of expressing this is to say that e is the lcm of the orders of the elements of G.)

By Lagrange’s Theorem, the exponent e of a finite group G divides its order:

e | ∥G∥.

In general a group of exponent e need not contain an element of order e. For example, the symmetric group S_{3} has exponent 6 (since it contains elements of orders 2 and 3); but it has no element of order 6 — otherwise it would be cyclic. However, an abelian group always has this property.

Lemma 1. Suppose A is a finite abelian group, of exponent e. Then there exists an element a ∈ A of order e.

Proof of Lemma. Let

e = p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}}.

There must exist an element a ∈ A of order p_{1}^{e_{1}}m for some m, since otherwise p_{1} would occur to a lower power in e. Then

a_{1} = a^{m}

has order p_{1}^{e_{1}}. Similarly there exist elements a_{2}, …, a_{r} or orders p_{2}^{e_{2}}, …, p_{r}^{e_{r}}.

Sublemma 1. In an abelian group A, if a has order m and b has order n, and gcd(a, b) = 1, then ab has order mn.

Proof of Sublemma. Suppose ab has order d. Since

(ab)^{mn} = (a^{m})^{n}(b^{n})^{m},

we have d | mn.

On the other hand,

(ab)^{d} = 1 ⟹ (ab)^{nd} = 1 ⟹ a^{nd} = 1,

since b^{nd} = (b^{n})^{d} = 1. But a has order m; consequently

m | nd ⟹ m | d,

since gcd(m, n) = 1. Similarly n | d. But then

mn | d,

since gcd(m, n) = 1.

We conclude that d = mn.

5–2

The orders of the elements a_{1}, …, a_{r} are mutually co-prime. It follows from the Sublemma that their product

a_{1} ⋯ a_{r}

is of order

p_{1}^{e_{1}} ⋯ p_{r}^{e_{r}} = e

Now suppose the multiplicative group F^{∗} has exponent e. Then each of the q − 1 elements a ∈ F^{∗} satisfies the polynomial equation

x^{e} − 1 = 0.

But a polynomial p(x) of degree d has at most d roots. It follows that

q − 1 ≤ e.

Since e | q − 1 we conclude that

e = q − 1.

Hence, by our Lemma, F^{∗} contains an element a of order q − 1, which therefore generates F^{∗} (since this group has q − 1 elements). In particular, F^{∗} is cyclic.

Definition 5. Suppose F is a finite field. A generator of F^{×} is called a primitive element (or primitive root) of F

Our Theorem can thus be stated in the form: Every finite field possesses at least one primitive element.

Recall that Euler’s function ϕ(n) (for positive integers n) is defined to be the number of numbers i in the range

{0, 1, 2, …, n − 1}

coprime to n (ie with gcd(i, n) = 1). Thus

ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4, ϕ(6) = 2, ϕ(7) = 6, ϕ(8) = 4,

and so on.

Proposition 7. The number of primitive roots in F is ϕ(q − 1).

Proof. Since we know that

F^{∗} = C_{q−1},

the result is a consequence of the following Lemma.

Lemma 2. The cyclic group C_{n} has ϕ(n) generators

Proof of Lemma. Suppose g is a generator of C_{n}. We have to determine how many of the elements g^{r} with 0 ≤ r < n are also generators of C_{n}.

Sublemma 2. The order of g^{r} ∈ C_{n} is

\frac{n}{gcd(n, r)}

5–3

Proof of Sublemma. Let the order of g^{r} be d; and let gcd(n, r) = e. Then

n = en′, r = er′ (gcd(n′, r′) = 1).

Hence

(g^{r})^{n′} = (g^{en′})^{r′} = (g^{n})^{r′} = 1,

since g^{n} = 1. It follows that

d | n′.

On the other hand,

(g^{r})^{d} = 1 ⟹ g^{rd} = 1
⟹ n | rd
⟹ n′ | r′d
⟹ n′ | d,

since gcd(n′, r′) = 1.

We conclude that

d = n′ = \frac{n}{e} = \frac{n}{gcd(n, r)}.

In particular, the number of elements of order n in C_{n}, ie the number of generators of C_{n}, is equal to the number of integers r in the range 0 ≤ r < n which are coprime to n. But that, by definition, is ϕ(n).

Recall the explicit formula for ϕ(n): if

n = p_{1}^{e_{1}}p_{2}^{e_{2}} … p_{s}^{e_{s}}

then

ϕ(n) = p_{1}^{e_{1}−1}(p_{1} − 1)p_{2}^{e_{2}−1}(p_{2} − 1) … p_{s}^{e_{s}−1}(p_{s} − 1).

This follows from the fact that the function ϕ(n) is multiplicative in the numbertheoretic sense, ie

ϕ(mn) = ϕ(m)ϕ(n) if gcd(m, n) = 1.

(This in turn is a simple consequence of the Chinese Remainder Theorem.) The result now follows from the particular case n = p^{e}. But the only numbers in {0, 1, 2, …, p^{e} −1} not coprime to p^{e} are the multiples of p; and there are just p^{e−1} of these. Hence

ϕ(p^{e}) = p^{e} − p^{e−1} = p^{e−1}(p − 1).

So now it is easy to determine the number of primitive elements in a finite field. For example, 𝔽_{2^{4}} has ϕ(15) = 8 primitive elements, while 𝔽_{2^{5}} has ϕ(31) = 30 primitve elements.

Surprisingly, perhaps, it is just as difficult to prove our theorem for the elementary finite fields 𝔽_{p} as in the general case. Moreover, there is really no better way of finding a primitive root modulo p (ie a primitive element of 𝔽_{p}) than testing the elements 2, 3, 5, 6, … successively. (We can at least omit powers like 4; for if 4 were primitive 2 would certainly be so.)

5–4

On the other hand, once we have found one primitive element a ∈ F^{×} it is easy to determine the others; they are just the powers

a^{r} where gcd(r, q − 1) = 1.

As an illustration, consider the field 𝔽_{7} = ℤ/(7). We find that

2^{3} = 8 ≡ 1.

Thus 2 has order 3, and is not primitive. But 3^{2} ≡ 2, 3^{3} ≡ 6. Since the order of every non-zero element must divide q − 1 = 6, we conclude that 3 has order 6, and so is a primitive root modulo 7. There are just ϕ(6) = 2 primitive elements; and these are the elements 3^{r} where 0 ≤ r < 6 and gcd(r, 6) = 1; in other words r = 1 and r = 5. Thus the full set of primitive roots modulo 7 is

3, 3^{5} = 5.

(We may note that since 3^{6} ≡ 1,

3^{5} = 3^{−1}.

And clearly, if a is a primitive element of F^{×} then so is its inverse a^{−1}.)

Summary: The multiplicative group F^{×} of a finite field F is cyclic. The generators of this group are called the primitive elements of the field.

5–5

𝔽_{16}

� E CONSTRUCTED 𝔽_{4} knowing almost nothing of finite fields. Now,

with a little more knowledge let’s raise our sights a little. Suppose the field F contains 16 elements. Let π be a primitive element of F.

Then

F = {0, 1, π, π^{2}, …, π^{14}}.

Since

π^{15} = 1,

the multiplication in F is completely determined:

\begin{matrix}× & 0 & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} \\ π & 0 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 \\ π^{2} & 0 & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π \\ π^{3} & 0 & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} \\ π^{4} & 0 & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} \\ π^{5} & 0 & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} \\ π^{6} & 0 & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} \\ π^{7} & 0 & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} \\ π^{8} & 0 & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} \\ π^{9} & 0 & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} \\ π^{10} & 0 & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} \\ π^{11} & 0 & π^{11} & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} \\ π^{12} & 0 & π^{12} & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} \\ π^{13} & 0 & π^{13} & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} \\ π^{14} & 0 & π^{14} & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} \end{matrix}

Turning to addition, consider the sum

π^{i} + π^{j}.

If j > i, we can write this is

π^{i}(1 + π^{j−i}).

Thus addition will be determined if we know 1 + π^{i} for each i (0 ≤ i ≤ 14).

We have

1 + π^{i} = π^{j},

6–1

for some j = σ(i). Since we are working in characteristic 2, we can rewrite this as

π^{i} + π^{σ(i)} = 1.

Evidently σ is a permutation of {1, 2, …, 14} of order 2,

σ^{2} = 1,

ie σ(σ(i)) = i for all i. Furthermore,

σ(i) ≠ i,

since π^{i} + π^{i} = 0. Thus σ is a permutation of type 2^{7}, that is, it splits into 7 2-cycles.

There are

\frac{14!}{2^{7}7!} = 13 · 11 · 9 · 7 · 5 · 3 = 135135

such permutations. For we can write the numbers 1, 2, …, 14 is 14! ways; and if we now bracket successive pairs, eg

(3, 7)(8, 2)(10, 13)(14, 4)(6, 1)(5, 9)(12, 11),

we have a permutation of type 2^{7}. Each such permutation arises in 2^{7}7! ways; for firstly, we can write each of the 7 pairs in 2 ways, and secondly, we can order the 7 pairs in 7! ways.

Recall that π^{15} = 1. Thus we can regard the exponents of π as numbers modulo 15, and σ as a permutation of ℤ/(15). With this understanding, σ defines the addition of 2 different powers of π by the rule:

π^{i} + π^{j} = π^{i+σ(j−i)}.

The permutation σ determines the addition table, while the multiplication table is already known. In principle we could go through the 135135 cases, examining in each case if the 9 field axioms were satisfied.

For example, if

σ = (1, 11)(2, 8)(3, 12)(4, 5)(6, 13)(7, 9)(10, 14)

the addition table starts

\begin{matrix}+ & 0 & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} \\ 0 & 0 & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} \\ 1 & 1 & 0 & π^{11} & π^{8} & π^{12} & π^{5} & π^{4} & π^{13} & π^{9} & π^{2} & π^{7} & π^{14} & π & π^{3} & π^{6} & π^{10} \\ π & π & π^{11} & 0 & π^{12} & π^{9} & π^{13} & π^{6} & π^{5} & π^{14} & π^{10} & π^{3} & π^{8} & 1 & π^{2} & π^{4} & π^{7} \\ π^{2} & π^{2} & π^{8} & π^{12} & 0 & π^{13} & π^{10} & π^{14} & π^{7} & π^{6} & 1 & π^{11} & π^{4} & π^{9} & π & π^{3} & π^{5} \\ π^{3} & π^{3} & π^{6} & π^{9} & π^{13} & 0 & π^{14} & π^{11} & 1 & π^{8} & π^{7} & π & π^{12} & π^{5} & π^{10} & π^{2} & π^{4} \end{matrix}

On going through the axioms, it is clear that all except the first two are automatically satisfied for every permutation σ of type 2^{7}—we only need to consider the associativity and commutativity of addition.

Taking commutativity first,

1 + π^{i} = π^{i} + 1 ⟹ π^{σ(i)} = π^{i+σ(−i)}
⟹ σ(i) = i + σ(−i)
⟹ σ(i) − σ(−i) = i.

6–2

It’s readily verified that if this holds for all i ∈ {1, …, 14} then π^{i} + π^{j} = π^{j} + π^{i} for all i, j.

Suppose this is so. Turning to associativity,

π^{i} + (1 + π^{j}) = (π^{i} + 1) + π^{j} ⟹ π^{i} + π^{σ(j)} = π^{σ(i)} + π^{j}
⟹ π^{i+σ(σ(j)−i)} = π^{j+σ(σ(i)−j)}
⟹ σ(σ(j) − i) + i = σ(σ(i) − j) + j.

Again, it is readily verified that if this holds for all i, j ∈ {1, …, 14} then π^{i} + (π^{j} + π^{k}) = (π^{i} + π^{j}) + π^{k} for all i, j, k.

So all(!) we have to do is to run through the 135135 permutations, and determine in each case whether or not these 2 relations hold:

σ(i) − σ(−i) = i

for all i, and

σ(σ(j) − i) + i = σ(σ(i) − j) + j.

for all i, j. If these relations do hold then the permutation yields a field of 16 elements.

But it’s more instructive to look at the question from another point of view. Since (a + b)^{2} = a^{2} + b^{2} in a field of characteristic 2,

π^{i} + π^{σ(i)} = 1 ⟹ π^{2i} + π^{2σ(i)} = 1
⟹ σ(2i) = 2σ(i).

In other words, σ commutes with multiplication by 2. Formally, let

μ : ℤ/(15) → ℤ/(15)

be the map corresponding to multiplication by 2:

μ(i) = 2i.

Then

σμ = μσ.

Now μ is a permutation of ℤ/(15); in cyclic notation

μ = (1, 2, 4, 8)(3, 6, 12, 9)(5, 10)(7, 14, 13, 11).

(Under μ, in other words, 1 ↦ 2, 2 ↦ 4, etc.)

There is a neat way of expressing commutation among permutations. Note first that

σμ = μσ ⟺ σμσ^{−1} = μ.

But if we have a permutation expressed in cyclic form, say

θ = (a_{1}, a_{2}, …, a_{r})(b_{1}, b_{2}, …, b_{s}) …

then it is readily verified that for any other permutation g,

gθg^{−1} = (ga_{1}, ga_{2}, …, ga_{r})(gb_{1}, gb_{2}, …, gb_{s}) ….

(Under gθg^{−1},

ga_{i} ↦^{g^{−1}} a_{i} ↦^{θ} a_{i+1} ↦^{g} ga_{i+1},

6–3

for example.) Applying this to the present case,

σμσ^{−1} = (σ1, σ2, σ4, σ8)(σ3, σ6, σ12, σ9)(σ5, σ10)(σ7, σ14, σ13, σ11).

This must be the same as μ:

σμσ^{−1} = μ.

It follows that σ must permute the three 4-cycles in some way, and must send the 2-cycle to itself. Since σi ≠ i, the latter implies that

σ(5) = 10, σ(10) = 5.

In other words,

π^{5} + π^{10} = 1.

As for the action of σ on the three 4-cycles, there are 2 possibilities. Either σ sends each 4-cycle into itself, or it interchanges two and sends the third into itself. In any case, it must send at least one 4-cycle into itself.

Suppose σ sends the 4-cycle (a, b, c, d) into itself:

(σa, σb, σc, σd) = (a, b, c, d),

Then we must have

σa = c, σb = d, σc = a, σd = b.

For we know that σa ≠ a; while for example

σ(a) = b ⟹ σ(b) = σ(2a) = 2σ(a) = 2b = c,

whereas we know that

σ(a) = b ⟹ σ(b) = a,

since σ^{2} = 1.

We have dramatically reduced the number of possibilities; there is just one σ sending each 4-cycle into itself, while if σ swaps 2 4-cycles, we can choose the one that goes to itself in 3 ways, and there are then 4 ways of defining σ, eg if

σ(1, 2, 4, 8) = (3, 6, 12, 9)

we have 4 possibilities:

\begin{matrix}σ1 = 3, & σ2 = 6, & σ4 = 12, & σ8 = 9; \\ σ1 = 6, & σ2 = 12, & σ4 = 9, & σ8 = 3; \\ σ1 = 12, & σ2 = 9, & σ4 = 3, & σ8 = 6; \\ σ1 = 9, & σ2 = 3, & σ4 = 6, & σ8 = 12. \end{matrix} \}

Note that in each of these cases, σ is completely determined. In the first case, for example,

σ = (1, 3)(2, 6)(4, 12)(5, 10)(7, 13)(8, 9)(11, 14).

Thus we have reduced the 135135 cases to just 1 + 3 · 4 = 13.

Observe that in this reduction we have not invoked the conditions that commutativity and associativity of addition impose on σ. Consider the commutativity condition:

σ(−i) = σ(i) − i.

Suppose σ sends the 4-cycle (1, 2, 4, 8) into itself. As we have seen this implies that

σ1 = 4.

6–4

But this in turn implies that

σ(−1) = σ(14) = σ(1) − 1 = 3.

Since 14 and 3 belong to different 4-cycles, the first of our 13 cases is out; σ must send one 3-cycle into itself, and interchange the other two.

There is one last reduction. We should perhaps have noted earlier that the three 4-cycles are not on the same footing. While (1, 2, 4, 8) and (7, 14, 13, 11) correspond to primitive elements (since the numbers are co-prime to 15), the 4cycle (3, 6, 12, 9) corresponds to elements of order 5.

Now we could have chosen any of the permutations π^{i}, with i co-prime to 15, in place of π. In particular we could have chosen π^{7} in place of π. This would have interchanged the two primitive 4-cycles. Thus the case in which the third 4-cycle is sent into itself is effectively the same as that in which the first 4-cycle is sent into itself. We have reduced the 13 cases to 8.

In fact, if the first 4-cycle is sent into itself, σ is determined completely. For as we saw, we must have

\begin{matrix}σ1 = 4, σ2 = 8, σ3 = 14, σ5 = 10, \\ σ13 = σ(−2) = σ2 − 2 = 6, σ12 = σ(−3) = σ3 − 3 = 11. \end{matrix}

Thus

σ = (1, 4)(2, 8)(3, 14)(5, 10)(6, 13)(7, 9)(11, 12).

Suppose the second 4-cycle is sent into itself. Then

σ3 = 12, σ6 = 9, σ12 = 3, σ9 = 6.

But

σ3 = 12 ⟹ σ12 = σ(−3) = σ3 − 3 = 9.

We conclude that this case cannot occur.

In the end therefore we are left with only 1 case, (corresponding to the permutation above) leading to the addition table

\begin{matrix}+ & 0 & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} \\ 0 & 0 & 1 & π & π^{2} & π^{3} & π^{4} & π^{5} & π^{6} & π^{7} & π^{8} & π^{9} & π^{10} & π^{11} & π^{12} & π^{13} & π^{14} \\ 1 & 1 & 0 & π^{4} & π^{8} & π^{14} & π & π^{10} & π^{13} & π^{9} & π^{2} & π^{7} & π^{5} & π^{12} & π^{11} & π^{6} & π^{3} \\ π & π & π^{4} & 0 & π^{5} & π^{9} & 1 & π^{2} & π^{11} & π^{14} & π^{10} & π^{3} & π^{8} & π^{6} & π^{13} & π^{12} & π^{7} \\ π^{2} & π^{2} & π^{8} & π^{5} & 0 & π^{6} & π^{10} & π & π^{3} & π^{12} & 1 & π^{11} & π^{4} & π^{9} & π^{7} & π^{14} & π^{13} \\ π^{3} & π^{3} & π^{14} & π^{9} & π^{6} & 0 & π^{7} & π^{11} & π^{2} & π^{4} & π^{13} & π & π^{12} & π^{5} & π^{10} & π^{8} & 1 \\ π^{4} & π^{4} & π & 1 & π^{10} & π^{7} & 0 & π^{8} & π^{12} & π^{3} & π^{5} & π^{14} & π^{2} & π^{13} & π^{6} & π^{11} & π^{9} \\ π^{5} & π^{5} & π^{10} & π^{2} & π & π^{11} & π^{8} & 0 & π^{9} & π^{13} & π^{4} & π^{6} & 1 & π^{3} & π^{14} & π^{7} & π^{12} \\ π^{6} & π^{6} & p^{13} & π^{11} & π^{3} & π^{2} & π^{12} & π^{9} & 0 & π^{10} & π^{14} & π^{5} & π^{7} & π & π^{4} & 1 & π^{8} \\ π^{7} & π^{7} & π^{9} & p^{14} & π^{12} & π^{4} & π^{3} & π^{13} & π^{10} & 0 & π^{11} & 1 & π^{6} & π^{8} & π^{2} & π^{5} & π \\ π^{8} & π^{8} & π^{2} & π^{10} & 1 & π^{13} & π^{5} & π^{4} & π^{14} & π^{11} & 0 & π^{12} & π & π^{7} & π^{9} & π^{3} & π^{6} \\ π^{9} & π^{9} & π^{7} & π^{3} & π^{11} & π & π^{14} & π^{6} & π^{5} & 1 & π^{12} & 0 & π^{13} & π^{2} & π^{8} & π^{10} & π^{4} \\ π^{10} & π^{10} & π^{5} & π^{8} & π^{4} & π^{12} & π^{2} & 1 & π^{7} & π^{6} & π & π^{13} & 0 & π^{14} & π^{3} & π^{9} & π^{11} \\ π^{11} & π^{11} & π^{12} & π^{6} & π^{9} & π^{5} & π^{13} & π^{3} & π & π^{8} & π^{7} & π^{2} & π^{14} & 0 & 1 & π^{4} & π^{10} \\ π^{12} & π^{12} & π^{11} & π^{13} & π^{7} & π^{10} & π^{6} & π^{14} & π^{4} & π^{2} & π^{9} & π^{8} & π^{3} & 1 & 0 & π & π^{5} \\ π^{13} & π^{13} & π^{6} & π^{12} & π^{14} & π^{8} & π^{11} & π^{7} & 1 & π^{5} & π^{3} & π^{10} & π^{9} & π^{4} & π & 0 & π^{2} \\ π^{14} & π^{14} & π^{3} & π^{7} & π^{13} & 1 & π^{9} & π^{12} & π^{8} & π & π^{6} & π^{4} & π^{11} & π^{10} & π^{5} & π^{2} & 0 \end{matrix}

It only remains to verify that this addition table (together with the ealier multiplication table) do indeed defined a field; that is, the identities enshrining the commutativity and associativity of addition hold.

We pass the task on to the computer.

6–5

#include <stdio.h>
int sigma[16] = {0, 4, 8, 14, 1, 10, 13, 9, 2, 7, 5, 12, 11, 6, 3};
main()
{
int i, j;
int err = 0;
/* testing (F1) */
for(i = 1; i <= 14; i++)
  for(j = 1; j <= 14; j++)
    if (sigma[i] != j)
if ((15 + sigma[(15 + sigma[i] -j) % 15] + j) % 15 !=
(15 + sigma[(15 + sigma[j] -i) % 15] + i) % 15) {
  err++;
      printf("\\pi^%d + (1 + \\pi^%d) != (\\pi^%d + 1) + \\pi^%d\n",
i, j, i, j);
}
if (!err) printf("Axiom F1 satisfied\n");
/* testing (F2) */
err = 0;
for(i = 1; i <= 14; i++)
  if ( (15 + sigma[i] - sigma[15-i]) % 15 != i) {
    err++;
    printf("1 + \\pi^%d != \\pi^%d + 1\n", i, i);
  }
if (!err) printf("Axiom F2 satisfied\n");
}

Summary: We have shown that there exists just 1 field 𝔽_{2^{4}} containing 16 elements. Moreover, our construction would apply in principle to any finite field 𝔽_{2^{n}} of characteristic 2.

6–6

Polynomials over a Finite Field

� POLYNOMIAL over a field F is a formal expression

f(x) = c_{n}x^{n} + c_{n−1}x^{n−1} + ⋯ + c_{0} (c_{i} ∈ F).

When F is finite we must distinguish between the polynomial f(x) and the map

x ↦ f(x) : F → F

which it defines; for 2 different polynomials may define the same map, or what comes the the same thing, a polynomial may vanish for all elements of F, as for example the polynomial

f(x) = x^{2} − x,

in the field 𝔽_{2}.

The polynomials over F can be added and multiplied—we assume that the constructions are familiar—and so constitute a commutative ring (with 1) which we denote by F [x].

Example 3. There are just 8 polynomials of degree ≤ 2 over 𝔽_{2}, namely

0, 1, x, x + 1, x^{2}, x^{2} + 1, x^{2} + x, x^{2} + x + 1.

We have

(x + 1) + (x^{2} + x + 1) = x^{2}, (x + 1)(x^{2} + x + 1) = x^{3} + 1.

We will be dealing almost exclusively with polynomials over a prime field P. Many of the questions concerning a finite field F can be expressed in terms of the polynomials over its prime subfield, which are generally much easier to get hold of, particularly with a computer.

At the same time, the study of the ring P [x] of polynomials over the prime field P is a subject of great interest in its own right. There is a remarkable analogy between the ring P [x] and the familiar ring of integers ℤ. Almost every question that one can ask about ℤ—for example, questions concerning the distribution of the primes—can equally well be asked of P [x]. To take an extreme example, the Riemann hypothesis (or more accurately, conjecture)—which has baffled generations of mathematicians—can be proved relatively easily in P [x]. (Usually it is simpler to establish a proposition in P [x] than in ℤ.)

Definition 6. A polynomial f(x) of degree ≥ 1 over the field F is said to be prime (or indecomposable) if it cannot be expressed as the product of 2 polynomials of lower degree over F.

7–1

Example 4. There are just 5 prime polynomials of degree ≤ 3 over 𝔽_{2}, namely

x, x + 1, x^{2} + x + 1, x^{3} + x + 1, x^{3} + x^{2} + 1.

Proposition 8. (The Prime Factorisation Theorem) Every polynomial over the field F is expressible as a product of prime polynomials over F, unique up to order (and scalar multiples).

Proof. This is almost identical with the usual proof in the classical case ℤ.

Lemma 3. Suppose f(x), g(x) ∈ F [x]; and suppose g ≠ 0. Then we can divide f by g to obtain quotient q(x) and remainder r(x):

f(x) = q(x)g(x) + r(x) (deg r < deg g).

Lemma 4. Suppose f(x), g(x) ∈ F [x]. Then f and g have a greatest common divisor

d(x) = gcd(f(x), g(x))

such that

d(x) | f(x), g(x);

and if e(x) ∈ F (x) then

e(x) | f(x), g(x) ⟹ d(x) | e(x).

Furthermore, we can find polynomials u(x), v(x) ∈ F [x] such that

u(x)f(x) + v(x)g(x) = d(x).

Proof. We apply the Euclidean algorithm to f(x) and g(x):

f(x) = q_{1}(x)g(x) + r_{1}(x)
g(x) = q_{2}(x)r_{1}(x) + r_{2}(x)
r_{1}(x) = q_{3}(x)r_{2}(x) + r_{3}(x)
…
r_{i−1}(x) = q_{i+1}(x)r_{i}(x).

the process must end with an exact division, since the degrees of the remainders are strictly decreasing:

deg g > deg r_{1} > deg r_{2} > ….

Now it is easy to see that the last non-zero remainder r_{i}(x) is the required polynomial:

r_{i}(x) = gcd (f(x), g(x)) .

For on the one hand, going up the chain we see successively that

r_{i}(x) | r_{i−1}(x),
r_{i}(x) | r_{i−2}(x),

…

r_{i}(x) | g(x),
r_{i}(x) | f(x).

7–2

On the other hand, if e(x) | f(x), g(x) then going down the chain we see successively that

e(x) | r_{1}(x),
e(x) | r_{2}(x),
…
e(x) | r_{i}(x).

Finally, going down the chain we can successively express r_{1}(x), r_{2}(x), … in the form

r_{j}(x) = u_{j}(x)f(x) + v_{j}(x)g(x)
r_{j+1}(x) = r_{j−1}(x) − q_{j+1}(x)r_{j}(x)
= (u_{j−1}(x) − q_{i+1}(x)u_{i}(x)) f(x) + (v_{j−1}(x) − q_{i+1}(x)v_{i}(x)) g(x)
= u_{j+1}(x)f(x) + v_{j+1}(x)g(x),

where

u_{j+1}(x) = (u_{j−1}(x) − q_{i+1}(x)u_{i}(x)) , v_{j+1}(x) = (v_{j−1}(x) − q_{i+1}(x)v_{i}(x)) ;

until finally we obtain an expression for r_{i}(x) = gcd(f, g) of the form

gcd(f(x), g(x) = u(x)f(x) + v(x)g(x),

as required.

Example 5. Working over 𝔽_{2}, suppose

f(x) = x^{5} + x^{2} + 1, g(x) = x^{4} + x^{3} + 1.

We have

f(x) + xg(x) = x^{4} + x^{2} + x + 1,
f(x) + xg(x) + g(x) = x^{3} + x^{2} + x = r_{1}(x).

This is the first step of the euclidean algorithm. Continuing,

g(x) + xr_{1}(x) = x^{3} + x + 1,
g(x) + xr_{1}(x) + r_{1}(x) = x^{2} + x + 1 = r_{2}(x),
r_{1}(x) + xr_{2}(x) = 1 = r_{3}(x).

Hence

gcd (f(x), g(x)) = 1,

and working backwards we find that

1 = r_{1}(x) + xr_{2}(x)
= r_{1}(x) + g(x) + (x + 1)r_{1}(x)
= g(x) + xr_{1}(x)
= g(x) + f(x) + (x + 1)g(x)
= f(x) + xg(x).

Returning to the proof of the Prime Factorisation Theorem—sometimes call the Fundamental Theorem of Arithmetic—

7–3

Lemma 5. Suppose p(x), f(x), g(x) ∈ F [x]; and suppose p is prime. Then

p(x) | f(x)g(x) ⟹ p(x) | f(x) or p(x) | g(x).

Proof. Consider

d(x) = gcd (p(x), f(x)) .

Since d(x) by definition divides p(x); and since p(x) by definition has only the factors 1 and itself, either d(x) = 1 or d(x) = p(x).

If d(x) = p(x) then

p(x) | f(x)

(since d(x) | f(x)) and we are done.

On the other hand if d(x) = 1, then by the Lemma above we can find u(x), v(x) ∈ F [x] such that

u(x)p(x) + v(x)f(x) = 1.

Multiplying by g(x),

u(x)p(x)g(x) + b(x)f(x)g(x) = g(x).

Now p(x) divides both terms on the left (since p(x) | f(x)g(x)). Hence

p(x) | g(x).

Turning to the proof of the Proposition, if f(x) is not a prime then we can factorise it

f(x) = u(x)v(x)

into 2 polynomials of lesser degree. If these are not prime, they can again be split; until finally we must attain an expression for f(x) as a product of primes.

Finally, if we have 2 expressions for f(x) as products of primes

p_{1}(x) ⋯ p_{m}(x) = f(x) = q_{1}(x) ⋯ q_{n}(x)

then the last Lemma shows that the p’s and q’s must be the same, up to order.

Proposition 9. Suppose F is a finite field, with prime subfield P. Each element a ∈ F is a root of a unique prime polynomial m(x) over P.

If ∥F ∥ = p^{n} then the degree of m(x) is ≤ n.

For each polynomial f(x) over P,

f(a) = 0 ⟺ m(x) | f(x).

Proof. If ∥F ∥ = p^{n}, then

dim_{P} F = n.

Hence if a ∈ F, the n + 1 elements

1, a, a^{2}, …, a^{n}

must be linearly dependent, ie

c_{0} + c_{1}a + c_{2}a^{2} + ⋯ + c_{n}a^{n} = 0

for some c_{i} ∈ P (not all zero). In other words a is a root of the polynomial

f(x) = c_{0} + c_{1}x + c_{2}x^{2} + ⋯ + c_{n}x^{n} = 0.

7–4

Now let m(x) be the polynomial of smallest degree ≥ 1 satisfied by a. Then

deg m(x) ≤ deg f(x) ≤ n.

Also m(x) must be prime. For if

m(x) = u(x)v(x)

then

0 = m(a) = u(a)v(a) ⟹ u(a) = 0 or v(a) = 0,

since F is a field. But that contradicts the minimality of m(x).

Finally, suppose f(a) = 0. Divide f(x) by m(x):

f(x) = m(x)q(x) + r(x),

where deg r(x) < deg m(x). Then

r(a) = f(a) − m(a)q(a) = 0,

and so r(x) = 0 by the minimality of m(x), ie m(x) | f(x).

This last result shows in particular that m(x) is the only prime polynomial (up to a scalar multiple) satisfied by a.

Remarks 1. 1. Another way of seeing that a ∈ F satisfies an equation of degree ≤ n is to consider the linear map μ_{a} : F → F defined by multiplication by a:

μ_{a}(t) = at.

By the Cayley-Hamilton theorem, this linear transformation satisfies its own characteristic equation

χ_{a}(x) = det (xI − μ_{a}) .

It follows that a also satisfies this equation:

χ_{a}(a) = 0.

2. We shall see in Chapter 9 that if a ∈ 𝔽_{p^{n}} then the minimal polynomial of a must have degree d | n.

Conversely—and more surprisingly—we shall find that all the roots of any prime polynomial of degree d | n lie in 𝔽_{p^{n}}.

Summary: Each element a ∈ F is the root of a unique prime polynomial m(x) ∈ P [x].

7–5

The Universal Equation of a Finite Field

� N AN INFINITE FIELD, a polynomial p(x) cannot vanish for all values of x unless it vanishes identically, ie all its coefficients vanish. For if p is of degree d it cannot have more than d roots, by the Remainder Theorem.

In a finite field, however, the position is quite different.

Theorem 3. Suppose F is a finite field of order q. Then every element a ∈ F satisfies the equation

U(x) ≡ x^{q} − x = 0.

Proof. By Lagrange’s Theorem

a^{q−1} = 1

for all a ∈ F^{×}. Multiplying by a,

a^{q} = a.

But this is also satisfied by a = 0. Thus it is satisfied by all a ∈ F.

Corollary 2. Suppose F is a finite field of order q. Then

x^{q} − x ≡ ∏_{a∈F}(x − a)

over F.

Corollary 3. Suppose F is a finite field of order q; and suppose p(x) ∈ P [x], where P is the prime subfield of F. Then

p(x) = 0 for all x ∈ F ⟺ U(x) | p(x).

Corollary 4. Suppose F is a finite field of order q; and suppose a ∈ F. Then the minimal polynomial m(x) of a is a factor of the universal polynomial:

m(x) | U(x).

Let

U_{n}(x) ≡ x^{p^{n}} − x.

We want to show that

U_{m}(x) | U_{n}(x) ⟺ m | n.

It turns out to be simpler to prove a more difficult result.

8–1

Proposition 10. Let d = gcd(m, n). Then

gcd (U_{m}(x), U_{n}(x)) = U_{d}(x),

where

U_{m}(x) ≡ x^{p^{m}} − x, U_{n}(x) ≡ x^{p^{n}} − x, U_{d}(x) ≡ x^{p^{d}} − x.

Proof. Recall the recursive version of the euclidean algorithm (for calculating gcd(m, n)), enshrined in the following C-code.

unsigned gcd( unsigned m, unsigned n )
{
  if( m == 0 ) return n;
  if( n == 0 ) return m;
  if ( m < n ) return gcd( m, n - m );
  return gcd( n, m - n );
}

Following this idea, we prove the result by induction on max(m, n). The result is trivial if m = n, or m = 0, or n = 0. We may therefore assume, without loss of generality, that 0 < m < n. Let

n = m + r.

By the binomial theorem,

(x^{p^{m}} − x)^{p} = x^{p^{m+1}} − x^{p},

all the terms except the first and last in the expansion vanishing. Repeating this r times,

U_{m}(x)^{p^{r}} = (x^{p^{m}} − x)^{p^{r}}
= x^{p^{m+r}} − x^{p^{r}}
= x^{p^{n}} − x^{p^{r}}
= U_{n}(x) − U_{r}(x).

It follows from this that

gcd (U_{m}(x), U_{n}(x)) = gcd (U_{r}(x), U_{m}(x)) .

But by the inductive hypothesis,

gcd (U_{r}(x), U_{m}(x)) = U_{gcd(r,m)}(x)
= U_{gcd(m,n)}(x),

since

gcd(r, m) = gcd(m, n).

Corollary 5. We have

U_{m}(x) | U_{n}(x) ⟺ m | n.

Summary: In a finite field, every element satisfies the universal equation

x^{q} = x,

where q = ∥F ∥.

8–2

Uniqueness of the Finite Fields

� F WE ARE NOT YET in a position to show that the field 𝔽_{p^{n}} exists for each prime powers p^{n}, we can at least show that there is at most one such field.

Theorem 4. Two finite fields with the same number of elements are necessarily isomorphic.

Proof. Suppose F, F′ are finite fields with

∥F ∥ = q = ∥F′∥.

(Of course we know that q must be a prime-power: q = p^{n}.)

Choose a primitive root π ∈ F. Let its minimal polynomial be m(x). Then

m(x) | x^{q} − x.

Now let us go across to F′. Since

x^{q} − x = ∏_{a′∈F′} (x − a′) ,

m(x) must factor completely in F′, say

m(x) = (x − a′_{1}) ⋯ (x − a′_{d}).

Choose any of these roots as π′, say π′ = a′_{1}. We are going to define an isomorphism

Θ : F → F′

under which

π ↦ π′.

Observe first that π′ must be a primitive root in F′, ie it must have order q −1. For suppose its order were d < q − 1. Then π′ would satisfy the equation

x^{d} − 1.

Now m(x), as a prime polynomial satisfied by π′, must in fact be its minimal polynomial. Hence

m(x) | x^{d} − 1.

But then, going back to F, this implies that

π^{d} − 1 = 0,

9–1

ie π has order < q − 1. We conclude that π′ must be a primitive root in F′.

Thus π and π′ each generates a cyclic group C_{q−1}. So we can certainly define a group isomorphism

Θ : F^{×} → F′^{×} : π^{i} ↦ π′^{i}.

We can extend this to a bijection

Θ : F → F′

by adding the rule 0 ↦ 0.

This bijection Θ certainly preserves multiplication:

Θ(ab) = Θ(a)Θ(b)

for all a, b ∈ F. It remains to show that it also preserves addition, ie

Θ(a + b) = Θ(a) + Θ(b).

If one (or both) of a and b is 0 this holds trivially; so we may assume that a, b ≠ 0. There are 2 cases to consider, according as a + b = 0 or not.

Dealing first with the second (and general) case, let

a = π^{i}, b = π^{j}, a + b = π^{k}.

Thus

π^{i} + π^{j} = π^{k}

in F. In other words, π satisfies the equation

x^{i} + x^{j} − x^{k} = 0.

It follows that

m(x) | x^{i} + x^{j} − x^{k}.

Going across to F′, we deduce that π′ also satisfies the equation

x^{i} + x^{j} − x^{k} = 0.

In other words

π′^{i} + π′^{j} = π′^{k}

Thus

Θ(a) + Θ(b) = Θ(a + b),

as required.

It remains to consider the trivial case

a + b = 0.

If the characteristic is 2 then this implies that a = b, in which case it is evident that Θ(a) = Θ(b), and so

Θ(a) + Θ(b) = 0.

If the characteristic is odd, then we note that −1 is the only element in F of order 2; for the polynomial

x^{2} − 1 = (x − 1)(x + 1)

9–2

has just the 2 roots ±1. (This is a particular case of our earlier result that the number of elements in F of order d | q − 1 is ϕ(d).) In fact we must have

−1 = π^{\frac{q−1}{2}}

since the element on the right certainly has order 2.

Thus if we suppose that i > j (as we may without loss of generality)

π^{i} + π^{j} = 0 ⟹ π^{i−j} = −1
⟹ i − j = \frac{q − 1}{2}
⟹ (π′)^{i−j} = −1
⟹ π′^{i} + π′^{j} = 0;

so addition is preserved in this case also.

We have shown that the bijection Θ : F → F′ preserves addition and multiplication; in other words, it is an isomorphism.

Summary: There is at most 1 field 𝔽_{p^{n}} with p^{n} elements. (It remains to be shown that this field actually exists!)

9–3

Automorphisms of a Finite Field

� HE AUTOMORHPHISM GROUP G of a field F is usually called its Galois group. Galois theory establishes a correspondence between subfields of F and subgroups of G. To each subfield K ⊂ F we associate the subgroup

{g ∈ G : gx = x for all x ∈ K}.

Conversely, to each subgroup H ⊂ G we associate the subfield

{x ∈ F : gx = x for all g ∈ H}.

In the case of a finite field F, as we shall see, this establishes a one-one correspondence between the subfields of F and the subgroups of G.

Proposition 11. Suppose F is a finite field of characteristic p. Then the map

a ↦ a^{p}

is an automorphism of F.

Proof. The map evidently preserves multiplication:

(ab)^{p} = a^{p}b^{p}.

Less obviously, it also preserves addition:

(a + b)^{p} = a^{p} + b^{p}.

For on expanding the left-hand side by the binomial theorem, all the terms except the first and last vanish. For

p | ( \begin{matrix}p \\ i \end{matrix} ) (i = 1, …, p − 1),

since p divides the numerator but not the denominator of

( \begin{matrix}p \\ i \end{matrix} ) = \frac{p(p − 1) ⋯ (p − i + 1)}{1 · 2 ⋯ i}.

Finally, the map is injective since

a^{p} = 0 ⟹ a = 0.

Since F is finite, this implies that the map is bijective, and so an automorphism of F.

10–1

Remarks 2. 1. This is an astonishing result. In characteristic p, the map

x ↦ x^{p}

is linear.

2. The map a ↦ a^{p} is an injective endomorphism for any field F of characteristic p. But it may not be bijective if F is infinite.

Definition 7. We call the automorphism a ↦ a^{p} the Frobenius automorphism of F, and denote it by Φ.

Theorem 5. Suppose F is a finite field, with

∥F ∥ = p^{n}.

Then the automorphism group of F is a cyclic group of order n, generated by the Frobenius automorphism:

Aut 𝔽_{p^{n}} = C_{n} = {I, Φ, Φ^{2}, …, Φ^{n−1} : Φ^{n} = I}

Proof.

Lemma 6. The Frobenius automorphism Φ of 𝔽_{p^{n}} has order n

Proof of Lemma. We know that

a^{p^{n}} = a

for all a ∈ F. We can rewrite this as

Φ^{n}(a) = a

for all a, ie

Φ^{n} = I.

Suppose

Φ^{m} = I

for some m < n. In other words

a^{p^{m}} = a

for all a ∈ F. This is an equation of degree p^{m} with p^{n} > p^{m} roots: an impossibility. We conclude that Φ has order n.

We must show that

I, Φ, Φ^{2}, …, Φ^{n−1}

are the only automorphisms of 𝔽_{p^{n}}.

Lemma 7. Each automorphism Θ of a finite field F leaves invariant each element of its prime subfield P.

Proof of Lemma. If c ∈ P, we have

c = 1 + ⋯ + 1.

Hence

Θ(c) = Θ(1) + ⋯ + Θ(1) = 1 + ⋯ + 1 = c.

10–2

Lemma 8. The only elements of a finite field F left invariant by the Frobenius automorphism Φ are the elements of its prime subfield P.

Proof of Lemma. By the last lemma, the p elements of P are all roots of the equation

Φ(a) ≡ a^{p} = a.

Since this equation has degree p, they are all the roots.

Lemma 9. Suppose π is a primitive element of the finite field F. Then any automorphism Θ of F is completely determined by its action on π; that is, if Θ, Θ′ are 2 such automorphisms then

Θ(π) = Θ′(π) ⟹ Θ = Θ′.

Proof of Lemma. Since every element α ≠ 0 in F is of the form α = π^{i} for some i, the result follows from the fact that

Θ(π) = Θ′(π) ⟹ Θ(π^{i}) = Θ′(π^{i}).

Let π be a primitive element in F. Consider the product

f(x) = (x − π)(x − Φπ) ⋯ (x − Φ^{n−1}π).

Applying the automorphism Φ to this product,

f^{Φ}(x) = (x − Φπ)(x − Φ^{2}π) ⋯ (x − π)
= f(x),

the n factors simply being permuted cyclically. Thus f(x) is left unchanged by Φ. From the Lemma above, this implies that the coefficients of f(x) all lie in the prime subfield P:

f(x) ∈ P [x].

Now suppose Θ is an automorphism of F. Then

f^{Θ}(x) = f(x),

since the coefficients of f(x), being in P, are left unchanged by Θ. Thus

f^{Θ}(x) = (x − Θπ)(x − ΘΦπ) ⋯ (x − ΘΦ^{n−1}π)
= (x − π)(x − Φπ) ⋯ (x − Φ^{n−1}π).

It follows that

Θπ = Φ^{i}π

for some i. But by the last lemma, this implies that

Θ = Φ^{i}.

Proposition 12. Suppose p(x) ∈ P [x] is a prime polynomial of degree d; and suppose p(x) has a root α in the finite field F. Then all the roots of p(x) lie in F; they are in fact the d elements

{α, Φα, …, Φ^{d−1}α} .

10–3

Proof. Since the automorphism Φ leaves the elements of the prime field P fixed,

p(α) = 0 ⟹ p(Φα) = 0

Thus Φα = α^{p} is also a root of p(x). So by the same argument are Φ^{2}α, Φ^{3}α, . . .. On the other hand, we saw in the proof of the last Proposition that

f(x) ≡ ∏_{0≤i<n} (x − Φ^{i}α) ∈ P [x].

Since p(x) is the minimal polynomial of α, and α is a root of f(x), it follows that

p(x)|f(x).

But f(x) factorises completely in F. Hence the same is true of p(x); and its roots must lie among the roots

{α, Φα, …, Φ^{n−1}α}

of f(x).

Let e be the least integer > 0 such that

Φ^{e}α = α.

Then the elements

{α, Φα, …, Φ^{e−1}α}

are all distinct. For if 0 ≤ i < j ≤ e,

Φ^{i}α = Φ^{j}α ⟹ Φ^{j−i}α = α,

on applying the automorphism Φ^{−i}. But since 0 < j − i < e that contradicts the minimality of e.

On the other hand, we saw that the elements of this reduced set are all roots of p(x). In fact they are all the roots. For we know that every root is of the form Φ^{i}α; and if

i = eq + r (0 ≤ r < e),

then

Φ^{i}α = Φ^{r}α.

Finally, since p(x) is of degree d, it has just d roots. Hence d = e.

Proposition 13. The field 𝔽_{p^{n}} has exactly one subfield containing p^{m} elements for each m | n.

Proof. We know from Chapter 3 that if F ⊂ 𝔽_{p^{n}} contains p^{m} elements then m | n; and we also know that in this case

F = 𝔽_{p^{m}}.

It follows that all the elements of F satisfy the equation

x^{p^{m}} = x.

Since this equation has at most p^{m} roots in 𝔽_{p^{n}}, it follows that

F = {x ∈ 𝔽_{p^{n}} : x^{p^{m}} = x} .

10–4

Conversely, suppose m | n. Let

F = {x ∈ 𝔽_{p^{n}} : x^{p^{m}} = x}
= {x ∈ 𝔽_{p^{n}} : Φ^{m}x = x} .

Then F is a subfield of 𝔽_{p^{n}}, since Φ^{m} is an automorphism of 𝔽_{p^{n}}:

x, y ∈ F ⟹ Φ^{m}x = x, Φ^{m}y = y
⟹ Φ^{m}(x + y) = x + y, Φ^{m}(xy) = xy
⟹ x + y, xy ∈ F.

But we saw in Chapter 8 that

m | n ⟹ U_{m}(x) | U_{n}(x).

Since U_{n}(x) factorises completely in F, the same must be true of U_{m}(x). In other words, U_{m}(x) has p^{m} roots in 𝔽_{p^{n}}, ie

∥F ∥ = p^{m}.

In conclusion, let us see how this fits in with the general remarks on galois theory with which the chapter opened.

A cyclic group C_{n} has just 1 subgroup of order m for each m | n (ie each m allowed by Lagrange’s Theorem). These subgroups are all cyclic themselves. Suppose Φ generates C_{n}. If n = md then the subgroup of order m is generated by Φ^{d}:

C_{m} = {1, Φ^{d}, Φ^{2d}, …, Φ^{(m−1)d}} .

According to the prescription of galois theory this corresponds to the subfield

K = {x ∈ 𝔽_{p^{n}} : Φ^{d}x = x}
= {x ∈ 𝔽_{p^{n}} : x^{p^{d}} = x}
= 𝔽_{p^{d}}.

Thus we have a one-one correspondence between subfields and subgroups:

𝔽_{p^{m}} ⟷ C_{n/m}.

Notice that under this correspondence, the larger the subfield the smaller the subgroup: if K ⟷ S, K′ ⟷ S′,

K ⊂ K′ ⟹ S ⊃ S′.

It follows from this that the Galois correspondence sends intersections into joins, and vice versa:

K ∩ K′ ⟷ ⟨S, S′⟩, ⟨K, K′⟩ ⟷ S ∩ S′.

(The join ⟨K, K′⟩ of 2 subfields K, K′ is the smallest subfield containing both K and K′; Similarly the join ⟨S, S′⟩ of 2 subgroups S, S′ is the smallest subgroup containing both S and S′.)

Concretely, if 𝔽_{p^{n}} exists, and d | n, e | n then we can regard 𝔽_{p^{d}} and 𝔽_{p^{e}} as subfields of 𝔽_{p^{n}}:

𝔽_{p^{d}}, 𝔽_{p^{e}} ⊂ 𝔽_{p^{n}}.

It follows from the galois correspondence that

𝔽_{p^{d}} ∩ 𝔽_{p^{e}} = 𝔽_{p^{gcd(d,e}}), ⟨𝔽_{p^{d}}, 𝔽_{p^{e}}⟩ = 𝔽_{p^{lcm(d,e}}).

10–5

Summary: A finite field has just one subfield of each allowed size:

𝔽_{p^{m}} ⊂ 𝔽_{p^{n}} ⟺ m | n.

10–6

Wedderburn’s Theorem

� F WE RELAX THE CONDITION that multiplication should be commutative, but retain all the other laws of arithmetic, we are left with the axioms for a skew-field or division-algebra. (We shall use the term skewfield.) Note that with this definition, fields (ie commutative fields) are

also skew-fields.

The most familiar example of a non-commutative skew-field is furnished by the quaternions

ℍ = {t + xi + yj + zk : t, x, y, z ∈ ℝ},

with multiplication defined by

i^{2} = j^{2} = k^{2} = −1, ij = −ji = k, jk = −kj = i, ki = −ik = j.

In fact one can show that the only finite-dimensional skew-fields over ℝ are: ℝ itself, the complex numbers ℂ, and the quaternions ℍ.

Theorem 6. Every finite skew-field is commutative.

Proof. Suppose S is a finite skew-field. Let F be the centre of S, ie

F = {z ∈ S : zs = sz for all s ∈ S}.

We have to prove in effect that F = S.

To this end we assume that F ≠ S; we shall show that this leads to a contradiction. We do this by ‘counting conjugates’ in the multiplicative group

S^{×} = S − {0}.

Let

∥F ∥ = q = p^{m}.

Just as in the commutative case, in Chapter 3, we can regard S as a vector space over F. As there, we deduce that

∥S∥ = ∥F ∥^{n},

where n = dim_{F} S.

Recall that 2 elements h, k of a finite group G are said to be conjugate (and we write h ∼ k) if there is an element g ∈ G such that

k = ghg^{−1}.

Conjugacy is an equivalence relation; so G is partitioned into conjugacy classes.

11–1

Lemma 10. Suppose G is a finite group; and suppose g ∈ G. Then the number of elements conjugate to g is

\frac{∥G∥}{∥Z(g)∥},

where

Z(g) = {z ∈ G : zg = gz}

Proof of Lemma. Each element x ∈ G defines a conjugate xgx^{−1} of g. We shall see that each conjugate arises just ∥Z(g)∥ times in this way.

Suppose h ∼ g, say

h = x_{0}gx_{0}^{−1}.

Then

xgx^{−1} = h = x_{0}gx_{0}^{−1} ⟺ x_{0}^{−1}xg = gx_{0}^{−1}x
⟺ x_{0}^{−1}x ∈ Z(g)
⟺ x ∈ x_{0}Z(g).

Thus just ∥Z(s)∥ elements x ∈ G give rise to h ∼ g. Since this holds for each conjugate of g, the number of conjugates is

\frac{∥G∥}{∥Z(g)∥}.

We apply this result with G = S^{×}.

Lemma 11. Suppose s ∈ S. Then

Z(s) = {z ∈ S : zs = sz}

is a sub-skew-field of S.

Corollary 6. With the same notation,

∥Z(s)∥ = q^{d}

for some d | n

Proof of Lemma. Regarding Z(s) as a skew-field over F, we see that

∥Z(s)∥ = q^{d}

If s = 0 the result is trivial. Suppose not; then s ∈ S^{×}, and Z(s)^{×} is a subgroup of S^{×}. Hence, by Lagrange’s Theorem,

q^{d} − 1 | q^{n} − 1.

As we have already seen, this implies that

d | n.

(For on dividing n by d, say n = md + r (where 0 ≤ r < d), we have

q^{n} − 1 = q^{md+r} − 1 = q^{r}(q^{m}d − 1) + (q^{r} − 1).

Thus

q^{d} − 1 | q^{n} − 1, q^{d} − 1 | q^{md} − 1 ⟹ q^{d} − 1 | q^{r} − 1.

But that is impossible unless r = 0, since q^{d} − 1 > q^{r} − 1.)

11–2

Proof of Lemma. We can regard S as a vector space over the skew-field Z(s). Usually we consider linear algebra over a commutative field; but the fundamental theory—the notions of dimension and basis—extends to vector spaces over a skewfield. In particular, if

dim_{Z(s)} S = e

then

q^{n} = ∥S∥ = ∥Z(s)∥^{e} = q^{de},

and so n = de, ie

d | n.

Lemma 12. The number of elements conjugate to s ∈ S^{×} is

\frac{q^{n} − 1}{q^{d} − 1}

for some d | n.

Proof of Lemma. The number of elements conjugate to s is

\frac{∥S^{×}∥}{∥Z(s)^{×}∥} = \frac{q^{n} − 1}{q^{d} − 1}

by our last result.

An element s ∈ S^{×} lies in a conjugacy class by itself if and only if s ∈ F^{×}. Thus there are just q − 1 such elements. Each of the remaining conjugacy classes contains

\frac{q^{n} − 1}{q^{d} − 1}

elements, for some d | n (d ≠ n).

So counting the elements in the various conjugacy classes gives an equation of the form

q^{n} − 1 = q − 1 + \frac{q^{n} − 1}{q^{d_{1}} − 1} + \frac{q^{n} − 1}{q^{d_{2}} − 1} + · · · .

We are going to show that all the fractions

\frac{q^{n} − 1}{q^{d} − 1}

share a common factor f > 1, which also divides q^{n} − 1. It will follow that

f | q − 1.

But that, as we shall see, is impossible since f > q. We thus arrive at a contradiction.

Definition 8. Suppose n is a positive integer. Let

ω = e^{\frac{2πi}{n}} .

Then the cyclotomic polynomial C_{n}(x) is defined to be

C_{n}(x) = ∏_{0<i<n, gcd(i,n)=1}(x − ω^{i}).

Thus C_{n}(x) is a polynomial of degree ϕ(n) (where ϕ(n) is Euler’s function).

11–3

Lemma 13. For each n > 0,

x^{n} − 1 = ∏_{d|n} C_{d}(x).

Proof of Lemma. We know that

x^{n} − 1 = ∏_{0≤i<n}(x − ω^{i}).

We divide the factors x − ω^{i} according to the value of gcd(i, n).

Suppose n = de. Then

gcd(i, n) = d ⟺ i = dj, gcd(j, e) = 1, 0 ≤ j < e.

Thus

∏_{gcd(i,n)=d,0≤i<n}(x − ω^{i}) = ∏_{gcd(j,e)=1,0≤j<e}(x − σ^{j}),

where

σ = ω^{d} = e^{\frac{2πi}{e}} .

In other words,

∏_{gcd(i,n)=d,0≤i<n}(x − ω^{i}) = C_{e}(x).

We conclude that

x^{n} − 1 = ∏_{d|n} C_{\frac{n}{d}} (x).

Since \frac{n}{d} runs over the factors of n as d does, we can rewrite our last result as

x^{n} − 1 = ∏_{d|n} C_{d}(x).

Corollary 7. The cyclotomic polynomial C_{n}(x) has integer coefficients.

Proof of Lemma. We argue by induction on n. Suppose the result true of C_{m}(x) for all m < n.

We have

C_{n}(x) = \frac{x^{n} − 1}{∏_{d|n,d≠n} C_{d}(x)}.

Each cyclotomic polynomial is evidently monic, ie has leading coefficient 1. But if we divide f(x) by g(x), where both f(x) and g(x) have integer coefficients and g(x) is monic, say

f(x) = q(x)g(x) + r(x) (deg r(x) < deg g(x)),

then both q(x) and r(x) have integer coefficients. (This is clear if we derive q(x) and r(x) by repeatedly reducing the degree of f(x) by subtracting terms of the form ax^{r}g(x).)

Since by our inductive hypothesis the factors C_{d}(x) have integer coefficients, and each is monic, the same is true of their product. Hence C_{n}(x), as the quotient of x^{n} − 1 by this product, also has integer coefficients.

11–4

Example 6. We have

C_{1}(x) = x − 1
C_{2}(x) = \frac{x^{2} − 1}{x − 1} = x + 1
C_{3}(x) = \frac{x^{3} − 1}{x − 1} = x^{2} + x + 1
C_{4}(x) = \frac{x^{4} − 1}{C_{1}(x)C_{2}(x)} = \frac{x^{4} − 1}{(x − 1)(x + 1)} = x^{2} + 1
C_{5}(x) = \frac{x^{5} − 1}{x − 1} = x^{4} + x^{3} + x^{2} + x + 1
C_{6}(x) = \frac{x^{6} − 1}{(x − 1)C_{2}(x)C_{3}(x)} = \frac{x^{6} − 1}{(x − 1)(x + 1)(x^{2} + x + 1} = \frac{x^{6} − 1}{(x + 1)(x^{3} − 1)} = x^{2} − x + 1.

Lemma 14. If d | n (d ≠ n) then

C_{n}(q) | \frac{q^{n} − 1}{q^{d} − 1}.

Proof of Lemma. Let

\frac{x^{n} − 1}{x^{d} − 1} = f(x).

Then f(x) has integer coefficients.

We know that

C_{n}(x) | f(x).

It follows on substituting x = q that

C_{n}(q) | f(q),

ie

C_{n}(q) | \frac{q^{n} − 1}{q^{d} − 1}

for all d | n (d ≠ n).

Thus we see that the number of elements in each conjugacy class in S^{×} − F^{×} is divisible by

f = C_{n}(q).

Since C_{n}(q) | q − 1, we conclude that

C_{n}(q) | q − 1.

But

C_{n}(q) = ∏_{gcd(i,n)=1}(q − ω^{i})

and so

|C_{n}(q)| = ∏ |q − ω^{i}| ≥ (q − 1)^{ϕ(n)},

since

|q − ω^{i}| ≥ q − 1.

Moreover there is equality only if each factor is q − 1, which is the case only if n = 1. Thus if n ≠ 1,

|C_{n}(q)| > q − 1.

11–5

But this contradicts our assertion that

C_{n}(q) | q − 1.

We conclude that our original hypothesis is untenable, ie F = S, and so S is commutative.

Summary: There are no ‘finite quaternions’; every finite skew-field is commutative.

11–6

Existence of 𝔽_{p^{n}}

� E CLAIMED at the outset that finite fields abound in nature. But to date, apart from the prime fields 𝔽_{p} we knew about anyway, we have only come up with a couple of trivial examples. It is surely time to ‘put up or shut up’!

We shall see in the next two Sections how finite fields can arise in two contexts— in group representation theory, and in the theory of algebraic numbers.

Unfortunately, it does not seem possible in either case to prove that every finite field arises in this way, without delving deeply into one theory or the other.

We are therefore forced—against out natural inclination—to demonstrate the existence of 𝔽_{p^{n}} by construction. This we carry out in Sections 3 and 4.

So for the first 2 Sections that follow, we are in ‘waffle mode’. The results we quote are not required for the theory that follows; and the discussion can be ignored without danger.

12.1 Looking for 𝔽_{p^{n}}: 1. Among group representations

How do fields—or skew-fields— arise ‘naturally’?

One way is as the endomorphism ring of a simple object in an abelian category. If that sounds highfalutin, a concrete example should make it clearer.

Suppose G is a finite group. Recall that a representation α of G in a finitedimensional vector space V is defined by an action of G on V, ie a map

G × V → V : (g, v) ↦ gv,

satisfying the conditions:

1. (gh)v = g(hv);

2. ev = v;

3. g(u + v) = gu + gv;

4. g(λv) = λ(gv).

We say that the space V, with the action of G on it, constitutes a G-space. If U, V are 2 G-spaces, a map t : U → V is said to be a G-map if it preserves the action of G, ie

t(gv) = g(tv)

for all v ∈ V and all g ∈ G. (The category of G-spaces and G-maps is an example of an abelian category—abelian because maps u, v : U → V can be added.)

12–1

The representation α of G in V is said to be simple (or irreducible) if no proper subspace of U ⊂ V is stable under G, ie

gu ∈ U for all g ∈ G, u ∈ U ⟹ U = {0} or V.

Suppose α is a representation of G in the vector space V over the field K. Then the G-maps t : V → V form a ring E(α), the endomorphism-ring of α (or V). This ring is not in general commutative, but it has an identity element 1.

Now suppose α is simple. In that case E(α) is a skew-field. For suppose t ∈ E(α), ie t is a G-map

t : V → V.

It is readily verified that both

ker t = {v ∈ V : tv = 0} and im t = {v ∈ V : v = tu for some u ∈ V }

are stable subspaces of V. Since α is simple, this implies that

ker t = {0} or V, im t = {0} or V.

But ker t = V and im t = 0 each imply that t = 0. Thus if t ≠ 0,

ker t = 0, im t = V.

In other words, t is both injective and surjective. This implies that t is invertible, ie there exists a G-map u : V → V such that tu = 1. Thus every element t ≠ 0 in E(α) is invertible, ie E(α) is a skew-field.

This skew-field contains the scalar field:

K ⊂ E(α).

Moreover, E(α) is a finite-dimensional vector space over K. For E(α) is a subset of the space hom(V, V) of all linear maps t : V → V, and so

dim_{K} E(α) ≤ dim hom(V, V) = (dim V)^{2}.

In other words, E(α) is a finite-dimensional division-algebra over K.

In the familiar case, where K = ℂ and we are dealing with representations over the complex numbers, it follows that

E(α) = K.

For since ℂ is algebraically-closed the only finite-dimensional division algebra over ℂ is ℂ itself. This is the well-known Schur’s Lemma: In a simple representation, the only linear maps t : V → V commuting with all elements of G are the multiplies of the identity. In matrix terms,

T A(g) = A(g)T for all g ∈ G ⟹ T = λI.

But this is far from the case if K is finite, say K = P = 𝔽_{p}. In this case,

E(α) = 𝔽_{p^{n}},

where in general n > 1.

So we have a prescription for finding finite fields: Take a simple representation (of which there is an enormous choice), and determine E(α).

12–2

Unfortunately, this is not a practical way of showing that 𝔽_{p^{n}} exists for all prime powers p^{n}, as we would have to delve into representation theory too deeply. However, it is easy enough to see that if 𝔽_{p^{n}} exists then it arises in this way!

To see this, suppose 𝔽_{q} exists, where q = p^{n}. Consider the cyclic group

C_{q−1} = 𝔽_{q}^{×}.

This has a natural representation, ρ say, in 𝔽_{q}, regarded as an n-dimensional vector space over P = 𝔽_{p}:

(g, α) ↦ gα (g ∈ 𝔽_{q}^{×}, α ∈ 𝔽_{q}).

It is easy to see that this representation ρ is simple. For suppose U is a proper subspace of 𝔽_{q}. Choose any element α ≠ 0 in U. Then

g = α^{−1} ∈ G ⟹ gα = 1 ∈ U
⟹ g · 1 = g ∈ U

for all g ∈ 𝔽_{q}^{×}. Thus U = 𝔽_{q}.

On the other hand, suppose α ∈ 𝔽_{q}. Let

μ_{α} : 𝔽_{q} → 𝔽_{q}

be the map defined by multiplication by α:

μ_{α}(x) = αx.

This map evidently commutes with the action of C_{q−1}. Thus

μ_{α} ∈ E(ρ).

So we have a natural injection

𝔽_{q} ⊂ E(α).

In fact it is easy to see that every endomorphism γ ∈ E(α) arises in this way. For

γ(1) = α ⟹ γ = μ_{α}.

Thus we may say that

E(α) = 𝔽_{q}.

We have seen therefore that every finite field F does arise in this way—as the endomorphism ring of a simple representation over a prime field.

But as we have already pointed out, this is far from proving that 𝔽_{p^{n}} exists for all p^{n}!

12.2 Looking for 𝔽_{p^{n}}: 2. In number theory

We know that

𝔽_{p} = ℤ/(p).

It is natural to ask if the other non-prime finite fields can be constructed in the same way, taking some other ring in place of the integers ℤ.

A concrete example will show what we mean. Let ℤ[i] denote the ring of gaussian integers:

ℤ[i] = {m + ni : m, n ∈ Z}.

12–3

The number 2 is no longer prime in ℤ[i]:

2 = (1 + i)(1 − i).

Each of these factors has remainder field 𝔽_{2}, eg

Z[i]/(1 + i) = 𝔽_{2}.

For modulo 1 + i,

m + ni ≡ \{ \begin{matrix}0 & if m + n is even, \\ 1 & if m + n is odd. \end{matrix}

On the other hand, 3 remains prime in ℤ[i], and

ℤ[i]/(3) = 𝔽_{3^{2}}.

In fact, an odd prime p remains prime in ℤ[i] if p ≡ 3 mod 4, and splits if p ≡ 1 mod 4. Thus

ℤ[i]/(p) = 𝔽_{p^{2}} if p ≡ 3 mod 4.

ℤ[i] is an example of an algebraic integer ring. These form the subject matter of algebraic number theory, and have been much studied—the initial impetus arising from attempts to prove Fermat’s Last Theorem. It would take us too far out of our way to go into the theory here. But in fact every finite field 𝔽_{p^{n}} does arise in this way, with the proviso that instead of prime elements one really has to consider prime ideals. The 2 rings ℤ and ℤ[i] are both principal ideal domains, in which every ideal is of the form (θ), consisting of all multiples of some generator θ. In such a case there is no real distinction between elements and ideals. But in general the Fundamental Theorem of Arithmetic, according to which each n ∈ ℕ is expressible in the form

n = p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{r}^{e_{r}},

and on which all depends, remains true only in the realm of ideals.

12.3 Extension fields

It is time to return to mathematical mode. Proposition 14. Suppose F is a finite field, with prime subfield P; and suppose α ∈ F. Then there is a smallest subfield K ⊂ F containing α; K consists of all elements expressible in the form f(α), where f(x) ∈ P [x]:

K = {f(α) : f(x) ∈ P [x]}.

Proof. Any intersection of subfields is itself a subfield. So there is certainly a smallest subfield containing α, namely the intersection K of all subfields containing α.

Clearly

α ∈ K ⟹ f(α) ∈ K

for all polynomials f(x) ∈ P [x].

The result will therefore follow if we can show that the set L of elements of the form f(α) forms a field. This set L is evidently closed under addition, subtraction and multiplication. It only remains to show that it is closed under division by non-zero elements.

Lemma 15. A subset S ⊂ G of a finite group G closed under multiplication is necessarily a subgroup.

12–4

Proof of Lemma. We have to show that

s ∈ S ⟹ s^{−1} ∈ S.

By Lagrange’s Theorem,

s^{n} = 1,

where n = ∥G∥. Thus

s^{−1} = s^{n−1} = s · s ⋯ s ∈ S.

Applying this result to the subset L^{×} = L − {0}, we conclude that L^{×} is a subgroup of F^{×}. But this implies that L is a subfield of F, and so L = K.

Proposition 15. If the minimal polynomial of α ∈ F has degree d, then the smallest subfield K ⊂ F containing α contains p^{d} elements:

K = 𝔽_{p^{d}}.

Proof.

Lemma 16. Suppose F is a finite field, with prime subfield P; and suppose α ∈ F has minimal polynomial m(x) ∈ P [x]. If f(x), g(x) ∈ P [x] then

f(α) = g(α) ⟺ m(x) | f(x) − g(x).

Proof of Lemma. This follows at once from the fact that

f(α) = 0 ⟺ m(x) | f(x).

Suppose f(x) ∈ P [x]. Dividing f(x) by m(x),
f(x) = m(x)q(x) + r(x) (deg r(x) < d).

By the Lemma,

f(α) = r(α).

Thus each element β ∈ K is expressible in the form

β = c_{0} + c_{1}α + c_{2}α^{2} + ⋯ + c_{d−1}α^{d−1} (c_{i} ∈ P).

Furthermore, the Lemma shows that this expression is unique.

It follows that the d elements

1, α, α^{2}, …, α^{d−1}

form a basis for K as a vector space over P. Thus

dim_{P} K = d,

and so

∥K∥ = p^{d}.

Suppose p(x) ∈ P [x] is a prime polynomial. If there is an extension field K ⊃ P containing a root α of p(x), the Proposition above shows us how it is constructed. Now we must try to turn analysis into synthesis.

12–5

Theorem 7. Suppose m(x) ∈ P [x] is a prime polynomial over the prime field P = 𝔽_{p}. Then there exists a finite field F of characteristic p, and an element α ∈ F, such that α has minimal polynomial m(x);

Proof. The last proposition tells us how to construct F. Each polynomial f(x) ∈ P [x] defines an element f̄ ∈ F; and

f̄ = ḡ ⟺ m(x) | f(x) − g(x) (f(x), g(x) ∈ P [x]).

In other words

F = P [x]/ (m(x)) .

More precisely, the elements of F consist of the equivalence classes in P [x] under the equivalence relation

f(x) ≡ g(x) if m(x) | f(x) − g(x).

Addition, subtraction and multiplication of elements of F, ie classes in P [x], is defined by taking representatives of these classes, adding, subtracting or multiplying them, and returning the class of the result. The resulting classes are independent of the choice of representatives, since eg

m(x) | f_{1}(x) − f_{2}(x), m(x) | g_{1}(x) − g_{2}(x) ⟹ m(x) | f_{1}(x)g_{1}(x) − f_{2}(x)g_{2}(x).

We have constructed a ring F = P [x]/ (m(x)). It remains to show that F is in fact a field. Suppose f̄ ∈ F; and suppose f̄ ≠ 0, ie

m(x) |̸ f(x).

Then

gcd (f(x), m(x)) = 1;

for the only factor of m(x) apart from 1 is m(x) itself.

It follows that we can find a(x), b(x) ∈ P [x]—for example, by the euclidean algorithm—such that

a(x)f(x) + b(x)m(x) = 1.

But this implies that

m(x) | a(x)f(x) − 1,

and so by definition

āf̄ = 1.

Thus f̄ is invertible in F. Therefore F is a field.

Consider the polynomial

i(x) = x,

and the corresponding element ī ∈ F. From the definition of multiplication in F,

ī^{2} = \overline{x^{2}}, ī^{3} = \overline{x^{3}},

etc. More generally, for any polynomial f(x) ∈ P [x],

f \binom{}{ī} = \overline{f(x)}.

In particular

m \binom{}{ī} = \overline{m(x)} = 0.

Thus m(x) has a root in the field F, namely ī.

12–6

12.4 Constructing 𝔽_{p^{n}}

Theorem 8. For each prime power p^{n} there exists a field 𝔽_{p^{n}} containing p^{n} elements.

Proof. We may assume by induction that there exist fields 𝔽_{p^{m}} containing p^{m} elements for all m < n.

Consider the prime factorisation of the universal polynomial

U_{n}(x) ≡ x^{p^{n}} − x = f_{1}(x)f_{2}(x) … f_{r}(x)

over the prime field P = 𝔽_{p}.

Lemma 17. At least one of the factors f(x) = f_{i}(x) is not a factor of U_{m}(x) for any m | n:

f(x) | x^{p^{n}} − x, f(x) |̸ x^{p^{m}} − x

if m | n, m < n.

Proof of Lemma. Notice that if 𝔽_{p^{n}} exists, and α is any element of 𝔽_{p^{n}} not in any proper subfield—for example, α could be any primitive element of 𝔽_{p^{n}}—then its minimal polynomial m(x) will satisfy the lemma.

But without this assumption, a crude counting argument suffices. For each m | n, the sum of the degrees of all prime polynomials dividing U_{m}(x) cannot exceed the degree of U_{m}(x):

∑_{f(x)|U_{m}(x)} deg f(x) ≤ p^{m}.

Summing this over all factors m of n apart from n itself,

∑_{f(x)|U_{m}(x), m|n, m<n} deg f(x) ≤ ∑_{m|n, m<n} p^{m}
≤ ∑_{m<n} p^{m}
= \frac{p^{n} − 1}{p − 1}
< p^{n}.

since

∑_{f(x)|U_{n}(x)} deg f(x) = p^{n},

it follows that at least one factor f(x) of U_{n}(x) divides no U_{m}(x).

Now let F = P [x]/f(x) be the field extension corresponding to such a factor f(x), as defined above. Then F = 𝔽_{p^{m}} for some m. We must show that m = n.

As we saw, F contains an element α satisfying f(α) = 0. Since f(x) | U_{n}(x) it follows that

U_{n}(α) = 0.

On the other hand, since α ∈ 𝔽_{p^{m}},

U_{m}(α) = 0.

It follows that α satisfies

gcd (U_{n}(x), U_{m}(x)) = U_{d}(x),

12–7

where d = gcd(n, m). Now f(x) is the minimal polynomial of α. Hence

f(x) | U_{d}(x).

Since d | n, this contradicts the defining property of f(x), unless d = n.

But now we have constructed a field F = 𝔽_{p^{m}}, where n | m. It follows that F has a subfield 𝔽_{p^{n}} containing p^{n} elements.

Summary: There exists one and only one field 𝔽_{p^{n}} containing p^{n} elements, for each prime power p^{n}.

12–8

Prime Polynomials over a Prime Field

� S WE HAVE SEEN (particularly in the last chapter), there is an intimate relation between the finite fields 𝔽_{p^{n}} of characteristic p and polynomials— in particular prime polynomials—over the prime field P = 𝔽_{p}. The following result summarises the relation.

Proposition 16. Suppose α ∈ 𝔽_{p^{n}}. Then the minimal polynomial of α over P = 𝔽_{p} is a prime polynomial of degree d | n.

Conversely, if p(x) is a prime polynomial of degree d in P [x] then the roots of p(x) lie in 𝔽_{p^{n}} if and only if d | n.

Proof. Let m(x) be the minimal polynomial of α ∈ 𝔽_{p^{n}}. Suppose deg m(x) = d. Let K be the smallest subfield containing α. Then

dim_{P} K = d,

where P = 𝔽_{p}. In other words,

K = 𝔽_{p^{d}}.

But since K ⊂ 𝔽_{p^{n}} this implies that

d | n.

Conversely, suppose p(x) is a prime polynomial of degree d over P. By the construction of an algebraic extension in the last Chapter, we can find a field F ⊃ P in which p(x) has a root α. (In fact, as we saw, this means that p(x) factorises completely in F.)

Let K be the smallest subfield containing α. As we just saw

K = 𝔽_{p^{d}}.

It follows that α satisfies the universal equation

U_{d}(x) = 0.

Hence

p(x) | U_{d}(x).

But if d | n,

U_{d}(x) | U_{n}(x)

Thus

p(x) | U_{n}(x),

and so p(x) factorises completely in 𝔽_{p^{n}}.

13–1

Corollary 8. Let

U(x) ≡ x^{p^{n}} − x

over P = 𝔽_{p}. Then the prime factorisation of U(x) takes the form

U(x) = ∏_{deg m(x)|n} m(x),

where m(x) runs over all prime polynomials of degree d | n over P.

Corollary 9. If Π(n) = Π_{p}(n) denotes the number of prime polynomials of degree n over the prime field P = 𝔽_{p}, then

∑_{d|n} dΠ(d) = p^{n}.

Proof. This follows from the previous Corollary on comparing degrees.

Corollary 10. The number of prime polynomials of degree n over P = 𝔽_{p} is given by

Π(n) = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) d^{n},

where μ(n) is Möbius’ function:

μ(n) = \{ \begin{matrix}0 & if n has a repeated prime factor \\ (−1)^{e} & if n has e distinct prime factors. \end{matrix}

Proof. This follows from the previous Corollary on applying Möbius’ inversion formula:

F (n) = ∑_{d|n} f(d) ⟹ f(n) = ∑_{d|n} μ (\frac{n}{d}) F (d).

Example 7. The number of prime polynomials of degree 6 over P = 𝔽_{2} is

Π(6) = Π_{2}(6) = \frac{1}{6} (μ(1)2^{6} + μ(2)2^{3} + μ(3)2^{2} + μ(6)2^{1})
= \frac{1}{6} (2^{6} − 2^{3} − 2^{2} + 2^{1})
= \frac{54}{6}
= 9.

In determining these 9 polynomials, note that if

p(x) = c_{0} + c_{1}x + c_{2}x^{2} + c_{3}x^{3} + c_{4}x^{4} + c_{5}x^{5} + c_{6}x^{6}

is a prime polynomial of degree 6 then

1. The first and last coefficients c_{0} and c_{6} must not vanish:

c_{0} = c_{6} = 1.

2. The sum of the coefficients must be non-zero, or else 1+x would divide p(x):

c_{0} + c_{1} + c_{2} + c_{3} + c_{4} + c_{5} + c_{6} = 1.

13–2

This leaves just 16 possibilities.

Suppose p(x) is prime. Then so is the polynomial obtained by taking the coefficients in reverse order

p̃(x) = x^{6}p (\frac{1}{x}) .

For it is easy to verify that if p(x) factorises so does p̃(x).

So the prime polynomials of degree 6 occur in pairs, except for those which are ‘symmetrical’, ie p̃(x) = p(x). There are just 4 symmetrical polynomials among the 16 we are examining, namely

1 + x^{3} + x^{6}, 1 + x + x^{3} + x^{5} + x^{6}, 1 + x^{2} + x^{3} + x^{4} + x^{6}, 1 + x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6}.

So 1 or 3 of these is prime; and then 4 or 3 of the remaining 6 pairs are prime.

If one of our 16 polynomials is not prime then it must have a prime factor of degree 2 or 3. (We have excluded the prime factors x and 1 + x of degree 1.)

The number of prime polynomials of degree 2 is

Π(2) = \frac{1}{2} (2^{2} − 2^{1}) = 1,

while

Π(3) = \frac{1}{3} (2^{3} − 2^{1}) = 2.

Given that a prime polynomial of degree > 1 over 𝔽_{2} must have an odd number of non-zero coefficients, as we remarked above, we see that the prime of degree 2 must be

q(x) = 1 + x + x^{2},

while the two primes of degree 3 are

r(x) = 1 + x + x^{3}, s(x) = 1 + x^{2} + x^{3}.

If one of our 16 polynomials is not prime, then it is either divisible by q(x) or else it is the product of 2 primes of degree 2, ie it is one of

r(x)^{2} = 1 + x^{2} + x^{6},
s(x)^{2} = 1 + x^{4} + x^{6},
r(x)s(x) = 1 + x + x^{2} + x^{3} + x^{4} + x^{5} + x^{6}.

It is easy to see if a polynomial p(x) is divisible by q(x), since

x^{3} − 1 = (x − 1)(x^{2} + x + 1),

and therefore

x^{3} ≡ 1 mod q(x).

So, for example,

p(x) = x^{6} + x^{5} + x^{2} + x + 1 ≡ 1 + x^{2} + x^{2} + x + 1 ≡ x mod q(x),

and so

q(x) |̸ p(x).

Dividing the 4 symmetrical polynomials of degree 6 by each of these in turn, we see that just 1 is prime, namely the first:

1 + x^{3} + x^{6}.

13–3

Thus just 4 out of the 6 pairs of asymmetric polynomials are prime. We can exclude the pair

(1 + x + x^{3})^{2} = 1 + x^{2} + x^{6}, (1 + x^{2} + x^{3})^{2} = 1 + x^{4} + x^{6}.

Just one non-prime pair more to go!

It is evident that

(1 + x + x^{2})^{3}, (1 + x + x^{3})(1 + x^{2} + x^{3})

are both symmetric. It follows that the last non-prime of degree 6 must be the product of 1 + x + x^{2} and a prime of degree 4.

Now

Π(4) = \frac{1}{4} (2^{4} − 2^{2}) = 3.

The 3 prime polynomials of degree 4 are

1 + x + x^{4}, 1 + x^{3} + x^{4}, 1 + x + x^{2} + x^{3} + x^{4}.

So our last non-prime pair is

(1 + x + x^{2})(1 + x + x^{4}) = 1 + x^{3} + x^{4} + x^{5} + x^{6}

and its ‘conjugate’

(1 + x + x^{2})(1 + x^{3} + x^{4}) = 1 + x + x^{2} + x^{3} + x^{6}.

So if we represent the polynomial by its coefficients as a sequence of bits,

c_{0} + c_{1}x + c_{2}x^{2} + c_{3}x^{3} + c_{4}x^{4} + c_{5}x^{5} + c_{6}x^{6} ⟷ (c_{0}c_{1}c_{2}c_{3}c_{4}c_{5}c_{6}),

then our 9 prime polynomials of degree 6 are

(1000011) (1100001)
(1000101) (1010001)

(1001001)

(1001011) (1101001)
(1001101) (1011001)

Definition 9. Suppose p(x) is a prime polynomial of degree d over P = 𝔽_{p}. Let α be a root of p(x) in 𝔽_{p^{d}}. Then p(x) is said to be primitive if α is primitive.

Proposition 17. Suppose p(x) is a prime polynomial of degree d over P = 𝔽_{p}; and suppose α ∈ 𝔽_{p^{d}} is a root of p(x). Then the order of α in 𝔽_{p^{d}}^{×} is equal to the order of x modulo p(x), ie the least integer e > 0 such that

p(x) | x^{e} − 1.

Proof. Suppose

α^{e} = 1.

Then α satisfies the equation

x^{e} − 1 = 0.

But p(x) is the minimal polynomial of α. hence

p(x) | x^{e} − 1,

13–4

or in other words,

x^{e} ≡ 1 mod p(x).

Conversely,

x^{e} ≡ 1 mod p(x) ⟹ p(x) | x^{e} − 1
⟹ α^{e} − 1 = 0
⟹ α^{e} = 1.

Corollary 11. With the same notation, the order of x modulo p(x) divides p^{d} −1.

Corollary 12. Suppose p(x) is a prime polynomial of degree d over P. Then p(x) is primitive if and only if x has order p^{d} − 1 modulo p(x).

Proposition 18. The number of primitive polynomials of degree d is

\frac{ϕ(p^{d} − 1)}{d},

where ϕ(n) denotes Euler’s function.

Proof.

Lemma 18. If α ∈ 𝔽_{q} is primitive, then so are all its conjugates

α, Φα, Φ^{2}α, ….

Proof of Lemma. Suppose Φα is not primitive. In other words Φα had degree d < q − 1. Then

(Φα)^{d} = 1 ⟹ Φ (α^{d}) = 1
⟹ α^{d} = 1,

since Φ is an automorphism.

There are ϕ(p^{d} − 1) primitive elements in 𝔽_{p^{d}}. Each primitive polynomial p(x) of degree d has d of these elements as roots. Thus the number of such polynomials is

\frac{ϕ(p^{d} − 1)}{d}.

Example 8. The number of primitive polynomials of degree 6 over 𝔽_{2} is

\frac{ϕ(2^{6} − 1)}{6} = = \frac{ϕ(63)}{6}
= \frac{ϕ(3^{2})ϕ(7)}{6}
= \frac{3 · 2 · 6}{6}
= 6.

So of our 9 prime polynomials of degree 6, just 6 are primitive and 3 non-primitive.

It is a straightforward matter to establish that if p(x) is primitive then so is its ‘conjugate’ p̃(x). (We leave the proof of this to the reader.) So it follows that

13–5

our symmetric prime of degree 6 cannot be primitive (or there would be an odd number of primitive polynomials). Let us verify this.

It is sufficient, as we have seen, to determine the order of x modulo p(x). If p(x) is primitive this will be 2^{6} − 1 = 63. In any case, it will be a factor of 63.

Taking

p(x) = 1 + x^{3} + x^{6},

we have

x^{6} ≡ x^{3} + 1 mod p(x),

and so

x^{9} ≡ x^{6} + x^{3}
≡ 1.

Thus x has order 9 modulo p(x), and so p(x) is not primitive. (We’ve actually shown that the order divides 9; but since the order of x modulo p(x) is manifestly greater than the degree of p(x), the order must in fact be 9.)

We leave it to the student to determine which of the 4 pairs of asymmetric primes is not primitive.

Summary: The prime polynomials over the P = 𝔽_{p} divide into 2 classes: primitive and non-primitive. We are able to compute both the number of prime polynomials, and the number of primitive polynomials, of a given degree.

13–6

Appendix A

Galois Theory

A.1 The Galois Correspondence

Definition 10. Suppose G is finite group of automorphisms of the field K. Let k be the set of fixed elements under G:

k = {θ ∈ K : gθ = θ for all g ∈ G}.

Then we say that K is a galois extension of k.

We shall show that in this case

1. k is a subfield of K;

2. deg_{k} K is finite;

3. G is the full group of automorphisms of K over k:

G = Aut_{k} K.

It will follow in particular from this that if K is a galois extension of k then we can take G = Aut_{k} K; so the property depends only on K and k (and not on G).

Examples 1. 1. The finite field

K = F_{(}p^{n})

is a galois extension of F_{(}p), with

G = {I, Φ, Φ^{2}, …, Φ^{n−1}},

where Φ is the Frobenius automorphism x ↦ x^{p}.

2. The Gaussian rationals

K = ℚ(i),

ie the field of complex numbers of the form x+yi, where x, y ∈ ℚ, is a galois extension of ℚ, with

G = {I, C},

where C is complex conjugation x + yi ↦ x − yi.

A–1

3. The quadratic number field

K = ℚ(\sqrt{2}),

ie the field of real numbers of the form x + y\sqrt{2}, where x, y ∈ ℚ, is a galois extension of ℚ, with

G = {I, J},

where J is the map x + y\sqrt{2} ↦ x − y\sqrt{2}.

4. The cyclotomic field

K = ℚ(ω),

where ω = e^{2πi/n}, is a galois extension of ℚ; G is the group of ϕ(n) automorphisms of the form

ω ↦ ω^{i},

where gcd(i, n) = 1. Definition 11. Suppose G is a finite group of automorphisms of K. Then For each subgroup S ⊂ G we set

F(S) = {θ ∈ K : gθ = θ for all g ∈ S}.

{1. \atop 2.} For each subfield F ⊂ K we set

S(F) = {g ∈ G : gθ = θ for all θ ∈ F }.

As indicated above, we assume that

k = F(G),

ie k denotes the set of elements left fixed by all the automorphisms in G, Proposition 19. Suppose G is a finite group of automorphisms of K. Then

1. For each subgroup S ⊂ G, F(S) is a subfield of K.

2. For each subfield F ⊂ K, S(F) is a subgroup of G.

3. If S is a subgroup of G then

S ⊂ SF(S);

4. If F is a subfield of K then

F ⊂ FS(F);

5. If S, T are subgroups of G then S ⊂ T ⟹ F(S) ⊃ F(T);

6. If E, F are subfields of K then E ⊂ F ⟹ S(E) ⊃ S(F);

A–2

7. For each subgroup S ⊂ G,

FSF(S) = F(S).

In other words,

FSF = F.

8. For each subfield F ⊂ K,

SFS(F) = S(F).

In other words,

SFS = S.

Proof. All these results are immediate, except perhaps the last two.

For (7) we note that by (3)

S ⊂ SF(S).

Hence

F(S) ⊃ F(SF(S)),

by (5). On the other hand,

F(S) ⊂ FS(F(S)),

on applying (4) with F(S) in place of F.

The last part (8) is proved similarly.

It follows from the last 2 parts of this Proposition that if F = F(S), ie if F is the fixed field of some subgroup S ⊂ G, then

FS(F) = F;

and similarly, if S = S(F), ie if S is the invariant subgroup of some subfield F ⊂ K then

SF(S) = S.

We shall show that every field F between k and K is the fixed field of some subgroup, and every subgroup S ⊂ G is the invariant group of some subfield.

It will follow from this that the mappings

S ↦ F(S), F ↦ S(F)

establish a one-one correspondence between the subgroups of G and the subfields of K containing k. That is the Fundamental Theorem of Galois Theory.

A.2 Towers of Extensions

Proposition 20. Suppose F is a subfield of K containing k,

k ⊂ F ⊂ K;

and suppose deg_{k} F and deg_{F} K are both finite. Then deg_{k} K is finite, and

deg_{k} K = deg_{k} F · deg_{F} K.

A–3

Proof. Let {ϵ_{1}, …, ϵ_{r}} be a basis for F over k; and let {η_{1}, …, η_{s}} be a basis for K over F. Then the rs elements

ϵ_{i}η_{j} (1 ≤ i ≤ r, 1 ≤ j ≤ s)

form a basis for K over k.

For any θ ∈ K is uniquely expressible in the form

θ = ∑_{1≤j≤s} ξ_{j}η_{j},

with ξ_{1}, …, ξ_{s} ∈ F. But now each ξ_{j} is uniquely expressible in terms of the ϵ_{i}:

ξ_{j} = ∑_{1≤i≤r} a_{ij}ϵ_{i},

where a_{ij} ∈ k, giving

θ = ∑_{i,j} a_{ij}ϵ_{i}η_{j},

A.3 Algebraic Extensions

Recall that an element θ ∈ K is said to be algebraic over the subfield k if it satisfies a polynomial equation

x^{n} + c_{1}x^{n−1} + ⋯ + c_{n} = 0

with coefficients c_{i} ∈ k.

We say that K is an algebraic extension of k if every element θ ∈ K is algebraic over k. The algebraic extension K over k is said to be simple if

K = k(α)

for some α ∈ K. If this is so, and m(x) is the minimal polynomial of α over k then

deg_{k} K = deg m(x),

with each element θ ∈ K uniquely expressible in the form

θ = c_{0} + c_{1}α + ⋯ + c_{d−1}α^{d−1},

where d = deg m(x). Proposition 21. An extension of finite degree is necessarily algebraic.

Proof. Suppose deg_{k} K = d; and suppose θ ∈ K. The d + 1 elements

1, θ, θ^{2}, …, θ^{d}

must be linearly dependent over k, ie we can find c_{0}, c_{1}, …, c_{d} ∈ k such that

c_{0} + c_{1}θ + ⋯ + c_{d}θ^{d} = 0.

In other words θ is a root of the polynomial

c_{0} + c_{1}x + ⋯ + c_{d}x^{d} = 0.

Corollary 13. If θ is algebraic over k then the extension k(θ) is algebraic.

A–4

A.4 Conjugacy

We suppose in this Section that G is a finite group of automorphisms of the field K, and that k = F(G). Definition 12. Suppose θ ∈ K. Then the elements gθ(g ∈ G) are called the conjugates of θ.

The argument used in the proof of the following Proposition is frequently encountered in galois theory.

Proposition 22. Suppose θ ∈ K. Let the distinct conjugages of θ be

θ = θ_{1}, θ_{2}, …, θ_{d};

Then the minimal polynomial of θ is

m(x) = (x − θ_{1}) ⋯ (x − θ_{d}).

Proof. Consider the action of the automorphism g ∈ G on m(x). It is easy to see that g simply permutes the factors of m(x):

m^{g}(x) = (x − gθ_{1}) ⋯ (x − gθ_{d})
= (x − θ_{1}) ⋯ (x − θ_{d})
= m(x).

It follows that the coefficients of m(x) are invariant under all g ∈ G, and so lie in the groundfield k:

m(x) ∈ k[x].

Thus m(x) is a polynomial over k satisfied by θ. If M(x) is the minimal polynomial of θ, therefore,

M(x) | m(x).

But on applying the automorphism g ∈ G

M(θ) = 0 ⟹ M(gθ) = 0,

since g leaves the coefficients of M(x) fixed. Thus every conjugate θ_{i} of θ is a factor of M(x), and so

m(x) | M(x).

Hence M(x) = m(x), ie m(x) is the minimal polynomial of θ.

Corollary 14. If θ ∈ K has d distinct conjugates then

d = deg_{k} k(θ).

Recall that the polynomial p(x) is said to be separable if it has distinct roots. We say that θ is separable over k if it is algebraic over k and its minimal polynomial m(x) is separable; and we say that the algebraic extension F of k is separable if every element of F is separable over k.

In characteristic 0 (which is the case we are chiefly interested in), every algebraic element is separable; for if g(x) = gcd(m(x), m′(x)) then g(x) | m(x), and so g(x) = 1.

However, in finite characteristic p this argument may break down, since m′(x) may vanish identically. This happens if (and only if) m(x) contains only powers of x^{p}, say

m(x) = M(x^{p}).

In fact this cannot happen in our case; for we have seen that each element θ ∈ K satisfies an equation over k with distinct roots θ_{i}.

A–5

Corollary 15. K is a separably algebraic extension of k.

Proposition 23. Suppose

F = k(θ),

where θ ∈ K. Then

deg_{k} F · ∥S(F)∥ = ∥G∥.

Proof. Suppose θ has d conjugates. Then

deg_{k} k(θ) = d,

by the Corollary to the last Proposition.

On the other hand

S(F) = {g ∈ G : gθ = θ};

for if g leaves θ fixed then it will leave every element of k(θ) fixed.

Let S = S(F). Then

g_{1}θ = g_{2}θ ⟺ g_{2}^{−1}g_{1}θ = θ
⟺ g_{2}^{−1}g_{1} ∈ S
⟺ g_{1}S = g_{2}S.

This establishes a one-one correspondence between the conjugates of θ and the cosets of S. Hence the number d of conjugates is equal to the number of cosets, ie

d = ∥G∥/∥S∥.

Thus

deg_{k} k(θ) · ∥S∥ = d · ∥S| = ∥G∥,

as required.

A.5 The Correspondence Theorem

Theorem 9. Suppose G is a finite group of automorphisms of the field K; and suppose k = F(G) is the field of fixed elements under G. Then

1. The maps

S ↦ F(S), F ↦ S(F)

establish a one-one correspondence between subgroups S ⊂ G and subfields F ⊂ K containing k.

2. If S and F correspond in this way then

∥S∥ · deg_{k} F = ∥G∥.

3. In particular

deg_{k} K = ∥G∥.

4. Each subfield F is a simple extension of k:

F = k(θ).

5. G is the full group of isomorphisms of K:

G = Aut_{k} K.

A–6

Proof. Let us assume that deg_{k} K < ∞, as is implied by (3). We shall show at the end of the proof that this assumption is justified.

We argue by induction on G. Thus we may assume the result true for all proper subgroups S ⊂ G.

To establish the correspondence we have to show that SF(S) = S for every subgroup S ⊂ G, and FS(F) = F for every subfield F ⊂ K containing k.

Lemma 19. For each subgroup S ⊂ G we have

SF(S) = S.

Proof of Lemma. This follows at once on applying our inductive hypothesis with S in place of G, and k′ = F(S) in place of k. For the last part of the Theorem tells us that S is the full group of automorphisms of Aut_{k′} K).

Lemma 20. Suppose

k ⊂ F, F′ ⊂ K;

and suppose

Θ : F → F′

is an isomorphism over k. Then Θ can be extended to an automorphism of K over k.

Putting the matter the other way round, Θ is the restriction to F of some g ∈ Aut_{k} K.

Proof of Lemma. Suppose θ ∈ K \ F. Let

m(x) = (x − θ_{1}) ⋯ (x − θ_{d}) = x^{d} + γ_{1}x^{d−1} + ⋯ + γ_{d}

be the minimal polynomial of θ over F.

We know that the minimal polynomial of θ over k is of the form

M(x) = (x − g_{1}θ) ⋯ (x − g_{r}θ),

where g_{1}θ, …, g_{r}θ are the distinct conjugates of θ. Since m(x) | M(X), we deduce that (1) the roots of m(x) are distinct, and (2) these roots are all of the form gθ.

Now consider the transform of m(x) under Θ,

m^{Θ}(x) ≡ x^{d} + (Θγ_{1})x^{d−1} + ⋯ + (Θγ_{d}).

Since

m^{Θ}(x) | M^{Θ}(x) = M(x),

we see that m^{Θ}(x) factorises completely in K.

Let θ′ be any root of m^{Θ}(x). We extend Θ to a map

Θ′ : F (θ) → F′(θ′)

as follows. Suppose ϕ ∈ F (θ, say ϕ = p(θ), where p(x) ∈ F [x]. Then

ϕ = p(θ) ↦ ϕ′ = p^{Θ}(θ′).

This is well-defined, since

p(θ) = 0 ⟹ m(x) | p(x) ⟹ m^{Θ}(x) | p^{Θ}(x) ⟹ p^{Θ}(θ′) = 0.

Since Θ′ clearly preserves addition and multiplication, it is an isomorphism extending Θ to F (θ).

A–7

We can extend the isomorphism repeatedly in this way to

F (θ_{1}, …, θ_{r}

until finally we must reach K since we are assuming that deg_{k} K is finite.

As it stands, we only know that this extension is an endomorphism of K. However, a linear transformation t : V → V of a finite-dimensional vector space V is bijective if and only if it is injective (that is, if det t ≠ 0). Thus we have extended the isomorphism Θ to an automorphisms g ∈ Aut_{k} K.

Lemma 21. Suppose

k ⊂ F ⊂ K.

Then

deg_{k} F · ∥S(F)∥ = ∥G∥.

Proof of Lemma. We argue by induction on deg_{k} F. Let us suppose the result holds for F; and suppose θ ∈ K \ F. Let

m(x) = (x − θ_{1}) ⋯ (x − θ_{d})

be the minimal polynomial of θ over F. In the proof of the last Lemma we showed how to construct an isomorphism F (θ) → F (θ_{i}) for each root θ_{i} of m(x). These isomorphisms extend — by the same Lemma — to automorphisms

g_{1}, …, g_{d} ∈ Aut_{F} K = S(F).

Let S = S(F); and suppose g ∈ S. Since g leaves m(x) unchanged, gθ = θ_{i} for some i. It follows that g restricts on F (θ) to one of our d isomorphisms, say the restriction of g_{i}. But then g_{i}^{−1}g leaves θ fixed, and so leaves every element of F′ = F (θ) fixed:

g_{i}^{−1}g ∈ S(F′) = S′,

say. We deduce that

S = g_{1}S′ ∪ ⋯ ∪ g_{d}S′.

Thus

∥S∥ = deg_{F} F′ · ∥S′∥;

and so

deg_{k} F′ · ∥S′∥ = deg_{k} F · deg_{F} F′ · ∥S′∥
= deg_{k} F · ∥S∥
= ∥G∥,

by the inductive hypothesis.

Applying this Lemma with F = K,

deg_{k} K = ∥G∥,

since S(K) = {e}.

Lemma 22. For each subfield F ⊂ K containing k we have

FS(F) = F.

A–8

Proof of Lemma. We know that

F′ = FS(F) ⊃ F,

and that

S(F′) = SFS(F) = S(F).

Thus from the last Lemma,

deg_{k} F′ = \frac{∥F ∥}{∥S(F′)∥} = \frac{∥F ∥}{∥S(F)∥} = deg_{k} F.

Hence

F′ = F,

by Proposition 20.

Lemma 23. Suppose V is a vector space over an infinite field k; and suppose U_{1}, …, U_{r} are subspaces of V. Then

V = ⋃_{1≤i≤r} U_{i} ⟹ V = U_{i}

for some i.

Proof of Lemma. Suppose to the contrary that the U_{i} are all proper subspaces of V. We may suppose r minimal, so that

U_{1} ∪ ⋯ ∪ U_{r−1} ≠ V.

Let

v ∈ V, v ∉ U_{1} ∪ ⋯ ∪ U_{r−1};

and let

w ∈ V, w ∉ U_{r}.

Consider the “line”

u = v + tw (t ∈ k).

This cuts each U_{i} in at most one point; for if there were 2 such points then the whole line would lie in U_{i}. Thus if we choose t to avoid at most r values we can ensure that u = v + tw does not lie in any of the subspaces, contrary to supposition.

Lemma 24. Suppose k ⊂ F ⊂ K. Then F is a simple extension of k:

F = k(θ).

Proof of Lemma. If k is finite, then so is F, and the result follows from the fact that a finite field F is a simple extension of every subfield k ⊂ F, eg F = k(π), where π is a primitive root of F.

We may suppose therefore that k is infinite. By Lemma 22, each subfield F ⊂ K containing k corresponds to the subgroup of S(F) ⊂ G. Thus there can only be a finite number of such subfields.

It follows by the last Lemma that we can find θ ∈ F not belonging to any proper subfield of F containing k. But then k(θ) must be the whole of F:

k(θ) = F.

A–9

Lemma 25. G is the full group of automorphisms of K over k:

G = Aut_{k} K.

Proof of Lemma. By the last Lemma,

K = k(θ).

By Proposition 22 θ has minimal equation

m(x) = (x − g_{1}θ) ⋯ (x − g_{n}θ),

where g_{1}, …, g_{n} ∈ G.

Every automorphism Θ of K over k must send θ into one of these conjugates gθ. But this determines the automorphism completely. Hence Θ = g.

It only remains to show that deg_{k} K is finite. Suppose not. Then we can certainly find θ_{1}, …, θ_{n} such that

deg_{k} k(θ_{1}, …, θ_{n}) > ∥G∥.

Now adjoin all the conjugates mθ_{i} of these elements; and let

F = k(g_{1}θ_{1}, …, g_{m}θ_{n})

be the resulting subfield of K. Every automorphism g ∈ G sends F into itself, since it merely permutes the elements g_{i}θ_{j}. We can therefore apply the Theorem in this case, since deg_{k} F < ∞. But then we conclude that

deg_{k} F ≤ ∥G∥,

contrary to construction.

Corollary 16. Suppose K is a galois extension of k; and suppose F is a subfield of K containing k:

k ⊂ F ⊂ K.

Then K is a galois extension of F.

Corollary 17. Suppose K is a finite extension of k. Then

Aut_{k} K ≤ deg_{k} K,

with equality if and only if the extension is galois.

Proof. First we must show that G = Aut_{k} K is finite. Suppose

K = k(θ_{1}, …, θ_{n}).

Let m_{i}(x) be the minimal polynomial of θ_{i}. Then each automorphism g ∈ G must send θ_{i} into another root gθ_{i} of m_{i}(x). Thus there are only a finite number of choices for each gθ_{i}; and since g is completely determined by the gθ_{i}, there are only a finite number of choices for g.

Now we can apply the Theorem. Let

F = F(G) = {θ ∈ K : gθ = θ for all g ∈ G}.

Then

∥G∥ = deg_{F} K ≤ deg_{k} K,

with equality if and only if F = k, in which case the extension is galois, by definition.

A–10

A.6 Normal Subgroups and Galois Extensions

Proposition 24. Suppose F is a subfield of K containing k:

k ⊂ F ⊂ K.

Then K is sent into itself by every g ∈ G = Aut_{k} K if and only if S(G) is a normal subgroup of G; and if this is so then

Aut_{k} F = \frac{G}{S(F)}.

Proof. We know that

F = k(θ)

for some θ ∈ K, by Theorem 9(5). Let the conjugates of θ be

θ_{1} = θ, θ_{2} = g_{2}θ, …, θ_{d} = g_{d}θ.

The automorphism g ∈ G carries k(θ) into itself if and only if

gθ ∈ k(θ).

But θ and gθ have the same minimal polynomial, and so

deg_{k} k(gθ) = deg_{k} k(θ).

Thus

gθ ∈ k(θ) ⟺ k(gθ) = k(θ).

Now

S (k(θ)) = {h ∈ G : hgθ = gθ}
= {h ∈ G : g^{−1}hgθ = θ}
= gS (k(θ)) g^{−1}.

Thus

k(gθ) = k(θ) ⟺ S (k(gθ)) = S (k(θ)) ⟺ g^{−1}Sg = S,

where S = S(k(θ)). In particular every g ∈ G sends k(θ) into itself if and only if g^{−1}Sg = S for all g, ie S ⊲ G.

In this case, two automorphisms g, h ∈ G induce the same automorphism of F if and only if they map θ into the same element. But

gθ = hθ ⟺ h^{−1}gθ = θ
⟺ h^{−1}g ∈ S
⟺ hS = gS.

Thus the induced automorphisms of F are in one-one correspondence with the cosets of S, ie with the elements of the quotient-group G/S. It follows that

Aut_{k} F = G/S.

We note that these must be all the automorphisms of F over k, by Theorem 9(6).

A–11

A.7 Splitting Fields

Definition 13. The extension F of k is said to be a splitting field for the polynomial p(x) ∈ k[x] if

1. p(x) splits completely in F:

p(x) = (x − θ_{1}) ⋯ (x − θ_{d}) (θ_{i} ∈ F).

2. F is generated by the roots of p(x):

F = k(θ_{1}, …, θ_{d}).

Proposition 25. Suppose K is a splitting field for the separable polynomial p(x). Then K is a galois extension of k.

Proof. Certainly

K = k(θ_{1}, …, θ_{d})

is of finite degree over k, by Proposition 20. Thus we may argue by induction on deg_{k} K.

First let us dispose of the case in which k is finite. In this case K is a galois field

K = F_{(}p^{n});

and we know that F_{(}p^{n}) is a galois extension of all its subfields F_{(}p^{m}) (where m | n).

We may therefore assume that k is infinite. Let F be a minimal subfield of K containing k. Evidently K is the splitting field for p(x) over F. Thus by our inductive hypothesis K is a galois extension of F.

There are 2 cases. Suppose first that there are two (or more) minimal subfields, F_{1} and F_{2}. Then

F(G) ⊂ F_{1} ∩ F_{2} = k.

Hence K/k is galois.

Now suppose F is the unique minimal subfield. Since K/F is galois, K has only a finite number of subfields. By Lemma 23 we can choose ϕ ∈ K not in any of these subfields; and then

K = k(ϕ).

Let m(x) be the minimal polynomial of ϕ.

We can express ϕ as a polynomial in θ_{1}, …, θ_{d}, say

ϕ = f(θ_{1}, …, θ_{d}).

For each permutation π ∈ S_{d}, let

ϕ_{π} = f (θ_{π(1)}, …, θ_{π(d)}) (π ∈ S_{d}).

The coefficients of the product

P (x) = ∏_{π∈S_{d}}(x − ϕ_{π})

are all symmetric functions of θ_{1}, …, θ_{d}, and so lie in k:

P (x) ∈ k[x].

It follows that all the roots of the minimal polynomial of θ, say

m(x) = (x − θ_{1}) … (x − θ_{d}),

all lie in K.

A–12

Lemma 26. Every element θ ∈ K is separable, ie θ is the root of a separable polynomial.

Proof of Lemma. Let

g(x) = gcd(m(x), m′(x)).

Then

g(x) | m(x).

Since m(x) is irreducible, this implies that either g(x) is constant, in which case m(x) is separable, or else m′(x) vanishes identically.

This is impossible in characteristic 0; so we need only consider the case of finite characteristic p.

In that case m′(x) ≡ 0 if and only if m(x) contains only terms with powers x^{pr}; in other words,

m(x) = M(x^{p}) = x^{pr} + c_{1}x^{p(r−1)} + ⋯ + c_{r}.

It is easy to see that the pth powers form a subfield of K, say

K^{p} = {θ^{p} : θ ∈ K}.

Suppose K^{p} ≠ K. If K^{p} = k then

θ_{i}^{p} ∈ k

for each of the roots θ_{i} of the generating polynomial p(x). In other words, θ^{i} satisfies an equation

x^{p} − θ_{i}^{p} ≡ (x − θ_{i})^{p} = 0

over k. But since p(x) is separable, so is the minimal polynomial of θ_{i}. It follows that θ_{i} ∈ k. Since this must hold for all the generators θ_{i}, K = k and the result is trivial.

We may assume therefore that F = K^{p} is a non-trivial subfield of K. Thus we can apply our inductive hypothesis, and deduce that the extension K/K^{p} is galois.

But if θ ∈ K then θ^{p} ∈ K^{p}, and θ has minimal polynomial

x^{p} − θ^{p} ≡ (x − θ)^{p}.

It follows that every automorphism of K over K^{p} will leave θ fixed. Hence

G(K/K^{p}) = {e},

and so the extension K/K^{p} is not galois, contrary to hypothesis.

We have shown that K = k(θ), where the minimal polynomial m(x) of θ splits completely in K into distinct factors:

m(x) = (x − θ_{1}) ⋯ (x − θ_{d}).

For each root θ_{i}, the map

p(θ) ↦ p(θ_{i})

defines an automorphism of K over k. Thus

deg_{K} k = d ≤ ∥ Aut_{k} K∥.

It follows that K is a galois extension of k, by Corollary 2 to Theorem 9.

A–13

Appendix A

The Normal Basis Theorem

As we have seen, we can regard a finite field F as a vector space over its prime subfield P. We often want to construct a basis for this vector space.

The simplest way to choose such a basis is to pick an element α ∈ F whose minimal polynomial has degree n—or equivalently, such that F = P (α). (For example, any primitive root of F will have this property.) For then the elements

{1, α, α^{2}, …, α^{n−1}}

are linearly independent, and so form a basis for F.

However, it is sometimes preferable to use a more specialized basis, namely one consisting of a complete family of conjugates

{γ, γ^{p}, …, γ^{p^{n−1}}}

Such a basis is said to be normal; and the Normal Basis Theorem asserts the existence of normal bases in every finite field.

Theorem 10. There exists an element α ∈ F = F_{(}p^{n}) whose n conjugates

α, πα, π^{2}α, …, π^{n−1}α

form a basis for F over its prime subfield P.

Our proof of this theorem is based on a straightforward but perhaps unfamiliar result from linear algebra.

Suppose

T : V → V

is a linear transformation of the finite-dimensional vector space over the scalar field k. Let m(x) be the minimal polynomial of T.

(Recall that m(x) is the polynomial of least degree satisfied by T, taken with leading coefficient 1. It has the property that

p(T) = 0 ⟺ m(x)|p(x),

as is readily seen on dividing p(x) by m(x):

p(x) = m(x)q(x) + r(x) (deg r(x) < deg m(x))

(Incidentally, there certainly do exist polynomials p(x) such that p(T) = 0. For the space hom(V, V) of all linear maps T : V → V has dimension n^{2}; and so the linear maps

I, T, T^{2}, …, T^{n^{2}}

A–1

must be linearly independent, ie T satisfies an equation of degree ≤ n^{2}. In fact, by the Cayley-Hamilton Theorem T satisfies its own characteristic equation

χ_{T} (x) = det(xI − T);

so the minimal polynomial of T actually has degree ≤ n. But we don’t need this.)

We can extend this notion of minimal polynomial as follows. Suppose v ∈ V. Consider the set of polynomials

I(v) = {f(x) : f(T)v = 0}.

This set is an ideal in the polynomial ring k[x], ie it is closed under addition, and under multiplication by any polynomial in k[x]. It follows—since k[x] is a principle ideal doman—that I(v) consists of all the multiples of a polynomial m_{v}(x). (It is easy to prove this result directly, taking m_{v}(x) to be a polynomial of minimal degree in I(v).) The main properties of this polynial are summarised in

Lemma 27. 1. m_{v}(x)∥m(x) for all v ∈ V.

2. m(x) = lcm_{v∈V} m_{v}(x).

3. If u = f(T)v for some polynomial f(x) then m_{u}(x)∥m_{v}(x).

4. If u, v ∈ V and m_{u}(x), m_{v}(x) are co-prime then

m_{u+v}(x) = m_{u}(x)m_{v}(x).

Proof. 1. Since m(T) = 0, it follows that m(T)v = 0 for all v, and so

m_{v}(x)∥m(x).

2. It follows from the above that

f(x) = lcm_{v∈V} m_{v}(x)

is defined, with f(x)∥m(x). But

f(T)v = 0

for all v ∈ V, and so

f(T) = 0.

Hence f(x) = m(x).

3. We have

m_{v}(T)u = m_{v}(T)f(T)v = f(T)m_{v}(T)v = 0.

Hence m_{u}(x)∥m_{v}(x).

4. Clearly

m_{u+v}(x)∥m_{u}(x)m_{v}(x).

Let

w = m_{u}(T)(u + v) = m_{u}(T)v;

and let f(x) = m_{w}(x). Then

0 = f(T)w = f(T)m_{u}(T)v,

A–2

and so

m_{v}(x)∥f(x)m_{u}(x).

But since m_{u}(x), m_{v}(x) are coprime, this implies that

m_{v}(x)∥f(x).

On the other hand, by part 3 of the Lemma,

f(x)∥m_{u+v}(x).

Hence

m_{v}(x)∥m_{u+v}(x),

and similarly

m_{u}(x)∥m_{u+v}(x).

Since m_{u}(x), m_{v}(x) are coprime, this implies that

m_{u}(x)m_{v}(x)∥m_{u+v}(x),

from which the result follows.

Lemma 28. There exists a vector v (sometimes called a cylic vector of T) such that m_{v}(x) = m(x).

Proof. Let

m(x) = p_{1}(x)^{e_{1}}p_{2}(x)^{e_{2}} ⋯ p_{r}(x)^{e_{r}}

be the expression for the minimal polynomial m(x) of T as a product of prime polynomials.

From part 2 of the Lemma above, for each i(1 ≤ i ≤ r) we can find a vector u_{i} whose minimal polynomial is divisible by p_{i}(x)^{e_{i}}, say

m_{u_{i}}(x) = p_{i}(x)^{e_{i}}f_{i}(x).

But then

v_{i} = f_{i}(T)u_{i}

has minimal polynomial p_{i}(x)^{e_{i}}.

Now from part 4 of the Lemma above, if we set

v = v_{1} + v_{2} + ⋯ + v_{r}

then

m_{v}(x) = m(x).

We shall apply this result to the fundamental automorphism π of F_{(}p^{n}).

Proof. Since π : F → F is a linear transformation, we can apply the Lemma above. The minimal polynomial of π is

m(x) = x^{n} − 1.

For π satisfies m(x) = 0; and it cannot satisfy any equation of lower degree. For suppose

c_{0}π^{d} + c_{1}π^{d−1} + … c_{d} = 0.

A–3

Then every element α ∈ F satisfies the equation

c_{0}x^{p^{d}} + c_{1}x^{p^{d−1}} + … c_{d} = 0.

But that is a contradiction, since the polynomial on the left has at most p^{d} roots.

By the Lemma, we can find a cyclic vector of π, ie an element α ∈ F whose minimal polynomial is x^{n} − 1. But this implies in particular that

α, πα, π^{2}α, …, π^{n−1}α

are linearly independent, and so form a basis for F over P.

A–4