<< стр. 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 , , . . . , [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
(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 ). 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  or Nicholson  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
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)СОДЕРЖАНИЕ >>