TABLE 10.1. Quotient Ring Z6 /{0, 2, 4}

+ I +1 · I +1

I I

I +1

I I I I I

I +1 I +1 I +1 I +1

I I

For example, the quotient ring of Z by (n) is Z/(n) = Zn , the ring of integers

modulo n. A coset (n) + r = {nz + r|z ∈ Z} is the equivalent class modulo n

containing r.

If R is commutative, so is the quotient ring R/I , because

(I + r1 )(I + r2 ) = I + r1 r2 = I + r2 r1 = (I + r2 )(I + r1 ).

Example 10.6. If I = {0, 2, 4} is the ideal generated by 2 in Z6 , ¬nd the tables

for the quotient ring Z6 /I .

Solution. There are two cosets of Z6 by I : namely, I = {0, 2, 4} and I + 1 =

{1, 3, 5}. Hence

Z6 /I = {I, I + 1}.

The addition and multiplication tables given in Table 10.1 show that the quotient

ring Z6 /I is isomorphic to Z2 .

COMPUTATIONS IN QUOTIENT RINGS

If F is a ¬eld, the quotient rings of the polynomial ring F [x] form an important

class of rings that will be used to construct new ¬elds. Recall that F [x] is a

principal ideal ring, so that any quotient ring is of the form F [x]/(p(x)), for some

polynomial p(x) ∈ F [x]. We now look at the structure of such a quotient ring.

The elements of the ring F [x]/(p(x)) are equivalence classes under the rela-

tion on F [x] de¬ned by

f (x) ≡ g(x) mod(p(x)) f (x) ’ g(x) ∈ (p(x)).

if and only if

Lemma 10.7. f (x) ≡ g(x) mod(p(x)) if and only if f (x) and g(x) have the

same remainder when divided by p(x).

Proof. Let f (x) = q(x) · p(x) + r(x) and g(x) = s(x) · p(x) + t (x), where

r(x) and t(x) are zero or have degrees less than that of p(x). Now the lemma

follows because the following statements are equivalent:

(i) f (x) ≡ g(x) mod(p(x)).

(ii) f (x) ’ g(x) ∈ (p(x)).

(iii) p(x)|f (x) ’ g(x).

208 10 QUOTIENT RINGS

(iv) p(x)|[{q(x) ’ s(x)} · p(x) + (r(x) ’ t (x))].

(v) p(x)|[r(x) ’ t (x)].

(vi) r(x) = t (x).

Hence every coset of F [x] by (p(x)) contains the zero polynomial or a poly-

nomial of degree less than that of p(x).

Theorem 10.8. If F is a ¬eld, let P be the ideal (p(x)) in F [x] generated by

the polynomial p(x) of degree n > 0. The different elements of F [x]/(p(x)) are

precisely those of the form

P + a0 + a1 x + · · · + an’1 x n’1 where a0 , a1 , . . . , an’1 ∈ F.

Proof. Let P + f (x) be any element of F [x]/(p(x)) and let r(x) be the

remainder when f (x) is divided by p(x). Then, by Lemma 10.7, P + f (x) =

P + r(x), which is of the required form.

Suppose that P + r(x) = P + t (x), where r(x) and t (x) are zero or have

degree less than n. Then

r(x) ≡ t (x) mod(p(x)),

and by Lemma 10.7, r(x) = t (x).

Example 10.9. Write down the tables for Z2 [x]/(x 2 + x + 1).

Solution. Let P = (x 2 + x + 1), so that

Z2 [x]/(x 2 + x + 1) = {P + a0 + a1 x|a0 , a1 ∈ Z2 }

= {P , P + 1, P + x, P + x + 1}.

The tables for the quotient ring are given in Table 10.2. The addition table is

straightforward to calculate. Multiplication is computed as follows:

(P + x)2 = P + x 2 = P + (x 2 + x + 1) + (x + 1) = P + x + 1

and

(P + x)(P + x + 1) = P + x 2 + x = P + (x 2 + x + 1) + 1 = P + 1.

Example 10.10. Let P = x 2 ’ 2 be the principal ideal of Q[x] generated by

x 2 ’ 2. Find the sum and product of P + 3x + 4 and P + 5x ’ 6 in the ring

Q[x]/(x 2 ’ 2) = {P + a0 + a1 x|a0 , a1 ∈ Q}.

Solution. (P + 3x + 4) + (P + 5x ’ 6) = P + (3x + 4) + (5x ’ 6) = P +

8x ’ 2. (P + 3x + 4)(P + 5x ’ 6) = P + (3x + 4)(5x ’ 6) = P + 15x 2 + 2x

’ 24. By the division algorithm, 15x 2 + 2x ’ 24 = 15(x 2 ’ 2) + 2x + 6. Hence,

by Lemma 10.7, P + 15x 2 + 2x ’ 24 = P + 2x + 6.

MORPHISM THEOREM 209

TABLE 10.2. Ring Z2 [x ]/(x 2 + x + 1)

+ P +1 P +x P +x+1

P

P +1 P +x P +x+1

P P

P +1 P +1 P +x+1 P +x

P

P +x P +x P +x+1 P +1

P

P +x+1 P +x+1 P +x P +1 P

· P +1 P +x P +x +1

P

P P P P P

P +1 P +1 P +x P +x +1

P

P +x P +x P +x+1 P +1

P

P +x+1 P +x+1 P +1 P +x

P

There are often easier ways of ¬nding the remainder of f (x) when divided by

p(x) than by applying the division algorithm directly. If deg p(x) = n and P =

(p(x)), the problem of ¬nding the remainder reduces to the problem of ¬nding

a polynomial r(x) of degree less than n such that f (x) ≡ r(x) modP . This can

often be solved by manipulating congruences, using the fact that p(x) ≡ 0 modP .

Consider Example 10.10, in which P is the ideal generated by x 2 ’ 2. Then

x 2 ’ 2 ≡ 0 modP and x 2 ≡ 2 modP . Hence, in any congruence modulo P , we

can always replace x 2 by 2. For example,

15x 2 + 2x ’ 24 ≡ 15(2) + 2x ’ 24 modP

≡ 2x + 6 modP ,

so P + 15x 2 + 2x ’ 24 = P + 2x + 6.

In Example 10.9, P = (x 2 + x + 1), so x 2 + x + 1 ≡ 0 modP and x 2 ≡ x +

1 modP . (Remember + 1 = ’1 in Z2 .) Therefore, in multiplying two elements

in Z2 [x]/P , we can always replace x 2 by x + 1. For example,

P + x2 = P + x + 1 and P + x(x + 1) = P + x 2 + x = P + 1.

We have usually written the elements of Zn = Z/(n) simply as 0, 1, . . . ,

n ’ 1 instead of as [0], [1], . . . , [n ’ 1] or as (n) + 0, (n) + 1, . . . , (n) + n ’ 1.

In a similar way, when there is no confusion, we henceforth write the elements

of F [x]/(p(x)) simply as a0 + a1 x + · · · + an’1 x n’1 instead of (p(x)) + a0 +

a1 x + · · · + an’1 x n’1 .

MORPHISM THEOREM

Proposition 10.11. If f : R ’ S is a ring morphism, then Kerf is an ideal of R.

Proof. Since any ring morphism is a group morphism, it follows from Propo-

sition 4.23 that Kerf is a subgroup of (R, +). If x ∈ Kerf and r ∈ R, then

210 10 QUOTIENT RINGS

f (xr) = f (x)f (r) = 0 · f (r) = 0 and xr ∈ Kerf . Similarly, rx ∈ Kerf , so Kerf

is an ideal of R.

Furthermore, any ideal I of a ring R is the kernel of a morphism, for example,

the ring morphism π: R ’ R/I de¬ned by π(r) = I + r.

The image of a morphism f : R ’ S can easily be veri¬ed to be a subring

of S.

Theorem 10.12. Morphism Theorem for Rings. If f : R ’ S is a ring mor-

phism, then R/Kerf is isomorphic to Imf .

This result is also known as the ¬rst isomorphism theorem for rings; the

second and third isomorphism theorems are given in Exercises 10.19 and 10.20.

Proof. Let K = Kerf . It follows from the morphism theorem for groups

(Theorem 4.23), that ψ: R/K ’ Imf , de¬ned by ψ(K + r) = f (r), is a group

isomorphism. Hence we need only prove that ψ is a ring morphism. We have

ψ{(K + r)(K + s)} = ψ{K + rs} = f (rs) = f (r)f (s)

= ψ(K + r)ψ(K + s).

√

Example 10.13. Prove that Q[x]/(x 2 ’ 2) ∼ Q( 2).

=

Solution. Consider the ring morphism ψ: Q[x] ’ R de¬ned by ψ(f (x)) =

√

f ( 2) in Example 9.24. The kernel is the set of polynomials containing x 2 ’ 2

√

as a factor, that is, the principal ideal (x 2 ’ 2). The image of ψ is Q( 2) so by

√

the morphism theorem for rings, Q[x]/(x 2 ’ 2) ∼ Q( 2).

=

In this isomorphism, the element a0 + a1 x ∈ Q[x]/(x 2 ’ 2) is mapped to

√ √

a0 + a1 2 ∈ Q( 2). Addition and multiplication of the elements a0 + a1 x and

b0 + b1 x in Q[x]/(x 2 ’ 2) correspond to the addition and multiplication of the

√ √

real numbers a0 + a1 2 and b0 + b1 2.

Example 10.14. Prove that R[x]/(x 2 + 1) ∼ C.

=

Solution. De¬ne the ring morphism ψ: R[x] ’ C by ψ(f (x)) = f (i), where

√

i = ’1. Any polynomial in Kerψ has i as a root, and therefore, by Theo-

rem 9.22, also has ’i as a root and contains the factor x 2 + 1. Hence Kerψ =

(x 2 + 1).

Now ψ(a + bx) = a + ib; thus ψ is surjective. By the morphism theorem for

rings, R[x]/(x 2 + 1) ∼ C.

=

QUOTIENT POLYNOMIAL RINGS THAT ARE FIELDS

We now determine when a quotient of a polynomial ring is a ¬eld. This result

allows us to construct many new ¬elds.

QUOTIENT POLYNOMIAL RINGS THAT ARE FIELDS 211

Theorem 10.15. Let a be an element of the euclidean ring R. The quotient ring

R/(a) is a ¬eld if and only if a is irreducible in R.

Proof. Suppose that a is an irreducible element of R and let (a) + b be a

nonzero element of R/(a). Then b is not a multiple of a, and since a is irreducible,

gcd(a, b) = 1. By Theorem 9.9, there exist s, t ∈ R such that

sa + tb = 1.

Now sa ∈ (a), so [(a) + t] · [(a) + b] = (a) + 1, the identity of R/(a). Hence

(a) + t is the inverse of (a) + b in R/(a) and R/(a) is a ¬eld.

Now suppose that a is not irreducible in R so that there exist elements s and

t, which are not invertible, with st = a. By Lemma 9.17, δ(s) < δ(st) = δ(a)

and δ(t) < δ(st) = δ(a). Hence s is not divisible by a, and s ∈ (a). Similarly,

/

t ∈ (a), and neither (a) + s nor (a) + t is the zero element of R/(a). However,

/

[(a) + s] · [(a) + t] = (a) + st = (a), the zero element of R/(a).

Therefore, the ring R/(a) has zero divisors and cannot possibly be a ¬eld.

For example, in the quotient ring Q[x]/P , where P = (x 2 ’ 1), the elements

P + x + 1 and P + x ’ 1 are zero divisors because

(P + x + 1) · (P + x ’ 1) = P + x 2 ’ 1 = P , the zero element.

Corollary 10.16. Zp = Z/(p) is a ¬eld if and only if p is prime.

Proof. This result, which we proved in Theorem 8.11, follows from

Theorem 10.15 because the irreducible elements in Z are the primes (and

their negatives).

Another particular case of Theorem 10.15 is the following important theorem.

Theorem 10.17. The ring F [x]/(p(x)) is a ¬eld if and only if p(x) is irreducible

over the ¬eld F . Furthermore, the ring F [x]/(p(x)) always contains a subring

isomorphic to the ¬eld F .

Proof. The ¬rst part of the theorem is just Theorem 10.15. Let F = {(p(x)) +

r|r ∈ F }. This can be veri¬ed to be a subring of F [x]/(p(x)), which is isomor-

phic to the ¬eld F by the isomorphism that takes r ∈ F to (p(x))+

r ∈ F [x]/(p(x)).

Example 10.18. Show that Z2 [x]/(x 2 + x + 1) is a ¬eld with four elements.

Solution. We showed in Example 9.34 that x 2 + x + 1 is irreducible over Z2

and in Example 10.9 that the quotient ring has four elements. Hence the quotient

ring is a ¬eld containing four elements. Its tables are given in Table 10.2.

212 10 QUOTIENT RINGS

Example 10.19. Write down the multiplication table for the ¬eld Z3 [x]/(x 2 + 1).

Solution. If x = 0, 1, or 2 in Z3 , then x 2 + 1 = 1, 2, or 2; thus, by the factor

theorem, x 2 + 1 has no linear factors. Hence x 2 + 1 is irreducible over Z3 and,

by Theorem 10.17, the quotient ring Z3 [x]/(x 2 + 1) is a ¬eld. By Theorem 10.8,

the elements of this ¬eld can be written as

Z3 [x]/(x 2 + 1) = {a0 + a1 x|a0 , a1 ∈ Z3 }.

Hence the ¬eld contains nine elements. Its multiplication table is given in

Table 10.3. This can be calculated by multiplying the polynomials in Z3 [x] and

replacing x 2 by ’1 or 2, since x 2 ≡ ’1 ≡ 2mod (x 2 + 1).

Example 10.20. Show that Q[x]/(x 3 ’ 5) = {a0 + a1 x + a2 x 2 |ai ∈ Q} is a ¬eld

and ¬nd the inverse of the element x + 1.

Solution. By the rational roots theorem (Theorem 9.25), (x 3 ’ 5) has no linear

factors and hence is irreducible over Q. Therefore, by Theorem 10.17,

Q[x]/(x 3 ’ 5) is a ¬eld.

If s(x) is the inverse of x + 1, then (x + 1)s(x) ≡ 1 mod(x 3 ’ 5); that is,

(x + 1)s(x) + (x 3 ’ 5)t (x) = 1 for some t (x) ∈ Q[x].

We can ¬nd such polynomials s(x) and t (x) by the euclidean algorithm. We

have (see below)

x 3 ’ 5 = (x 2 ’ x + 1)(x + 1) ’ 6,

so

6 ≡ (x 2 ’ x + 1)(x + 1) mod(x 3 ’ 5)

and

1 ≡ 1 (x 2 ’ x + 1)(x + 1) mod(x 3 ’ 5).

6

TABLE 10.3. Multiplication in Z3 [x ]/(x 2 + 1)

· x+1 x+2 2x + 1 2x + 2

0 1 2 x 2x

0 0 0 0 0 0 0 0 0 0

x+1 x+2 2x + 1 2x + 2

1 0 1 2 2x

x

2x + 2 2x + 1 x+2 x+1

2 0 2 1 2x x

x+2 2x + 2 x+1 2x + 1

0 2x 2 1

x x

x+1 x+1 2x + 2 x+2 2x + 1

0 2x 1 2 x

x+2 x+2 2x + 1 2x + 2 x+1

0 1 2x 2

x

2x + 1 x+1 2x + 2 x+2

2x 0 2x 1 2

x

2x + 1 2x + 1 x+2 x+1 2x + 2

0 2 2x 1

x

2x + 2 2x + 2 x+1 2x + 1 x+2

0 2 1 2x

x

QUOTIENT POLYNOMIAL RINGS THAT ARE FIELDS 213

Hence (x + 1)’1 = 1 x 2 ’ 1 x + in Q[x]/(x 3 ’ 5).

1

6 6 6

x2 ’ x + 1

x + 1 x 3 + 0+0 ’5

x 3 +x 2

’x 2 ’ 5

’x 2 ’x

x ’5

x +1

’6

Example 10.21. Show that Z3 [x]/(x 3 + 2x + 1) is a ¬eld with 27 elements and

¬nd the inverse of the element x 2 .

Solution. If x = 0, 1, or 2 in Z3 , then x 3 + 2x + 1 = 1; hence x 3 + 2x + 1

has no linear factors and is irreducible. Therefore,

Z3 [x]/(x 3 + 2x + 1) = {a0 + a1 x + a2 x 2 |ai ∈ Z3 }

is a ¬eld that has 33 = 27 elements.

As in Example 10.20, to ¬nd the inverse of x 2 , we apply the euclidean algo-

rithm to x 3 + 2x + 1 and x 2 in Z3 [x].

We have x 3 + 2x + 1 = x(x 2 ) + (2x + 1) and x 2 = (2x + 2)(2x + 1) + 1.

Hence

1 = x 2 ’ (2x + 2){(x 3 + 2x + 1) ’ x · x 2 }

= x 2 (2x 2 + 2x + 1) ’ (2x + 2)(x 3 + 2x + 1),

so

1 ≡ x 2 (2x 2 + 2x + 1) mod(x 3 + 2x + 1)

and the inverse of x 2 in Z3 [x]/(x 3 + 2x + 1) is 2x 2 + 2x + 1.

x

2x + 2

x 3 +0+2x+1

x2

2x + 1 x 2 + 0+0

x3

x 2 +2x

2x+1

x+0

x+2

1

214 10 QUOTIENT RINGS

We cannot use Theorem 10.15 directly on a ¬eld to obtain any new quotient

¬elds, because the only ideals of a ¬eld are the zero ideal and the entire ¬eld. In

fact, the following result shows that a ¬eld can be characterized by its ideals.

Theorem 10.22. The nontrivial commutative ring R is a ¬eld if and only if (0)

and R are its only ideals.

Proof. Let I be an ideal in the ¬eld R. Suppose that I = (0), so that there is

a nonzero element a ∈ I . Since a ’1 ∈ R, a · a ’1 = 1 ∈ I . Therefore, by Propo-

sition 10.4, I = R. Hence R has only trivial ideals.

Conversely, suppose that (0) and R are the only ideals in the ring R. Let

a be a nonzero element of R and consider (a) the principal ideal generated

by a. Since 1 · a ∈ (a), (a) = (0), and hence (a) = R. Hence 1 ∈ R = (a), so

there must exist some b ∈ R such that a · b = 1. Therefore, b = a ’1 and R is

a ¬eld.

EXERCISES

For Exercises 10.1 to 10.6, ¬nd all the ideals in the rings.

10.1. Z2 — Z2 . 10.2. Z18 . 10.3. Q.

10.4. Z7 . 10.5. C[x]. 10.6. Z[i].

For Exercises 10.7 to 10.10, construct addition and multiplication tables for the

rings. Find all the zero divisors in each ring. Which of these rings are ¬elds?

10.8. Z2 [x]/(x 3 + 1).

10.7. Z6 /(3).

10.9. Z3 — Z3 /((1, 2)). 10.10. Z3 [x]/(x 2 + 2x + 2).

For Exercises 10.11 to 10.14, compute the sum and product of the elements in the

given quotient rings.

3x + 4 and 5x ’ 2 in Q[x]/(x 2 ’ 7).

10.11.

x 2 + 3x + 1 and ’2x 2 + 4 in Q[x]/(x 3 + 2).

10.12.

x 2 + 1 and x + 1 in Z2 [x]/(x 3 + x + 1).

10.13.

ax + b and cx + d in R[x]/(x 2 + 1), where a, b, c, d ∈ R.

10.14.

If U and V are ideals in a ring R, prove that U © V is also an ideal in

10.15.

R.

10.16. Show, by example, that if U and V are ideals in a ring R, then U ∪ V is

not necessarily an ideal in R. But prove that U + V = {u + v|u ∈ U, v ∈

V } is always an ideal in R.

10.17. Find a generator of the following ideals in the given ring and prove a

general result for the intersection of two ideals in a principal ideal ring.

(a) (2) © (3) in Z. (b) (12) © (18) in Z.

(c) (x ’ 1) © (x + 1) in Q[x].

2

EXERCISES 215

10.18. Find a generator of the following ideals in the given ring and prove a

general result for the sum of two ideals in a principal ideal ring.

(a) (2) + (3) in Z. (b) (9) + (12) in Z.

(c) (x + x + 1) + (x + 1) in Z2 [x].

2 2

10.19. (Second isomorphism theorem for rings) If I and J are ideals of the

ring R, prove that

I /(I © J ) ∼ (I + J )/J.

=

10.20. (Third isomorphism theorem for rings) Let I and J be two ideals of

the ring R, with J ⊆ I . Prove that I /J is an ideal of R/J and that

(R/J )/(I /J ) ∼ R/I.

=

For Exercises 10.21 to 10.29, prove the isomorphisms.

10.21. R[x]/(x 2 + 5) ∼ C.

=

10.22. Z[x]/(x + 1) ∼ Z[i] = {a + ib|a, b ∈ Z}.

=

2

√ √

10.23. Q[x]/(x ’ 7) ∼ Q( 7) = {a + b 7|a, b ∈ Q}.

=

2

10.24. Z[x]/(2x ’ 1) ∼ {a/b ∈ Q|a ∈ Z, b = 2r , r 0}, a subring of Q.

=

10.25. Z14 /(7) ∼ Z7 . 10.26. Z14 /(2) ∼ Z2 .

= =

10.27. R[x, y]/(x + y) ∼ R[y]. 10.28. (R — S)/((1, 0)) ∼ S.

= =

∼ P (Y ), where Y is a subset of X and the operations

10.29. P (X)/P (X ’ Y ) =

in these boolean rings are symmetric difference and intersection.

10.30. Let I be the set of all polynomials with no constant term in R[x, y]. Find

a ring morphism from R[x, y] to R whose kernel is the ideal I . Prove

that I is not a principal ideal.

10.31. Let I = {p(x) ∈ Z[x]| 5|p(0)}. Prove that I is an ideal of Z[x] by ¬nding

a ring morphism from Z[x] to Z5 with kernel I . Prove that I is not a

principal ideal.

10.32. Let I ⊆ P (X) with the property that, if A ∈ I , then all the subsets of A

are in I , and also if A and B are disjoint sets in I , then A ∪ B ∈ I . Prove

that I is an ideal in the boolean ring (P (X), , ©).

10.33. Is {p(x) ∈ Q[x]|p(0) = 3} an ideal of Q[x]?

a0

∈ M2 (Z)|a, b ∈ Z an ideal of M2 (Z)?

10.34. Is

b0

10

10.35. What is the smallest ideal in M2 (Z) containing ?

00

10.36. Let a, b be elements of a euclidean ring R. Prove that

(a) ⊆ (b) if and only if b|a.

For the rings in Exercises 10.37 and 10.38, ¬nd all the ideals and draw the poset

diagrams of the ideals under inclusion.

10.37. Z8 . 10.38. Z20 .

216 10 QUOTIENT RINGS

Which of the elements in Exercises 10.39 to 10.46 are irreducible in the given

ring? If an element is irreducible, ¬nd the corresponding quotient ¬eld modulo

the ideal generated by that element.

11 in Z. 10 in Z.

10.39. 10.40.

x 2 ’ 2 in R[x]. x 3 + x 2 + 2 in Z3 [x].

10.41. 10.42.

x 4 ’ 2 in Q[x]. x 7 + 4x 3 ’ 3ix + 1 in C[x].

10.43. 10.44.

√

x 2 ’ 3 in Q( 2)[x]. 3x 5 ’ 4x 3 + 2 in Q[x].

10.45. 10.46.

Which of the rings in Exercises 10.47 to 10.56 are ¬elds? Give reasons.

Z2 — Z2 . 10.48. Z4 .

10.47.

Z17 . 10.50. R3 .

10.49.

Q[x]/(x 3 ’ 3). 10.52. Z7 [x]/(x 2 + 1).

10.51.

Z5 [x]/(x 2 + 1). 10.54. R[x]/(x 2 + 7).

10.53.

√ 1 1 3

Q( 11) = {a + b11 4 + c11 2 + d11 4 |a, b, c, d ∈ Q}.

4

10.55.

10.56. Mn (R).

An ideal I = R is said to be a maximal ideal in the commutative ring

10.57.

R if, whenever U is an ideal of R such that I ⊆ U ⊆ R, then U = I or

U = R. Show that the nonzero ideal (a) of a euclidean ring R is maximal

if and only if a is irreducible in R.

10.58. If I is an ideal in a commutative ring R, prove that R/I is a ¬eld if and

only if I is a maximal ideal of R.

Find all the ideals in the ring of formal power series, R[[x]]. Which of

10.59.

the ideals are maximal?

Let C[0, 1] = {f : [0, 1] ’ R|f is continuous}, the ring of real-valued

10.60.

continuous functions on the interval [0, 1]. Prove that Ia = {f ∈

C[0, 1]|f (a) = 0} is a maximal ideal in C[0, 1] for each a ∈ [0, 1]. (Every

maximal ideal is, in fact, of this form, but this is much harder to prove.)

10.61. If P is an ideal in a commutative ring R, show that R/P is an integral

domain if and only if ab ∈ P can only happen if a ∈ P or b ∈ P . The

ideal P is called a prime ideal in this case.

Let R be a commutative ring. An element a ∈ R is called nilpotent if

10.62.

a n = 0 for some n 0 in Z. The set N (R) of all nilpotents in R is called

the radical of R.

(a) Show that N (R) is an ideal of R (the binomial theorem is useful).

(b) Show that N [R/N (R)] = {N (R)}.

(c) Show that N (R) is contained in the intersection of all prime ideals

of R (see Exercise 10.61). In fact, N (R) equals the intersection of

all prime ideals of R.

10.63. A commutative ring R is called local if the set J (R) of all non-invertible

elements forms an ideal of R.

(a) Show that every ¬eld is local as is Zpn for each prime p and n 1,

but that Z6 is not local.

EXERCISES 217

r

(b) Show that Z(p) = ∈ Q|p does not divide s is a local subring of

s

Q for each prime p.

(c) If R is local show that R/J (R) is a ¬eld.

(d) If R/N(R) is a ¬eld, show that R is local (if a is nilpotent, then 1 ’ a

is invertible).

10.64. If R is a (possibly noncommutative) ring, an additive subgroup L of R is

called a left ideal if rx ∈ L for all r ∈ R and x ∈ L. Show that the only

left ideals of R are {0} and R if and only if every nonzero element of R

has an inverse (then R is called a skew ¬eld).

10.65. If F is a ¬eld, show that R = M2 (F ) has exactly two ideals: 0 and R.

(Because of this, R is called a simple ring.) Conclude that Theorem 10.22

fails if the ring is not commutative.

11

FIELD EXTENSIONS

We proved in Chapter 10 that if p(x) is an irreducible polynomial over the ¬eld

F , the quotient ring K = F [x]/(p(x)) is a ¬eld. This ¬eld K contains a subring

isomorphic to F ; thus K can be considered to be an extension of the ¬eld F . We

show that the polynomial p(x) now has a root ± in this extension ¬eld K, even

though p(x) was irreducible over F . We say that K can be obtained from F by

adjoining the root ±. We can construct the complex numbers C in this way, by

adjoining a root of x 2 + 1 to the real numbers R.

Another important achievement is the construction of a ¬nite ¬eld with p n

elements for each prime p. Such a ¬eld is called a Galois ¬eld of order p n and

is denoted by GF(p n ). We show how this ¬eld can be constructed as a quotient

ring of the polynomial ring Zp [x], by an irreducible polynomial of degree n.

FIELD EXTENSIONS

A sub¬eld of a ¬eld K is a subring F that is also a ¬eld. In this case, the ¬eld

K is called an extension of the ¬eld F . For example, Q is a sub¬eld of R; thus

R is an extension of the ¬eld Q.

Example 11.1. Let p(x) be a polynomial of degree n irreducible over the ¬eld

F , so that the quotient ring

K = F [x]/(p(x)) = {a0 + a1 x + · · · + an’1 x n’1 |ai ∈ F }

is a ¬eld. Then K is an extension ¬eld of F .

Solution. This follows from Theorem 10.17 when we identify the coset

(p(x)) + a0 containing the constant term a0 with the element a0 of F .

Proposition 11.2. Let K be an extension ¬eld of F . Then K is a vector space

over F .

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson

ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

218

FIELD EXTENSIONS 219

Proof. K is an abelian group under addition. Elements of K can be multiplied

by elements of F . This multiplication satis¬es the following properties:

1 is the identity element of F then 1k = k for all k ∈ K.

(i) If

» ∈ F and k, l ∈ K, then »(k + l) = »k + »l.

(ii) If

», µ ∈ F and k ∈ K, then (» + µ)k = »k + µK.

(iii) If

», µ ∈ F and k ∈ K, then (»µ)k = »(µk).

(iv) If

Hence K is a vector space over F .

The fact that a ¬eld extension K is a vector space over F tells us much

about the structure of K. The elements of K can be written uniquely as a linear

combination of certain elements called basis elements. Furthermore, if the vector

space K has ¬nite dimension n over the ¬eld F , there will be n basis elements,

and the construction of K is particularly simple.

The degree of the extension K of the ¬eld F , written [K : F ], is the dimension

of K as a vector space over F . The ¬eld K is called a ¬nite extension if [K : F ]

is ¬nite.

Example 11.3. [C : R] = 2.

Solution. C = {a + ib|a, b ∈ R}; therefore, 1 and i span the vector space C

over R. Now 1 and i are linearly independent since, if », µ ∈ R, then »1 + µi = 0

implies that » = µ = 0. Hence {1, i} is a basis for C over R and

[C : R] = 2.

Example 11.4. If K = Z5 [x]/(x 3 + x + 1), then [K: Z5 ] = 3.

Solution. {1, x, x 2 } is a basis for K over Z5 because by Theorem 10.8, every

element of K can be written uniquely as the coset containing a0 + a1 x + a2 x 2 ,

where ai ∈ Z5 . Hence [K: Z5 ] = 3.

Example 11.4 is a special case of the following theorem.

Theorem 11.5. If p(x) is an irreducible polynomial of degree n over the ¬eld

F , and K = F [x]/(p(x)), then [K : F ] = n.

Proof. By Theorem 10.8, K = {a0 + a1 x + · · · + an’1 x n’1 |ai ∈ F }, and such

expressions for the elements of K are unique. Hence {1, x, x 2 , . . . , x n’1 } is a

basis for K over F , and [K : F ] = n.

Theorem 11.6. Let L be a ¬nite extension of K and K a ¬nite extension of F .

Then L is a ¬nite extension of F and [L : F ] = [L : K][K : F ].

Proof. We have three ¬elds, F , K, L, with L ⊇ K ⊇ F . We prove the theorem

by taking bases for L over K, and K over F , and constructing a basis for L

over F .

220 11 FIELD EXTENSIONS

Let [L : K] = m and let {u1 , . . . , um } be a basis for L over K. Let [K : F ] = n

and let {v1 , . . . , vn } be a basis for K over F . We show that

B = {vj ui |i = 1, . . . , m, j = 1, . . . , n} is a basis for L over F.

If x ∈ L, then x = m »i ui , for some »i ∈ K. Now each element »i can be

i=1

written as »i = n=1 µij vj , for some µij ∈ F . Hence x = m n

j =1 µij vj ui ,

j i=1

and B spans L over F .

m n

j =1 µij vj ui = 0, where µij ∈ F . Then, since

Now suppose that i=1

u1 , . . . , um are linearly independent over K, it follows that n=1 µij vj = 0 for

j

each i = 1, . . . , m. But v1 , . . . , vn are linearly independent over F so µij = 0

for each i and each j .

Hence the elements of B are linearly independent, and B is a basis for L over

F . Therefore, [L : F ] = m · n = [L : K][K : F ].

Example 11.7. Show that there is no ¬eld lying strictly between Q and L =

Q[x]/(x 3 ’ 2).

Solution. The constant polynomials in L are identi¬ed with Q. Suppose that

K is a ¬eld such that L ⊇ K ⊇ Q. Then [L : Q] = [L : K][K : Q], by Theo-

rem 11.6. But, by Theorem 11.5, [L : Q] = 3, so [L : K] = 1, or [K : Q] = 1.

If [L : K] = 1, then L is a vector space over K, and {1}, being linearly

independent, is a basis. Hence L = K. If [K : Q] = 1, then K = Q. Hence there

is no ¬eld lying strictly between L and Q.

Given a ¬eld extension K of F and an element a ∈ K, de¬ne F (a) to be

the intersection of all sub¬elds of K that contain F and a. This is the smallest

sub¬eld of K containing F and a, and is called the ¬eld obtained by adjoining

a to F .

For example, the smallest ¬eld containing R and i is the whole of the complex

numbers, because this ¬eld must contain all elements of the form a + ib where

a, b ∈ R. Hence R(i) = C.

In a similar way, the ¬eld obtained by adjoining a1 , . . . , an ∈ K to F is

denoted by F (a1 , . . . , an ) and is de¬ned to be the smallest sub¬eld of F con-

taining a1 , . . . , an and F . It follows that F (a1 , . . . , an ) = F (a1 , . . . , an’1 )(an ).

√ √

Example 11.8. Q( 2) is equal to the sub¬eld F = {a + b 2|a, b ∈ Q} of R.

√ √ √

Solution. Q( 2) must contain all rationals and 2. Hence Q( 2) must con-

√ √

tain all real numbers of the form√ 2 for b ∈ Q and also a + b 2 for a, b ∈ Q.

b

√ √

Therefore, F ⊆ Q( 2). But Q( 2) is√ smallest ¬eld containing Q and 2.

the √

Since F is another such ¬eld, F ⊇ Q( 2) and so F = Q( 2).

If R is an integral domain and x is an indeterminate, then

a0 + a1 x + · · · + an x n

R(x) = ai , bj ∈ R; not all the bj ™s are zero ,

b0 + b1 x + · · · + bm x m

ALGEBRAIC NUMBERS 221

which is the ¬eld of rational functions in R. Any ¬eld containing R and x must

contain the polynomial ring R[x], and the smallest ¬eld containing R[x] is its

¬eld of fractions R(x).

ALGEBRAIC NUMBERS

If K is a ¬eld extension of F , the element k ∈ K is called algebraic over F if

there exist a0 , a1 , . . . , an ∈ F , not all zero, such that

a0 + a1 k + · · · + an k n = 0.

In other words, k is the root of a nonzero polynomial in F [x]. Elements that are

not algebraic over F are called transcendental over F .

√ √

For example, 5, 3, i, n 7 + 3 are all algebraic over Q because they are roots

of the polynomials x ’ 5, x 2 ’ 3, x 2 + 1, (x ’ 3)n ’ 7, respectively.

√ √

Example 11.9. Find a polynomial in Q[x] with 3 2 + 5 as a root.

√ √

Solution. Let x = 3 2 + 5. We have to eliminate√ square and cube roots

the

√

√

have x ’ 5 = 2, so (x ’ 5)3 = 2 or

3

from this equation. We √

√2 √

x 3 ’ 3 5x + 15x ’ 5 5 = 2. Hence x 3 +√ ’ 2 = 5(3x 2 + 5), so

15x √

(x 3 + 15x ’ 2)2 = 5(3x 2 + 5)2 . Therefore, 3 2 + 5 is a root of

x 6 ’ 15x 4 ’ 4x 3 + 75x 2 ’ 60x ’ 121 = 0.

Not all real and complex numbers are algebraic over Q. The numbers π and

e can be proven to be transcendental over Q (see Stewart [35]). Since π is

transcendental, we have

a0 + a1 π + · · · + an π n

Q(π ) = ai , bj ∈ Q; not all the bj s are zero ,

b0 + b1 π + · · · + bm π m

the ¬eld of rational functions in π with coef¬cients in Q. Q(π ) must contain all

the powers of π and hence any polynomial in π with rational coef¬cients. Any

nonzero element of Q(π ) must have its inverse in Q(π ); thus Q(π ) contains the

set of rational functions in π. The number b0 + b1 π + · · · + bm π m is never zero

unless b0 = b1 = · · · = bm = 0 because π is not the root of any polynomial with

rational coef¬cients. This set of rational functions in π can be shown to be a

sub¬eld of R.

Those readers acquainted with the theory of in¬nite sets can prove that the set

of rational polynomials, Q[x], is countable. Since each polynomial has only a

¬nite number of roots in C, there are only a countable number of real or complex

numbers algebraic over Q. Hence there must be an uncountable number of real

and complex numbers transcendental over Q.

Example 11.10. Is cos(2π/5) algebraic or transcendental over Q?

222 11 FIELD EXTENSIONS

Solution. We know from De Moivre™s theorem that

(cos 2π/5 + i sin 2π/5)5 = cos 2π + i sin 2π = 1.

Taking real parts and writing c = cos 2π/5 and s = sin 2π/5, we have

c5 ’ 10s 2 c3 + 5s 4 c = 1.

Since s 2 + c2 = 1, we have c5 ’ 10(1 ’ c2 )c3 + 5(1 ’ c2 )2 c = 1. That is,

16c5 ’ 20c3 + 5c ’ 1 = 0 and hence c = cos 2π/5 is algebraic over Q.

Theorem 11.11. Let ± be algebraic over F and let p(x) be an irreducible poly-

nomial of degree n over F with ± as a root. Then

F (±) ∼ F [x]/(p(x)),

=

and the elements of F (±) can be written uniquely in the form

c0 + c1 ± + c2 ± 2 + · · · + cn’1 ± n’1 where ci ∈ F.

Proof. De¬ne the ring morphism f : F [x] ’ F (±) by f (q(x)) = q(±). The

kernel of f is an ideal of F [x]. By Corollary 10.3, all ideals in F [x] are principal;

thus Kerf = (r(x)) for some r(x) ∈ F [x]. Since p(±) = 0, p(x) ∈ Kerf , and

so r(x)|p(x). Since p(x) is irreducible, p(x) = kr(x) for some nonzero element

k of F . Therefore, Kerf = (r(x)) = (p(x)).

By the morphism theorem,

F [x]/(p(x)) ∼ Imf ⊆ F (±).

=

Now, by Theorem 10.17, F [x]/(p(x)) is a ¬eld; thus Imf is a sub¬eld of F (±)

that contains F and ±. Since Imf cannot be a smaller ¬eld than F (±), it follows

that Imf = F (±) and F [x]/(p(x)) ∼ F (±).

=

The unique form for the elements of F (±) follows from the isomorphism

above and Theorem 10.8.

Corollary 11.12. If ± is a root of the polynomial p(x) of degree n, irreducible

over F , then [F (±): F ] = n.

Proof. By Theorems 11.11 and 11.5, [F (±) : F ] = [F [x]/(p(x)) : F ] = n.

√ √ √

For example, Q( 2) √ Q[x]/(x 2 ’ 2) and [Q( 2) : Q] = 2. Also, Q( 4 7i) ∼

∼

= =

√

Q[x]/(x ’ 7) and [Q( 7i) : Q] = 4 because 7 i is a root of x ’ 7, which

4 4

4 4

is irreducible over Q, by Eisenstein™s criterion (Theorem 9.30).

ALGEBRAIC NUMBERS 223

Lemma 11.13. Let p(x) be an irreducible polynomial over the ¬eld F . Then F

has a ¬nite extension ¬eld K in which p(x) has a root.

Proof. Let p(x) = a0 + a1 x + a2 x 2 + · · · + an x n and denote the ideal (p(x))

by P . By Theorem 11.5, K = F [x]/P is a ¬eld extension of F of degree n

whose elements are cosets of the form P + f (x). The element P + x ∈ K is a

root of p(x) because

a0 + a1 (P + x) + a2 (P + x)2 + · · · + an (P + x)n

= a0 + (P + a1 x) + (P + a2 x 2 ) + · · · + (P + an x n )

= P + (a0 + a1 x + a2 x 2 + · · · + an x n ) = P + p(x)

= P + 0,

and this is the zero element of the ¬eld K.

Theorem 11.14. If f (x) is any polynomial over the ¬eld F , there is an extension

¬eld K of F over which f (x) splits into linear factors.

Proof. We prove this by induction on the degree of f (x). If deg f (x) 1,

there is nothing to prove.

Suppose that the result is true for polynomials of degree n ’ 1. If f (x) has

degree n, we can factor f (x) as p(x)q(x), where p(x) is irreducible over F .

By Lemma 11.13, F has a ¬nite extension K in which p(x) has a root, say ±.

Hence, by the factor theorem,

f (x) = (x ’ ±)g(x) where g(x) is of degree n ’ 1 in K [x].

By the induction hypothesis, the ¬eld K has a ¬nite extension, K, over which

g(x) splits into linear factors. Hence f (x) also splits into linear factors over K

and, by Theorem 11.6, K is a ¬nite extension of F .

Let us now look at the development of the complex numbers from the real

numbers. The reason for constructing the complex numbers is that certain equ-

ations, such as x 2 + 1 = 0, have no solution in R. Since x 2 + 1 is a quadratic

polynomial in R[x] without roots, it is irreducible over R. In the above manner,

we can extend the real ¬eld to

R[x]/(x 2 + 1) = {a + bx|a, b ∈ R}.

In this ¬eld extension

(0 + 1x)2 = ’1 since x 2 ≡ ’1 mod(x 2 + 1).

Denote the element 0 + 1x by i, so that i 2 = ’1 and i is a root of the equation

x 2 + 1 = 0 in this extension ¬eld. The ¬eld of complex numbers, C, is de¬ned

to be R(i) and, by Theorem 11.11, there is an isomorphism

ψ: R[x]/(x 2 + 1) ’ R(i)

224 11 FIELD EXTENSIONS

de¬ned by ψ(a + bx) = a + bi. Since

(a + bx) + (c + dx) ≡ (a + c) + (b + d)x mod(x 2 + 1)

and

(a + bx)(c + dx) ≡ ac + (ad + bc)x + bdx 2 mod(x 2 + 1)

≡ (ac ’ bd) + (ad + bc)x mod(x 2 + 1),

addition and multiplication in C = R(i) are de¬ned in the standard way by

(a + bi) + (c + di) = (a + c) + (b + d)i

and

(a + bi)(c + di) = (ac ’ bd) + (ad + bc)i.

Example 11.15. Find [Q(cos 2π/5) : Q].

Solution. We know from Example 11.10 that cos 2π/5 is algebraic over Q

and is a root of the polynomial 16x 5 ’ 20x 3 + 5x ’ 1. Using the same methods,

we can show that cos 2kπ/5 is also a root of this equation for each k ∈ Z.

Hence we see from Figure 11.1 that its roots are 1, cos 2π/5 = cos 8π/5, and

cos 4π/5 = cos 6π/5. Therefore, (x ’ 1) is a factor of the polynomial and

16x 5 ’ 20x 3 + 5x ’ 1 = (x ’ 1)(16x 4 + 16x 3 ’ 4x 2 ’ 4x + 1)

= (x ’ 1)(4x 2 + 2x ’ 1)2 .

It follows that cos 2π/5 and cos 4π/5 are roots of the quadratic 4x 2 + 2x ’

√

1 so by the quadratic formula, these roots are (’1 ± 5)/4. Since cos 2π/5

is positive,

√ √

cos 2π/5 = ( 5 ’ 1)/4 and cos 4π/5 = (’ 5 ’ 1)/4.

Therefore, Q(cos 2π/5) ∼ Q[x]/(4x 2 + 2x ’ 1) because 4x 2 + 2x ’ 1 is irre-

=

ducible over Q. By Corollary 11.12, [Q(cos 2π/5) : Q] = 2.

q = 2p

5

q = 4p

5

q=0

cos q

1

q = 6p

5

q = 8p

5

Figure 11.1. Values of cos(2kπ/5).

GALOIS FIELDS 225

√

Proposition 11.16. If [K : F ] = 2, where F ⊇ Q, then K = F ( γ ) for some

γ ∈ F.

Proof. K is a vector space of dimension 2 over F . Extend {1} to a basis {1, ±}

for K over F , so that K = {a± + b|a, b ∈ F }.

Now K is a ¬eld, so ± 2 ∈ K and ± 2 = a± + b for some a, b ∈ F . Hence

(± ’ (a/2))2 = b + (a 2 /4). Put β = ± ’ (a/2). Then {1, β} is also a basis for

√

K over F , and K = F (β) where β 2 = b + (a 2 /4) = γ ∈ F . Hence K = F ( γ ).

Proposition 11.17. If F is an extension ¬eld of R of ¬nite degree, then F is

isomorphic to R or C.

Proof. Let [F : R] = n. If n = 1, then F is equal to R. Otherwise, n > 1

and F contains some element ± not in R. Now {1, ±, ± 2 , . . . , ± n } is a linearly

dependent set of elements of F over R, because it contains more than n elements;

hence there exist real numbers »0 , »1 , . . . , »n , not all zero, such that

»0 + »1 ± + · · · + »n ± n = 0.

The element ± is therefore algebraic over R so since the only irreducible poly-

nomials over R have degree 1 or 2, ± must satisfy a linear or quadratic equation

over R. If it satis¬es a linear equation, then ± ∈ R, contrary to our hypothesis.

√

Therefore, [R(±) : R] = 2, and, by Proposition 11.16, R(±) = R( γ ). In this

case γ must be negative because R contains all positive square roots; hence

√

γ = ir, where r ∈ R and R(±) = R(i) ∼ C. =

Therefore, the ¬eld F contains a sub¬eld C = R(±) isomorphic to the complex

numbers and [F : C] = [F : R]/2, which is ¬nite. By an argument similar to

the above, any element of C is the root of an irreducible polynomial over C.

However, the only irreducible polynomials over C are the linear polynomials,

and all their roots lie in C. Hence F = C is isomorphic to C.

Example 11.18. [R : Q] is in¬nite.

√

Solution. The real number n 2 is a root of the polynomial x n ’ 2, which, by

Eisenstein™s criterion, is irreducible over Q. If [R : Q] were ¬nite, we could use

Theorem 11.6 and Corollary 11.12 to show that

√ √ √

[R : Q] = [R : Q( 2)][Q( 2) : Q] = [R : Q( 2)]n.

n n n

This is a contradiction, because no ¬nite integer is divisible by every integer n.

Hence [R : Q] must be in¬nite.

GALOIS FIELDS

In this section we investigate the structure of ¬nite ¬elds; these ¬elds are called

´

Galois ¬elds in honor of the mathematician Evariste Galois (1811“1832).

226 11 FIELD EXTENSIONS

We show that the element 1 in any ¬nite ¬eld generates a sub¬eld isomorphic

to Zp , for some prime p called the characteristic of the ¬eld. Hence a ¬nite ¬eld

is some ¬nite extension of the ¬eld Zp and so must contain p m elements, for

some integer m.

The characteristic can be de¬ned for any ring, and we give the general de¬-

nition here, even though we are mainly interested in its application to ¬elds.

For any ring R, de¬ne the ring morphism f : Z ’ R by f (n) = n · 1R where

1R is the identity of R. The kernel of f is an ideal of the principal ideal ring Z;

hence Kerf = (q) for some q 0. The generator q 0 of Kerf is called the

characteristic of the ring R. If a ∈ R then qa = q(1R a) = (q1R )a = 0, Hence

if q > 0 the characteristic of R is the least integer q > 0 for which qa = 0, for

all a ∈ R. If no such number exists, the characteristic of R is zero. For example,

the characteristic of Z is 0, and the characteristic of Zn is n.

Proposition 11.19. The characteristic of an integral domain is either zero or

prime.

Proof. Let q be the characteristic of an integral domain D. By applying the

morphism theorem to f : Z ’ D, de¬ned by f (1) = 1, we see that

if q = 0

Zq

f (Z) ∼

=

if q = 0.

Z

But f (Z) is a subring of an integral domain; therefore, it has no zero divisors,

and, by Theorem 8.11, q must be zero or prime.

The characteristic of the ¬eld Zp is p, while Q, R, and C have zero charac-

teristic.

Proposition 11.20. If the ¬eld F has prime characteristic p, then F contains a

sub¬eld isomorphic to Zp . If the ¬eld F has zero characteristic, then F contains

a sub¬eld isomorphic to the rational numbers, Q.

Proof. From the proof of Proposition 11.19 we see that F contains the sub-

ring f (Z), which is isomorphic to Zp if F has prime characteristic p. If the

characteristic of F is zero, f : Z ’ f (Z) is an isomorphism. We show that F

contains the ¬eld of fractions of f (Z) and that this is isomorphic to Q.

Let Q = {xy ’1 ∈ F |x, y ∈ f (Z)}, a subring of F . De¬ne the function

f˜: Q ’ Q

by f˜(a/b) = f (a) · f (b)’1 . Since rational numbers are de¬ned as equivalence

classes, we have to check that f˜ is well de¬ned. We can show that f˜(a/b) =

f˜(c/d) if a/b = c/d. Furthermore, it can be veri¬ed that f˜ is a ring isomorphism.

Hence Q is isomorphic to Q.

GALOIS FIELDS 227

Corollary 11.21. The characteristic of a ¬nite ¬eld is nonzero.

Theorem 11.22. If F is a ¬nite ¬eld, it has p m elements for some prime p and

some integer m.

Proof. By the previous results, F has characteristic p, for some prime p, and

contains a sub¬eld isomorphic to Zp . We identify this sub¬eld with Zp so that F

is a ¬eld extension of Zp . The degree of this extension must be ¬nite because F

is ¬nite. Let [F : Zp ] = m and let {f1 , . . . , fm } be a basis of F over Zp , so that

F = {»1 f1 + · · · + »m fm |»i ∈ Zp }.

There are p choices for each »i ; therefore, F contains p m elements.

A ¬nite ¬eld with p m elements is called a Galois ¬eld of order p m and is

denoted by GF(p m ). It can be shown that for a given prime p and positive integer

m, a Galois ¬eld GF(p m ) exists and that all ¬elds of order p m are isomorphic.

See Stewart [35] or Nicholson [11] for a proof of these facts. For m = 1, the

integers modulo p, Zp , is a Galois ¬eld of order p.

From Theorem 11.22 it follows that GF(p m ) is a ¬eld extension of Zp of

degree m. Each ¬nite ¬eld GF(p m ) can be constructed by ¬nding a polynomial

q(x) of degree m, irreducible in Zp [x], and de¬ning

GF(p m ) = Zp [x]/(q(x)).

By Lemma 11.13 and Corollary 11.12, there is an element ± in GF(pm ), such

that q(±) = 0, and GF(p m ) = Zp (±), the ¬eld obtained by adjoining ± to Zp .

For example, GF(4) = Z2 [x]/(x 2 + x + 1) = Z2 (±) = {0, 1, ±, ± + 1}, where

± 2 + ± + 1 = 0. Rewriting Table 10.2, we obtain Table 11.1 for GF(4).

Example 11.23. Construct a ¬eld GF(125).

Solution. Since 125 = 53 , we can construct such a ¬eld if we can ¬nd an

irreducible polynomial of degree 3 over Z5 .

A reducible polynomial of degree 3 must have a linear factor. Therefore, by

the factor theorem, p(x) = x 3 + ax 2 + bx + c is irreducible in Z5 [x] if and only

if p(n) = 0 for n = 0, 1, 2, 3, 4 in Z5 .

TABLE 11.1. Galois Field GF (4)

+ ±+1 · ±+1

0 1 0 1

± ±

±+1

0 0 1 0 0 0 0 0

±

±+1 ±+1

1 1 0 1 0 1

± ±

±+1 ±+1

0 1 0 1

± ± ± ±

±+1 ±+1 ±+1 ±+1

1 0 0 1

± ±

228 11 FIELD EXTENSIONS

By trial and error, we ¬nd that the polynomial p(x) = x 3 + x + 1 is irre-

ducible because p(0) = 1, p(1) = 3, p(2) = 11 = 1, p(3) = 31 = 1, and p(4) =

p(’1) = ’1 = 4 in Z5 . Hence

GF(125) = Z5 [x]/(x 3 + x + 1).

Note that (x 3 + x + 1) is not the only irreducible polynomial of degree 3

over Z5 . For example, (x 3 + x 2 + 1) is also irreducible. But Z5 [x]/(x 3 + x + 1)

is isomorphic to Z5 [x]/(x 3 + x 2 + 1).

PRIMITIVE ELEMENTS

The elements of a Galois ¬eld GF(p m ) can be written as

a0 + a1 ± + · · · + am’1 ± m’1 |ai ∈ Zp

where ± is a root of a polynomial q(x) of degree m irreducible over Zp . Addition

is easily performed using this representation, because it is simply addition of

polynomials in Zp [±]. However, multiplication is more complicated and requires

repeated use of the relation q(±) = 0. We show that by judicious choice of ±,

the elements of GF(p m ) can be written as

’2 ’1

m m

= 1.

0, 1, ±, ± 2 , ± 3 , . . . , ± p where ± p

This element ± is called a primitive element of GF(p m ), and multiplication is

easily calculated using powers of ±; however, addition is much harder to perform

using this representation.

For example, in GF(4) = Z2 (±) = {0, 1, ±, ± 2 } where ± + 1 = ± 2 and ± 3 = 1,

and the tables are given in Table 11.2.

If F is any ¬eld and F — = F ’ {0}, we know that (F — , ·) is an abelian group

under multiplication. We now show that the nonzero elements of a ¬nite ¬eld

form a cyclic group under multiplication; the generators of this cyclic group

are the primitive elements of the ¬eld. To prove this theorem, we need some

preliminary results about the orders of elements in an abelian group.

TABLE 11.2. Galois Field GF (4) in Terms of a

Primitive Element

+ ·

±2 ±2

0 1 0 1

± ±

±2

0 0 1 0 0 0 0 0

±

±2 ±2

1 1 0 1 0 1

± ±

±2 ±2

0 1 0 1

± ± ± ±

±2 ±2 ±2 ±2

1 0 0 1

± ±

PRIMITIVE ELEMENTS 229

Lemma 11.24. If g and h are elements of an abelian group of orders a and b,

respectively, there exists an element of order lcm(a, b).

Proof. Let a = p1 1 p2 2 · · · ps s and b = p1 1 p2 2 · · · ps s , where the pi are distinct

aa bb

a b

primes and ai 0, bi 0 for each i. For each i de¬ne

if ai bi 0 if ai bi

ai

xi = and yi = .

0 if ai < bi if ai < bi

bi

y y y

xx

If x = p1 1 p2 2 · · · ps s and y = p1 1 p2 2 · · · ps s , then x|a and y|b, so g a/x has order

x

x and hb/y has order y. Moreover, gcd(x, y) = 1, so g a/x hb/y has order xy

by Lemma 4.36. But xy = lcm(a, b) by Theorem 15 of Appendix 2 because

xi + yi = max(ai , bi ) for each i.

Lemma 11.25. If the maximum order of the elements of an abelian group G is

r, then x r = e for all x ∈ G.

Proof. Let g ∈ G be an element of maximal order r. If h is an element of order

t, there is an element of order lcm(r, t) by Lemma 11.24. Since lcm(r, t) r,

t divides r. Therefore, hr = e.

Theorem 11.26. Let GF(q)— be the set of nonzero elements in the Galois ¬eld

GF(q). Then (GF(q)— , ·) is a cyclic group of order q ’ 1.

Proof. Let r be the maximal order of elements of (GF(q)— , ·). Then, by

Lemma 11.25,

x r ’ 1 = 0 for all x ∈ GF(q)— .

Hence every nonzero element of the Galois ¬eld GF(q) is a root of the polynomial

x r ’ 1 and, by Theorem 9.6, a polynomial of degree r can have at most r roots

over any ¬eld; therefore, r q ’ 1. But, by Lagrange™s theorem, r|(q ’ 1); it

follows that r = q ’ 1.

(GF(q)— , ·) is therefore a group of order q ’ 1 containing an element of order

q ’ 1 and hence must be cyclic.

A generator of the cyclic group (GF(q)— , ·) is called a primitive element

of GF(q). For example, in GF(4) = Z2 (±), the multiplicative group of nonzero

elements, GF(4)— , is a cyclic group of order 3, and both nonidentity elements ±

and ± + 1 are primitive elements.

If ± is a primitive element in the Galois ¬eld GF(q), where q is the power of

a prime p, then GF(q) is the ¬eld extension Zp (±) and

GF(q)— = {1, ±, ± 2 , . . . , ± q’2 }.

Hence

GF(q) = {0, 1, ±, ± 2 , . . . , ± q’2 }.

230 11 FIELD EXTENSIONS

Example 11.27. Find all the primitive elements in GF(9) = Z3 (±), where

± 2 + 1 = 0.

Solution. Since x 2 + 1 is irreducible over Z3 , we have

GF(9) = Z3 [x]/(x 2 + 1) = {a + bx|a, b ∈ Z3 }.

The nonzero elements form a cyclic group GF(9)— of order 8; hence the multi-

plicative order of each element is either 1, 2, 4, or 8.

In calculating the powers of each element, we use the relationship ± 2 = ’1 =

2. From Table 11.3, we see that 1 + ±, 2 + ±, 1 + 2±, and 2 + 2± are the primi-

tive elements of GF(9).

Proposition 11.28.

(i) zq’1 = 1 for all elements z ∈ GF(q)— .

(ii) zq = z for all elements z ∈ GF(q).

(iii) If GF(q) = {±1 , ±2 , . . . , ±q }, then zq ’ z factors over GF(q) as

(z ’ ±1 )(z ’ ±2 ) · · · (z ’ ±q ).

Proof. We have already shown that (i) is implied by Lemma 11.25. Part (ii)

follows immediately because 0 is the only element of GF(q) that is not in GF(q)— .

The polynomial zq ’ z, of degree q, can have at most q roots over any ¬eld.

By (ii), all elements of GF(q) are roots over GF(q); hence zq ’ z factors into

q distinct linear factors over GF(q).

For example, in GF(4) = Z2 [x]/(x 2 + x + 1) = {0, 1, ±, ± + 1}, and we have

(z + 0)(z + 1)(z + ±)(z + ± + 1) = (z2 + z)(z2 + z + ± 2 + ±)

= (z2 + z)(z2 + z + 1)

= z4 + z = z4 ’ z.

TABLE 11.3. Nonzero Elements of GF (9)

x2 x4 x8

Element x Order Primitive

1 1 1 1 1 No

2 1 1 1 2 No

2 1 1 4 No

±

1+± 2± 2 1 8 Yes

2+± 2 1 8 Yes

±

2± 2 1 1 4 No

1 + 2± 2 1 8 Yes

±

2 + 2± 2± 2 1 8 Yes

PRIMITIVE ELEMENTS 231

An irreducible polynomial g(x), of degree m over Zp , is called a primitive

polynomial if g(x)|(x k ’ 1) for k = p m ’ 1 and for no smaller k.

Proposition 11.29. The irreducible polynomial g(x) ∈ Zp [x] is primitive if and

only if x is a primitive element in Zp [x]/(g(x)) = GF(p m ).

Proof. The following statements are equivalent:

x is a primitive element in GF(p m ) = Zp [x]/(g(x)).

(i)

x k = 1 in GF(p m ) for k = p m ’ 1 and for no smaller k.

(ii)

x k ’ 1 ≡ 0 mod g(x) for k = p m ’ 1 and for no smaller k.

(iii)

g(x)|(x k ’ 1) for k = p m ’ 1 and for no smaller k.

(iv)

For example, x 2 + x + 1 is primitive in Z2 [x]. From Example 11.27, we see

that x 2 + 1 is not primitive in Z3 [x]. However, 1 + ± and 1 + 2± = 1 ’ ± are

primitive elements, and they are roots of the polynomial

(x ’ 1 ’ ±)(x ’ 1 + ±) = (x ’ 1)2 ’ ± 2 = x 2 + x + 2 ∈ Z3 [x].

Hence x 2 + x + 2 is a primitive polynomial in Z3 [x]. Also, x 2 + 2x + 2 is

another primitive polynomial in Z3 [x] with roots 2 + ± and 2 + 2± = 2 ’ ±.

Example 11.30. Let ± be a root of the primitive polynomial x 4 + x + 1 ∈ Z2 [x].

Show how the nonzero elements of GF(16) = Z2 (±) can be represented by the

powers of ±.

Solution. The representation is given in Table 11.4.

Arithmetic in GF(16) can very easily be performed using Table 11.4. Addition

is performed by representing elements as polynomials in ± of degree less than 4,

whereas multiplication is performed using the representation of nonzero elements

as powers of ±. For example,

1 + ± + ±3 ±7

+ ± + ± = 13 + ± + ± 2

2

1+± 2 + ±3 ±

= ± ’6 + ± + ± 2

= ±9 + ± + ±2 since ± 15 = 1

= ± + ±3 + ± + ±2

= ±2 + ±3.

The concept of primitive polynomials is useful in designing feedback shift

registers with a long cycle length. Consider the circuit in Figure 11.2, in which

the square boxes are delays of one unit of time, and the circle with a cross inside

represents a modulo 2 adder.

232 11 FIELD EXTENSIONS

TABLE 11.4. Representation of GF (16)

±0 ±1 ±2 ±3

Element

=0

0 0 0 0 0

=1

±0 1 0 0 0

=

±1 0 1 0 0

±

=

±2 ±2 0 0 1 0

=

±3 ±3 0 0 0 1

=1+±

±4 1 1 0 0

= + ±2

±5 0 1 1 0

±

= ±2 + ±3

±6 0 0 1 1

=1+± + ±3

±7 1 1 0 1

=1 +±

±8 2

1 0 1 0

= + ±3

±9 0 1 0 1

±

=1+± + ±2

± 10 1 1 1 0

= + ±2 + ±3

± 11 0 1 1 1

±

=1+± + ±2 + ±3

± 12 1 1 1 1

=1 + ±2 + ±3

± 13 1 0 1 1

=1 + ±3

± 14 1 0 0 1

± 15 = 1

a4 = 1 + a

a0 a1 a2 a3

Figure 11.2. Feedback shift register.

If the delays are labeled by a representation of the elements of GF(16), a

single shift corresponds to multiplying the element of GF(16) by ±. Hence, if

the contents of the delays are not all zero initially, this shift register will cycle

through 15 different states before repeating itself. In general, it is possible to

construct a shift register with n delay units that will cycle through 2n ’ 1 different

states before repeating itself. The feedback connections have to be derived from a

primitive polynomial of degree n over Z2 . Such feedback shift registers are useful

in designing error-correcting coders and decoders, random number generators,

and radar transmitters. See Chapter 14 of this book and, Lidl and Niederreiter [34,

Chap. 6], or Stone [22, Chap. 9].

EXERCISES 233

EXERCISES

For Exercises 11.1 to 11.4, write out the addition and multiplication tables for

the ¬elds.

11.1. GF(5). 11.2. GF(7).

11.3. GF(9). 11.4. GF(8).

For Exercises 11.5 to 11.10, in each case ¬nd, if possible, an irreducible polyno-

mial of degree n over F .

11.5. n = 3, F = Z11 . 11.6. n = 3, F = Q.