<<

. 9
( 13)



>>



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.

<<

. 9
( 13)



>>