8.54. Let T = {f : R ’ R|f (x) = a cos x + b sin x, a, b ∈ R}. De¬ne addition

of two such trigonometric functions in the usual way and de¬ne convolu-

tion by

2π

(f — g)(x) = f (t)g(x ’ t) dt.

0

Show that (T , +, —) is a ¬eld.

n

a0

8.55. Let Tn = f : R ’ R|f (x) = + (ar cos rx + br sin rx), ar , br ∈ R .

2 r=1

Show that (Tn , +, —) is a commutative ring where addition and convolution

are de¬ned as in Exercise 8.54. What is the multiplicative identity? Is the

ring an integral domain?

8.56. If R is any ring, de¬ne R(i) = {a + bi|a, b ∈ R} to be the set of all formal

sums a + bi, where a and b are in R. As in C, we declare that a + bi =

a1 + b1 i if and only if a = a1 and b = b1 . If we insist that i 2 = ’1 and

ai = ia for all a ∈ R, then the ring axioms determine the addition and

multiplication in R(i):

(r + si) + (r1 + s1 i) = (r + r1 ) + (s + s1 )i

(r + si)(r1 + s1 i) = (rr1 ’ ss1 ) + (rs1 + sr1 )i.

Thus, for example, R(i) = C.

(a) Show that R(i) is a ring, commutative if R is commutative.

(b) If R is commutative, show that a + bi is has an inverse in R(i) if and

only if a 2 + b2 has an inverse in R.

(c) Show that Z3 (i) is a ¬eld of nine elements.

(d) Is C(i) a ¬eld? Is Z5 (i) a ¬eld? Give reasons.

8.57. If R is a ring call e ∈ R an idempotent if e2 = e. Call R “tidy” if some

positive power of every element is an idempotent.

(a) Show that every ¬nite ring is tidy. [Hint: If a ∈ R, show that a m+n =

a m for some n 1.]

(b) If R is tidy, show that uv = 1 in R implies that vu = 1.

(c) If R is a commutative tidy ring, show that every element of R is either

invertible or a zero divisor.

9

POLYNOMIAL AND

EUCLIDEAN RINGS

Polynomial functions and the solution of polynomial equations are a basic part

of mathematics. One of the important uses of ring and ¬eld theory is to extend

a ¬eld to a larger ¬eld so that a given polynomial has a root. For example,

the complex number ¬eld can be obtained by enlarging the real ¬eld so that all

quadratic equations will have solutions.

Before we are able to extend ¬elds, we need to investigate the ring of poly-

nomials, F [x], with coef¬cients in a ¬eld F . This polynomial ring has many

properties in common with the ring of integers; both F [x] and Z are integral

domains, but not ¬elds. Moreover, both rings have division and euclidean algo-

rithms. These algorithms are extremely useful, and rings with such algorithms

are called euclidean rings.

EUCLIDEAN RINGS

Long division of integers gives a method for dividing one integer by another to

obtain a quotient and a remainder. The fact that this is always possible is stated

formally in the division algorithm.

Theorem 9.1. Division Algorithm for Integers. If a and b are integers and b

is nonzero, then there exist unique integers q and r such that

a = qb + r r < |b|.

and 0

Proof. If b > 0, then |b| = b, so this restates Theorem 7 in Appendix 1. If b <

0, then ’b > 0, so the same theorem gives a = q(’b) + r, where

0 r < (’b). Since |b| = ’b in this case, this gives a = (’q)b + r, where

0 r < |b|.

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.

180

EUCLIDEAN RINGS 181

The integer r is called the remainder in the division of a by b, and q is called

the quotient.

What other rings, besides the integers, have a division algorithm? In a ¬eld, we

can always divide any element exactly by a nonzero element. If a ring contains

zero divisors, the cancellation property does not hold, and we cannot expect to

obtain a unique quotient. This leaves integral domains, and the following kinds

contain a useful generalization of the division algorithm.

An integral domain R is called a euclidean ring if for each nonzero element

a ∈ R, there exists a nonnegative integer δ(a) such that:

(i) If a and b are nonzero elements of R, then δ(a) δ(ab).

(ii) For every pair of elements a, b ∈ R with b = 0, there exist elements

q, r ∈ R such that

a = qb + r where r = 0 or (division algorithm)

δ(r) < δ(b).

Theorem 9.1 shows that the ring Z of integers is a euclidean ring if we take

δ(b) = |b|, the absolute value of b, for all b ∈ Z. A ¬eld is trivially a euclidean

ring when δ(a) = 1 for all nonzero elements a of the ¬eld. We now show that

the ring of polynomials, with coef¬cients in a ¬eld, is a euclidean ring when we

take δ(g(x)) to be the degree of the polynomial g(x).

Theorem 9.2. Division Algorithm for Polynomials. Let f (x), g(x) be ele-

ments of the polynomial ring F [x], with coef¬cients in the ¬eld F. If g(x) is

not the zero polynomial, there exist unique polynomials q(x), r(x) ∈ F [x] such

that

f (x) = q(x) · g(x) + r(x)

where either r(x) is the zero polynomial or deg r(x) < deg g(x).

Proof. If f (x) is the zero polynomial or deg f (x) < deg g(x), then writing

f (x) = 0 · g(x) + f (x), we see that the requirements of the algorithm are ful-

¬lled.

If deg f (x) = deg g(x) = 0, then f (x) and g(x) are nonzero constant poly-

’1

nomials a0 and b0 , respectively. Now f (x) = (a0 b0 )g(x), and the algorithm

holds.

We prove the other cases by induction on the degree of f (x). Suppose that,

when we divide by a ¬xed polynomial g(x), the division algorithm holds for

polynomials of degree less than n. Let f (x) = a0 + · · · + an x n and g(x) = b0 +

· · · + bm x m where an = 0, bm = 0. If n < m, we have already shown that the

algorithm holds.

Suppose that n m and put

’1

f1 (x) = f (x) ’ an bm x n’m g(x)

182 9 POLYNOMIAL AND EUCLIDEAN RINGS

so that deg f1 (x) < n. By the induction hypothesis

f1 (x) = q1 (x) · g(x) + r(x) where either r(x) = 0 or deg r(x) < deg g(x).

’1 ’1

Hence f (x) = an bm x n’m g(x) + f1 (x) = {an bm x n’m + q1 (x)} · g(x) + r(x),

which is a representation of the required form. The algorithm now follows by

induction, starting with n = m ’ 1 if m = 0, or with n = 0 if m = 0.

The uniqueness of the quotient, g(x), and of the remainder, r(x), follows in

a similar way to the uniqueness of the quotient and remainder in the division

algorithm for integers (Theorem 7, Appendix 2).

The quotient and remainder polynomials can be calculated by long division

of polynomials.

Example 9.3. Divide x 3 + 2x 2 + x + 2 by x 2 + 2 in Z3 [x].

Solution. Write Z3 = {0, 1, 2} for convenience.

x+2

x2 + 2 x 3 +2x 2 + x+2

x3+ +2x

2x 2 +2x+2

+1

2x 2

2x+1

Hence x 3 + 2x 2 + x + 2 = (x + 2)(x 2 + 2) + (2x + 1).

If we divide by a polynomial of degree 1, the remainder must be a constant.

This constant can be found as follows.

Theorem 9.4. Remainder Theorem. The remainder when the polynomial f (x)

is divided by (x ’ ±) in F [x] is f (±).

Proof. By the division algorithm, there exist q(x), r(x) ∈ F [x] with f (x) =

q(x)(x ’ ±) + r(x), where r(x) = 0 or deg r(x) < 1. The remainder is therefore

a constant r0 ∈ F and f (x) = q(x)(x ’ ±) + r0 . Substituting ± for x, we obtain

the result f (±) = r0 .

Theorem 9.5. Factor Theorem. The polynomial (x ’ ±) is a factor of f (x) in

F [x] if and only if f (±) = 0.

Proof. We can write f (x) = q(x)(x ’ ±) for some q(x) ∈ F [x] if and only

if f (x) has remainder 0 when divided by (x ’ ±). By the remainder theorem,

this happens if and only if f (±) = 0.

EUCLIDEAN RINGS 183

An element ± is called a root of a polynomial f (x) if f (±) = 0. The fac-

tor theorem shows that (x ’ ±) is a factor of f (x) if and only if ± is a root

of f (x).

Theorem 9.6. A polynomial of degree n over a ¬eld F has at most n roots in F .

Proof. We prove the theorem by induction on the degree n. A polynomial of

degree 0 consists of only a nonzero constant and therefore has no roots.

Assume that the theorem is true for polynomials of degree n ’ 1 and let

f (x) ∈ F [x] be a polynomial of degree n. If f (x) has no roots, the theorem

holds. If f (x) does have roots, let ± be one such root. By the factor theorem,

we can write

f (x) = (x ’ ±)g(x),

and by Proposition 8.22, deg g(x) = n ’ 1.

Since the ¬eld F has no zero divisors, f (β) = 0 if and only if (β ’ ±) = 0

or g(β) = 0. Therefore, any root of f (x) is either equal to ± or is a root of g(x).

By the induction hypothesis, g(x) has, at most, n ’ 1 roots, so f (x) has, at most,

n roots.

Example 9.7. Show that the ring of gaussian integers, Z[i] = {a + ib|a, b ∈ Z},

is a euclidean ring with δ(a + ib) = a 2 + b2 .

Solution. Z[i] is a subring of the complex numbers, C, and therefore is an

integral domain.

If z ∈ Z[i], then δ(z) = zz, where z is the conjugate of z in the complex

numbers. For any nonzero complex number z, δ(z) > 0, and for two nonzero

gaussian integers z and w, δ(z · w) = δ(z) · δ(w).

To prove the division algorithm in Z[i], let z and w be gaus-

sian integers where w = 0. Then z/w is a complex number, c +

id, where c, d ∈ Q. Choose integers, a, b as in Figure 9.1 so that

|c ’ a| 1 and |d ’ b| 1 . Then z/w = a + ib + [(c ’ a) + i(d ’ b)] so

2 2

z = (a + ib)w + [(c ’ a) + i(d ’ b)]w. Now δ([(c ’ a) + i(d ’ b)]w) =

z = c + id

w

’1 + i i

a + ib

’1 0 1 2

Complex numbers with the elements of Z[i] circled.

Figure 9.1.

184 9 POLYNOMIAL AND EUCLIDEAN RINGS

δ((c ’ a) + i(d ’ b))δ(w) = [(c ’ a)2 + (d ’ b)2 ]δ(w) ( 1 + 1 )δ(w) < δ(w).

4 4

Hence Z[i] is a euclidean ring.

EUCLIDEAN ALGORITHM

The division algorithm allows us to generalize the concepts of divisors and

greatest common divisors to any euclidean ring. Furthermore, we can produce a

euclidean algorithm that will enable us to calculate greatest common divisors.

If a, b, q are three elements in an integral domain such that a = qb, we say that

b divides a or that b is a factor of a and write b|a. For example, (2 + i)|(7 + i)

in the gaussian integers, Z[i], because 7 + i = (3 ’ i)(2 + i).

Proposition 9.8. Let a, b, c be elements in an integral domain R.

(i) If a|b and a|c, then a|(b + c).

(ii) If a|b, then a|br for any r ∈ R.

(iii) If a|b and b|c, then a|c.

Proof. These results follow immediately from the de¬nition of divisibility.

By analogy with Z, if a and b are elements in an integral domain R, then the

element g ∈ R is called a greatest common divisor of a and b, and is written

g = gcd(a, b), if the following hold:

(i) g|a and g|b.

(ii) If c|a and c|b, then c|g.

The element l ∈ R is called a least common multiple of a and b, and is

written l = lcm(a, b), if the following hold:

(i) a|l and b|l.

(ii) If a|k and b|k, then l|k.

For example, 4 and ’4 are greatest common divisors, and 60 and ’60 are

least common multiples, of 12 and 20 in Z. Note that in Z it is customary to

choose the positive value in each case to make it unique (see Appendix 2).

Theorem 9.9. Let R be a euclidean ring. Any two elements a and b in R have

a greatest common divisor g. Moreover, there exist s, t ∈ R such that

g = sa + tb.

Proof. If a and b are both zero, their greatest common divisor is zero, because

r|0 for any r ∈ R.

EUCLIDEAN ALGORITHM 185

Suppose that at least one of a and b is nonzero. By the well-ordering axiom

(Appendix 2), let g be a nonzero element for which δ(g) is minimal in the set

I = {xa + yb|x, y ∈ R}. We can write g = sa + tb for some s, t ∈ R.

Since R is a euclidean ring, a = hg + r, where r = 0 or δ(r) < δ(g). There-

fore, r = a ’ hg = a ’ h(sa + tb) = (1 ’ hs)a ’ htb ∈ I . Since g was an

element for which δ(g) was minimal in I , it follows that r must be zero, and

g|a. Similarly, g|b.

If c|a and c|b, so that a = kc and b = lc, then g = sa + tb = skc + tlc =

(sk + tl)c and c|g. Therefore, g = gcd(a, b).

Theorem 9.9 shows that greatest common divisors exist in any euclidean ring,

but does not give a method for ¬nding them. In fact, they can be computed using

the following general euclidean algorithm.

Theorem 9.10. Euclidean Algorithm. Let a, b be elements of a euclidean ring

R and let b be nonzero. By repeated use of the division algorithm, we can write

a = bq1 + r1 where δ(r1 ) < δ(b)

b = r1 q2 + r2 where δ(r2 ) < δ(r1 )

r1 = r2 q3 + r3 where δ(r3 ) < δ(r2 )

. .

. .

. .

rk’2 = rk’1 qk + rk where δ(rk ) < δ(rk’1 )

rk’1 = rk qk+1 + 0.

If r1 = 0, then b = gcd(a, b); otherwise, rk = gcd(a, b).

Furthermore, elements s, t ∈ R such that

gcd(a, b) = sa + tb

can be found by starting with the equation rk = rk’2 ’ rk’1 qk and successively

working up the sequence of equations above, each time replacing ri in terms of

ri’1 and ri’2 .

Proof. This algorithm must terminate, because δ(b), δ(r1 ), δ(r2 ), . . . is a de-

creasing sequence of nonnegative integers; thus, rk+1 = 0 for some k + 1. The

proof of the algorithm follows as in the proof of Theorem 10 in Appendix 2.

Example 9.11. Find the greatest common divisor of 713 and 253 in Z and ¬nd

two integers s and t such that

713s + 253t = gcd(713, 253).

Solution. By the division algorithm, we have

186 9 POLYNOMIAL AND EUCLIDEAN RINGS

(i) 713 = 2 · 253 + 207 a = 713, b = 253, r1 = 207

(ii) 253 = 1 · 207 + 46 r2 = 46

(iii) 207 = 4 · 46 + 23 r3 = 23

46 = 2 · 23 + 0. r4 = 0

The last nonzero remainder is the greatest common divisor. Hence

gcd(713, 253) = 23.

We can ¬nd the integers s and t by using equations (i)“(iii). We have

23 = 207 ’ 4 · 46 from equation (iii)

= 207 ’ 4(253 ’ 207) from equation (ii)

= 5 · 207 ’ 4 · 253

= 5 · (713 ’ 2 · 253) ’ 4 · 253 from equation (i)

= 5 · 713 ’ 14 · 253.

Therefore, s = 5 and t = ’14.

Example 9.12. Find a greatest common divisor, g(x), of a(x) = 2x 4 + 2 and

b(x) = x 5 + 2 in Z3 [x], and ¬nd s(x), t (x) ∈ Z3 [x], so that

g(x) = s(x) · (2x 4 + 2) + t (x) · (x 5 + 2).

Solution. By repeated use of the division algorithm (see below), we have:

(i) x 5 + 2 = (2x)(2x 4 + 2) + (2x + 2).

(ii) 2x 4 + 2 = (x 3 + 2x 2 + x + 2)(2x + 2) + 1.

(iii) 2x + 2 = (2x + 2) · 1 + 0.

Hence gcd(a(x), b(x)) = 1. From equation (ii) we have

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

= 2x 4 + 2 ’ (x 3 + 2x 2 + x + 2){x 5 + 2 ’ (2x)(2x 4 + 2)}

from equation (i)

= (2x 4 + x 3 + 2x 2 + x + 1)(2x 4 + 2) + (2x 3 + x 2 + 2x + 1)(x 5 + 2).

Therefore,

s(x) = 2x 4 + x 3 + 2x 2 + x + 1

and

t (x) = 2x 3 + x 2 + 2x + 1.

UNIQUE FACTORIZATION 187

x 3 + 2x 2 + x + 2

2x

2x 4 + 2 x 5 +0x 4 +0x 3 +0x 2 +0x+2 2x + 2 2x 4 +0x 3 +0x 2 +0x+2

+x 2x 4 +2x 3

x5

+2

2x+2 x3

x3+ x2

+2

2x 2

2x 2 +2x

x+2

x+1

1

Example 9.13. Find a greatest common divisor of a(x) = x 4 + x 3 + 3x ’ 9 and

b(x) = 2x 3 ’ x 2 + 6x ’ 3 in Q[x].

Solution. By the division algorithm we have (computation below)

a(x) = + b(x) ’ 9 x 2 ’

1 3 27

x

2 4 4 4

and

b(x) = ’ 8 x + ’ 9 x2 ’

4 27

.

9 9 4 4

Hence

gcd(a(x), b(x)) = ’ 9 x 2 ’ 27

.

4 4

+

1 3

x ’8x + 4

2 4 9 9

2x 3 ’ x 2 + 6x ’ 3 x 4 + x 3 +0x 2 +3x’ 9 ’ 9 x2 ’ 2x 3 ’x 2 +6x’3

27

4 4

x 4 ’ 1 x 3 +3x 2 ’ 3 x +6x

2x 3

2 2

x ’3x 2 + 9 x’ 9

33

’x 2 ’3

2 2

x ’ 4 x + 2 x’ 9

33 32 9

’x 2 ’3

2 4

’ 9 x2 ’ 27 0

4 4

UNIQUE FACTORIZATION

One important property of the integers, commonly known as the fundamental

theorem of arithmetic, states that every integer greater than 1 can be written as

188 9 POLYNOMIAL AND EUCLIDEAN RINGS

a ¬nite product of prime numbers, and furthermore, this product is unique up to

the ordering of the primes (see Theorem 13 in Appendix 2). In this section, we

prove a similar result for any euclidean ring.

Let R be a commutative ring. An element u is called an invertible element

(or unit) of R if there exists an element v ∈ R such that uv = 1. The invertible

elements in a ring R are those elements with multiplicative inverses in R. Denote

the set of invertible elements of R by R — . If R is a ¬eld, every nonzero element

is invertible and R — = R ’ {0}.

The invertible elements in the integers are ±1. If F is a ¬eld, the invertible

polynomials in F [x] are the nonzero constant polynomials, that is, the poly-

nomials of degree 0. The set of invertible elements in the gaussian integers is

Z[i]— = {±1, ±i}.

Proposition 9.14. For any commutative ring R, the invertible elements form an

abelian group, (R — , ·), under multiplication.

Proof. Let u1 , u2 ∈ R — and let u1 v1 = u2 v2 = 1. Then (u1 u2 )(v1 v2 ) = 1; thus

u1 u2 ∈ R — . The group axioms follow immediately.

Two elements in a euclidean ring may have many greatest common divisors.

For example, in Q[x], x + 1, 2x + 2, and 1 x + 1 are all greatest common divisors

3 3

of x 2 + 2x + 1 and x 2 ’ 1. However, they can all be obtained from one another

by multiplying by invertible elements.

Lemma 9.15. If a|b and b|a in an integral domain R, then a = ub, where u is

an invertible element.

Proof. Since a|b, b = va for v ∈ R so if a = 0, then b = 0 and a = b. If a =

0, then a = ub for u ∈ R since b|a. Therefore, a = ub = uva; thus a(uv ’ 1) =

0. As a = 0 and R has no zero divisors, uv = 1 and u is invertible.

Lemma 9.16. If g2 is a greatest common divisor of a and b in the euclidean ring

R, then g1 is also a greatest common divisor of a and b if and only if g1 = ug2 ,

where u is invertible.

Proof. If g1 = ug2 where uv = 1, then g2 = vg1 . Hence g2 |g1 and g1 |g2 if

and only if g1 = ug2 . The result now follows from the de¬nition of a greatest

common divisor.

Lemma 9.17. If a and b are elements in a euclidean ring R, then δ(a) = δ(ab)

if and only if b is invertible. Otherwise, δ(a) < δ(ab).

Proof. If b is invertible and bc = 1, then δ(a) δ(ab) δ(abc) = δ(a).

Hence δ(a) = δ(ab).

If b is not invertible, ab does not divide a and a = qab + r, where δ(r) <

δ(ab). Now r = a(1 ’ qb); thus δ(a) δ(r). Therefore, δ(a) < δ(ab).

UNIQUE FACTORIZATION 189

A noninvertible element p in a euclidean ring R is said to be irreducible if,

whenever p = ab, either a or b is invertible in R. The irreducible elements in

the integers are the prime numbers together with their negatives.

Lemma 9.18. Let R be a euclidean ring. If a, b, c ∈ R, gcd(a, b) = 1 and a|bc,

then a|c.

Proof. By Theorem 9.9, we can write 1 = sa + tb, where s, t ∈ R. Therefore

c = sac + tbc, so a|c because a|bc.

Proposition 9.19. If p is irreducible in the euclidean ring R and p|ab, then p|a

or p|b.

Proof. For any a ∈ R, write d = gcd(a, p). Then d|p, say p = d · h. Since p

is irreducible, either d or h is invertible, and so either d = 1 or p. Hence if p

does not divide a, then d = 1, and it follows from Lemma 9.18 that p|b.

Theorem 9.20. Unique Factorization Theorem. Every nonzero element in a

euclidean ring R is either an invertible element or can be written as the prod-

uct of a ¬nite number of irreducibles. In such a product, the irreducibles are

uniquely determined up to the order of the factors and up to multiplication by

invertible elements.

Proof. We proceed by induction on δ(a) for a ∈ R. The least value of δ(a) for

nonzero a is δ(1), because 1 divides any other element. Suppose that δ(a) = δ(1).

Then δ(1 · a) = δ(1) and, by Lemma 9.17, a is invertible.

By the induction hypothesis, suppose that all elements x ∈ R, with δ(x) <

δ(a), are either invertible or can be written as a product of irreducibles. We now

prove this for the element a.

If a is irreducible, there is nothing to prove. If not, we can write a = bc,

where neither b nor c is invertible. By Lemma 9.17, δ(b) < δ(bc) = δ(a) and

δ(c) < δ(bc) = δ(a). By the induction hypothesis, b and c can each be written

as a product of irreducibles, and hence a can also be written as a product of

irreducibles.

To prove the uniqueness, suppose that

a = p1 p2 · · · pn = q1 q2 · · · qm ,

where each pi and qj is irreducible. Now p1 |a and so p1 |q1 q2 · · · qm . By an

extension of Proposition 9.19 to m factors, p1 divides some qi . Rearrange the qi ,

if necessary, so that p1 |q1 . Therefore, q1 = u1 p1 where u1 is invertible, because

p1 and q1 are both irreducible.

Now a = p1 p2 · · · pn = u1 p1 q2 · · · qm ; thus p2 · · · pn = u1 q2 · · · qm . Proceed

inductively to show that pi = ui qi for all i, where each ui is invertible.

190 9 POLYNOMIAL AND EUCLIDEAN RINGS

If m < n, we would obtain the relation pm+1 · · · pn = u1 u2 · · · um , which is

impossible because irreducibles cannot divide an invertible element. If m > n,

we would obtain

1 = u1 u2 · · · un qn+1 · · · qm ,

which is again impossible because an irreducible cannot divide 1. Hence m = n,

and the primes p1 , p2 , . . . , pn are the same as q1 , q2 , . . . , qm up to a rearrange-

ment and up to multiplication by invertible elements.

When the euclidean ring is the integers, the theorem above yields the funda-

mental theorem of arithmetic referred to earlier. The ring of polynomials over

a ¬eld and the gaussian integers also have this unique factorization property

enjoyed by the integers. However, the integral domain

√ √

Z[ ’3] = {a + b ’3 |a, b ∈ Z},

which is a subring of C, does not have the unique factorization property. For

example, √ √

4 = 2 · 2 = (1 + ’3) · (1 ’ ’3),

√ √ √

whereas 2, 1 + ’3, and 1 ’ ’3 are all irreducible. Therefore, Z[ ’3] cannot

be a euclidean ring.

FACTORING REAL AND COMPLEX POLYNOMIALS

The question of whether or not a polynomial is irreducible will be crucial in

Chapter 10 when we extend number ¬elds by adjoining roots of a polynomial.

We therefore investigate different methods of factoring polynomials over various

coef¬cient ¬elds.

A polynomial f (x) of positive degree is said to be reducible over the ¬eld F

if it can be factored into two polynomials of positive degree in F [x]. If it cannot

be so factored, f (x) is called irreducible over F , and f (x) is an irreducible

element of the ring F [x]. It is important to note that reducibility depends on the

¬eld F . The polynomial x 2 + 1 is irreducible over R but reducible over C.

The following basic theorem, ¬rst proved by Gauss in his doctoral thesis in

1799, enables us to determine which polynomials are irreducible in C[x] and in

R[x].

Theorem 9.21. Fundamental Theorem of Algebra. If f (x) is a polynomial in

C[x] of positive degree, then f (x) has a root in C.

A proof of this theorem is given in Nicholson [11] using the fact from analysis

that a cubic real polynomial has a real root.

The following useful theorem shows that the complex roots of real polyno-

mials occur in conjugate pairs.

FACTORING REAL AND COMPLEX POLYNOMIALS 191

Theorem 9.22. (i) If z = a + ib is a complex root of the real polynomial f (x) ∈

R[x], then its conjugate z = a ’ ib is also a root. Thus the real polynomial

(x ’ z)(x ’ z) = x 2 ’ 2ax + (a 2 + b2 ) is a factor of f (x).

√

(ii) If a, b, c ∈ Q and a + b c is an irrational root of the rational polyno-

√

mial f (x) ∈ Q[x], then a ’ b c is also a root, and the rational polynomial

x 2 ’ 2ax + (a 2 ’ b2 c) is a factor of f (x).

Proof. (i) Let g(x) = x 2 ’ 2ax + a 2 + b2 = (x ’ z)(x ’ z). By the division

algorithm in R[x], there exist real polynomials q(x) and r(x) such that

f (x) = q(x)g(x) + r(x) where r(x) = 0 or deg r(x) < 2.

Hence r(x) = r0 + r1 x where r0 , r1 ∈ R. Now z = a + ib is a root of f (x) and

of g(x); therefore, it is also a root of r(x), so 0 = r0 + r1 (a + ib). Equating real

and imaginary parts, we have r0 + r1 a = 0 and r1 b = 0. But then

r(z) = r(a ’ ib) = r0 + r1 (a ’ ib) = r0 + r1 a ’ ir1 b = 0.

Since z is a root of r(x) and g(x), it must be a root of f (x).

If z is complex and not real, then b = 0. In this case r1 = 0 and r0 = 0; thus

g(x)|f (x).

(ii) This can be proved in a similar way to part (i).

Theorem 9.23. (i) The irreducible polynomials in C[x] are the polynomials of

degree 1.

(ii) The irreducible polynomials in R[x] are the polynomials of degree 1

together with the polynomials of degree 2 of the form ax 2 + bx + c, where

b2 < 4ac.

Proof. (i) The polynomials of degree 0 are the invertible elements of C[x].

By the fundamental theorem of algebra, any polynomial of positive degree has a

root in C and hence a linear factor. Therefore, all polynomials of degree greater

than 1 are reducible and those of degree 1 are the irreducibles.

(ii) The polynomials of degree 0 are the invertible elements of R[x]. By part (i)

and the unique factorization theorem, every real polynomial of positive degree

can be factored into linear factors in C[x]. By Theorem 9.22 (i), its nonreal

roots fall into conjugate pairs, whose corresponding factors combine to give a

quadratic factor in R[x] of the form ax 2 + bx + c, where b2 < 4ac. Hence any

real polynomial can be factored into real linear factors and real quadratic factors

of the form above.

Example 9.24. Find the kernel and image of the ring morphism ψ: Q[x] ’ R

√

de¬ned by ψ(f (x)) = f ( 2).

Solution. If p(x) = a0 + a1 x + · · · + an x n ∈ Q[x], then

√ √

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

√

= (a0 + 2a2 + 4a4 + · · ·) + 2 (a1 + 2a3 + 4a5 + · · ·),

192 9 POLYNOMIAL AND EUCLIDEAN RINGS

√ √ √

so ψ(p(x)) ∈ Q( 2) = {a + b 2|a, b ∈ Q}, √ where Q( 2) is the subring of

√

R de¬ned in Example 8.3. Hence Im ψ ⊆ Q( 2), and Im ψ = Q( 2) because

√

ψ(a + bx) = a + b 2. √ √

If p(x) ∈ Kerψ, then p( 2) = 0; therefore, by Theorem 9.22(ii), p(’ 2) =

0, and p(x) contains a factor (x 2 ’ 2). Conversely, if p(x) contains a factor

√

(x 2 ’ 2), then p( 2) = 0 and p(x) ∈ Kerψ. Hence Kerψ = {(x 2 ’ 2)q(x)|q(x)

∈ Q[x]}, that is, the set of all polynomials in Q[x] with (x 2 ’ 2) as a factor.

FACTORING RATIONAL AND INTEGRAL POLYNOMIALS

A rational polynomial can always be reduced to an integer polynomial by mul-

tiplying it by the least common multiple of the denominators of its coef¬cients.

We now give various methods for determining whether an integer polynomial

has rational roots or is irreducible over Q.

Theorem 9.25. Rational Roots Theorem. Let p(x) = a0 + a1 x + · · · + an x n ∈

Z[x]. If r/s is a rational root of p(x) and gcd(r, s) = 1, then:

(i) r|a0 .

(ii) s|an .

Proof. If p(r/s) = 0, then a0 + a1 (r/s) + · · · + an’1 (r/s)n’1 + an (r/s)n =

0, whence a0 s n + a1 rs n’1 + · · · + an’1 r n’1 s + an r n = 0. Therefore, a0 s n =

’r(a1 s n’1 + · · · + an’1 r n’2 s + an r n’1 ); thus r|a0 s n . Since gcd(r, s) = 1, it

follows from Lemma 9.18 that r|a0 . Similarly, s|an .

Example 9.26. Factor p(x) = 2x 3 + 3x 2 ’ 1 in Q[x].

Solution. If p(r/s) = 0, then, by Theorem 9.25, r|(’1) and s|2. Hence r =

±1 and s = ±1 or ±2, and the only possible values of r/s are ±1, ±1/2. Instead

of testing all these values, we sketch the graph of p(x) to ¬nd approximate roots.

Differentiating, we have p (x) = 6x 2 + 6x = 6x(x + 1), so p(x) has turning val-

ues at 0 and ’1.

We see from the graph in Figure 9.2 that ’1 is a double root and that there

is one more positive root. If it is rational, it can only be 1 . Checking this in

2

Table 9.1, we see that 2 is a root; hence p(x) factors as (x + 1)2 (2x ’ 1).

1

√

Example 9.27. Prove that 5 2 is irrational.

TABLE 9.1

’1 0 1/2 1 2

x

’1

0 0 4 27

p(x)

FACTORING RATIONAL AND INTEGRAL POLYNOMIALS 193

p(x)

x

’1 1

’1

Graph of p(x) = 2x 3 + 3x 2 ’ 1.

Figure 9.2.

TABLE 9.2

’2 ’1 1 2

x

x5 ’ 2 ’34 ’3 ’1 30

√

Solution. Observe that 5 2 is a root of x 5 ’ 2. If this polynomial has a rational

root r/s, in its lowest terms, it follows from Theorem 9.25 that r|(’2) and

s|1. Hence the only possible rational roots are ±1, ±2. We see from Table 9.2

that none of these are roots, so all the roots of the polynomial x 5 ’ 2 must be

irrational.

Theorem 9.28. Gauss™ Lemma. Let P (x) = a0 + · · · + an x n ∈ Z[x]. If P (x)

can be factored in Q[x] as P (x) = q(x)r(x) with q(x), r(x) ∈ Q[x], then P (x)

can also be factored in Z[x].

Proof. Express the rational coef¬cients of q(x) in their lowest terms and let

u be the least common multiple of their denominators. Then q(x) = (1/u)Q(x),

where Q(x) ∈ Z[x]. Let s be the greatest common divisor of all the coef¬cients

of Q(x); write q(x) = (s/u)Q(x), where Q(x) ∈ Z[x], and the greatest common

divisor of its coef¬cients is 1. Write r(x) = (t/v)R(x) in a similar way.

s t st

Now P (x) = q(x)r(x) = Q(x) R(x) = Q(x)R(x), so uvP (x) =

u v uv

stQ(x)R(x). To prove the theorem, we show that uv|st by proving that no

prime p in uv can divide all the coef¬cients of Q(x)R(x).

Let Q(x) = b0 + · · · + bk x k and R(x) = c0 + · · · + cl x l . Choose a prime p

and let bi and cj be the ¬rst coef¬cients of Q(x) and R(x), respectively, that p

fails to divide. These exist because gcd(b0 , . . . , bk ) = 1 and gcd(c0 , . . . , cl ) = 1.

The coef¬cient of x i+j in Q(x)R(x) is

bi+j c0 + bi+j ’1 c1 + · · · + bi+1 cj ’1 + bi cj + bi’1 cj +1 + · · · + b0 ci+j .

194 9 POLYNOMIAL AND EUCLIDEAN RINGS

Now p|c0 , p|c1 , . . . , p|cj ’1 , p|bi’1 , p|bi’2 , . . . , p|b0 but p |bi cj so this coef¬-

cient is not divisible by p. Hence the greatest common divisor of the coef¬cients

of Q(x)R(x) is 1; therefore, uv|st and P (x) can be factored in Z[x].

Example 9.29. Factor p(x) = x 4 ’ 3x 2 + 2x + 1 into irreducible factors in Q[x].

Solution. By Theorem 9.25, the only possible rational roots are ±1. However,

these are not roots, so p(x) has no linear factors.

Therefore, if it does factor, it must factor into two quadratics, and by Gauss™

lemma these factors can be chosen to have integral coef¬cients. Suppose that

x 4 ’ 3x 2 + 2x + 1 = (x 2 + ax + b)(x 2 + cx + d)

= x 4 + (a + c)x 3 + (b + d + ac)x 2 + (bc + ad)x + bd.

Thus we have to solve the following system for integer solutions:

a + c = 0, b + d + ac = ’3, bc + ad = 2, and bd = 1.

Therefore, b = d = ±1 and b(a + c) = 2. Hence a + c = ±2, which is a con-

tradiction. The polynomial cannot be factored into two quadratics and therefore

is irreducible in Q[x].

Theorem 9.30. Eisenstein™s Criterion. Let f (x) = a0 + a1 x + · · · + an x n ∈

Z[x]. Suppose that the following conditions all hold for some prime p:

(i) p|a0 , p|a1 , . . . , p|an’1 .

(ii) p |an .

(iii) p 2 |a0 .

Then f (x) is irreducible over Q.

Proof. Suppose that f (x) is reducible. By Gauss™ lemma, it factors as two

polynomials in Z[x]; that is,

f (x) = (b0 + · · · + br x r )(c0 + · · · + cs x s ),

where bi , cj ∈ Z, s > 0, and r + s = n. Comparing coef¬cients, we see that a0 =

b0 c0 . Now p|a0 , but p 2 |a0 , so p must divide b0 or c0 but not both. Without

loss of generality, suppose that p|b0 and p |c0 . Now p cannot divide all of

b0 , b1 , . . . , br , for then p would divide an . Let t be the smallest integer for

which p |bt ; thus 1 t r < n. Then at = bt c0 + bt’1 c1 + · · · + b1 ct’1 + b0 ct

and p|at , p|b0 , p|b1 , . . . , p|bt’1 . Hence p|bt c0 . However, p |bt and p |c0 , so we

have a contradiction, and the theorem is proved.

FACTORING POLYNOMIALS OVER FINITE FIELDS 195

For example, Eisenstein™s criterion can be used to show that x 5 ’ 2,

x 7 + 2x 3 + 12x 2 ’ 2 and 2x 3 + 9x ’ 3 are all irreducible over Q.

Example 9.31. Show that φ(x) = x p’1 + x p’2 + · · · + x + 1 is irreducible over

Q for any prime p. This is called a cyclotomic polynomial and can be written

φ(x) = (x p ’ 1)/(x ’ 1).

Solution. We cannot apply Eisenstein™s criterion to φ(x) as it stands. However,

if we put x = y + 1, we obtain

1

φ(y + 1) = [(y + 1)p ’ 1]

y

p p p

= y p’1 + y p’2 + y p’3 + · · · + y+p

p’1 p’2 2

p!

p

=

where is the binomial coef¬cient. Hence p divides

k!(p ’ k)!

k

p

k!(p ’ k)! . If 1 k p ’ 1, the prime p does not divide k!(p ’ k)!, so

k

p

. Hence φ(y + 1) is irreducible by Eisenstein™s criterion, so

it must divide

k

φ(x) is irreducible.

FACTORING POLYNOMIALS OVER FINITE FIELDS

The roots of a polynomial in Zp [x] can be found by trying all the p possi-

ble values.

Example 9.32. Does x 4 + 4 ∈ Z7 [x] have any roots in Z7 ?

Solution. We see from Table 9.3 that x 4 + 4 is never zero and therefore has

no roots in Z7 .

Proposition 9.33. A polynomial in Z2 [x] has a factor x + 1 if and only if it has

an even number of nonzero coef¬cients.

Proof. Let p(x) = a0 + a1 x + · · · + an x n ∈ Z2 [x]. By the factor theorem,

(x + 1) is a factor of p(x) if and only if p(1) = 0. (Remember that x ’ 1 = x + 1

TABLE 9.3. Values Modulo 7

0 1 2 3 4 5 6

x

x4 0 1 2 4 4 2 1

x4 + 4 4 5 6 1 1 6 5

196 9 POLYNOMIAL AND EUCLIDEAN RINGS

in Z2 [x].) Now p(1) = a0 + a1 + · · · + an , which is zero in Z2 if and only if p(x)

has an even number of nonzero coef¬cients.

Example 9.34. Find all the irreducible polynomials of degree less than or equal

to 4 over Z2 .

Solution. Degree 1 polynomials are irreducible; in Z2 [x] we have x and x + 1.

Let p(x) = a0 + · · · + an x n ∈ Z2 [x]. If p(x) has degree n, then an is nonzero,

so an = 1. The only possible roots are 0 and 1. The element 0 is a root if and

only if a0 = 0, and 1 is a root if and only if p(x) has an even number of nonzero

terms. Hence the following are the polynomials of degrees 2, 3, and 4 in Z2 [x]

with no linear factors:

x2 + x + 1 (degree 2)

x + x + 1, x + x + 1

3 3 2

(degree 3)

x 4 + x + 1, x 4 + x 2 + 1, x 4 + x 3 + 1, x 4 + x 3 + x 2 + x + 1 (degree 4).

If a polynomial of degree 2 or 3 is reducible, it must have a linear factor; hence

the polynomials of degree 2 and 3 above are irreducible. If a polynomial of degree

4 is reducible, it either has a linear factor or is the product of two irreducible

quadratic factors. Now there is only one irreducible quadratic in Z2 [x], and its

square (x 2 + x + 1)2 = x 4 + x 2 + 1 is reducible.

Hence the irreducible polynomials of degree 4 over Z2 are x, x + 1,

x + x + 1, x 3 + x + 1, x 3 + x 2 + 1, x 4 + x + 1, x 4 + x 3 + 1, and

2

x 4 + x 3 + x 2 + x + 1.

For example, the polynomials of degree 4 in Z2 [x] factorize into irreducible

factors as follows.

= x4

x4

x4 + 1 = (x + 1)4

x4 + x = x(x + 1)(x 2 + x + 1)

x4 + x + 1 is irreducible

x4 + x2 = x 2 (x + 1)2

x4 + x2 + 1 = (x 2 + x + 1)2

x4 + x2 + x = x(x 3 + x + 1)

x4 + x2 + x + 1 = (x + 1)(x 3 + x 2 + 1)

x4 + x3 = x 3 (x + 1)

x4 + x3 + 1 is irreducible

x4 + x3 + x = x(x 3 + x 2 + 1)

x4 + x3 + x + 1 = (x + 1)2 (x 2 + x + 1)

x4 + x3 + x2 = x 2 (x 2 + x + 1)

x4 + x3 + x2 + 1 = (x + 1)(x 3 + x + 1)

x4 + x3 + x2 + x = x(x + 1)3

x4 + x3 + x2 + x + 1 is irreducible

LINEAR CONGRUENCES AND THE CHINESE REMAINDER THEOREM 197

LINEAR CONGRUENCES AND THE CHINESE

REMAINDER THEOREM

The euclidean algorithm for integers can be used to solve linear congruences. We

¬rst ¬nd the conditions for a single congruence to have a solution and then show

how to ¬nd all its solutions, if they exist. We then present the Chinese remainder

theorem, which gives conditions under which many simultaneous congruences,

with coprime moduli, have solutions. These solutions can again be found by

using the euclidean algorithm.

First let us consider a linear congruence of the form

ax ≡ b mod n.

This has a solution if and only if the equation

ax + ny = b

has integer solutions for x and y. The congruence is also equivalent to the

equation [a][x] = [b] in Zn .

Theorem 9.35. The equation ax + ny = b has solutions for x, y ∈ Z if and only

if gcd(a, n)|b.

Proof. Write d = gcd(a, n). If ax + ny = b has a solution, then d|b because

d|a and d|n. Conversely, let d|b, say b = k · d. By Theorem 9.9, there exist

s, t ∈ Z such that as + nt = d. Hence ask + ntk = k · d and x = sk, y = tk is

a solution to ax + ny = b.

The euclidean algorithm gives a practical way to ¬nd the integers s and t in

Theorem 9.35. These can then be used to ¬nd one solution to the equation.

Theorem 9.36. The congruence ax ≡ b mod n has a solution if and only if d|b,

where d = gcd(a, n). Moreover, if this congruence does have at least one solu-

tion, the number of noncongruent solutions modulo n is d; that is, if [a][x] = [b]

has a solution in Zn , then it has d different solutions in Zn .

Proof. The condition for the existence of a solution follows immediately from

Theorem 9.35. Now suppose that x0 is a solution, so that ax0 ≡ b mod n. Let

d = gcd(a, n) and a = da , n = dn . Then gcd(a , n ) = 1, so the following state-

ments are all equivalent.

x is a solution to the congruence ax ≡ b mod n.

(i)

x is a solution to the congruence a(x ’ x0 ) ≡ 0 mod n.

(ii)

n|a(x ’ x0 ).

(iii)

n |a (x ’ x0 ).

(iv)

198 9 POLYNOMIAL AND EUCLIDEAN RINGS

(v) n |(x ’ x0 ).

(vi) x = x0 + kn for some k ∈ Z.

Now x0 , x0 + n , x0 + 2n , . . . , x0 + (d ’ 1)n form a complete set of noncon-

gruent solutions modulo n, and there are d such solutions.

Example 9.37. Find the inverse of [49] in the ¬eld Z53 .

Solution. Let [x] = [49]’1 in Z53 . Then [49] · [x] = [1]; that is, 49x ≡ 1

mod 53. We can solve this congruence by solving the equation 49x ’ 1 = 53y,

where y ∈ Z. By using the euclidean algorithm we have

53 = 1 · 49 + 4 and 49 = 12 · 4 + 1.

Hence gcd(49, 53) = 1 = 49 ’ 12 · 4 = 49 ’ 12(53 ’ 49) = 13 · 49 ’ 12 · 53.

Therefore, 13 · 49 ≡ 1 mod 53 and [49]’1 = [13] in Z53 .

Theorem 9.38. Chinese Remainder Theorem. Let m = m1 m2 · · · mr , where

gcd(mi , mj ) = 1 if i = j . Then the system of simultaneous congruences

x ≡ a1 mod m1 , x ≡ a2 mod m2 , x ≡ ar mod mr

...,

always has an integral solution. Moreover, if b is one solution, the complete

solution is the set of integers satisfying x ≡ b mod m.

Proof. This result follows from the ring isomorphism

f : Zm ’ Zm1 — Zm2 — · · · — Zmr

of Theorem 8.20 de¬ned by f ([x]m ) = ([x]m1 , [x]m2 , . . . , [x]mr ). The integer

x is a solution of the simultaneous congruences if and only if f ([x]m ) =

([a1 ]m1 , [a2 ]m2 , . . . , [ar ]mr ). Therefore, there is always a solution, and the solution

set consists of exactly one congruence class modulo m.

One method of ¬nding the solution to a set of simultaneous congruences is to

use the euclidean algorithm repeatedly.

x ≡ 36 mod 41

Example 9.39. Solve the simultaneous congruences .

x ≡ 5 mod 17

Proof. Any solution to the ¬rst congruence is of the form x = 36 + 41t where

t ∈ Z. Substituting this into the second congruence, we obtain

36 + 41t ≡ 5 mod 17 41t ≡ ’31 mod 17.

that is,

LINEAR CONGRUENCES AND THE CHINESE REMAINDER THEOREM 199

Reducing modulo 17, we have 7t ≡ 3 mod 17. Solving this by the euclidean

algorithm, we have

17 = 2 · 7 + 3 and 7 = 2 · 3 + 1.

Therefore, 1 = 7 ’ 2(17 ’ 2 · 7) = 7 · 5 ’ 17 · 2 and 7 · 5 ≡ 1 mod 17. Hence

7 · 15 ≡ 3 mod 17, so t ≡ 15 mod 17 is the solution to 7t ≡ 3 mod 17.

We have shown that if x = 36 + 41t is a solution to both congruences, then

t = 15 + 17u, where u ∈ Z. That is,

x = 36 + 41t = 36 + 41(15 + 17u) = 651 + 697u

or x ≡ 651 mod 697 is the complete solution.

Example 9.40. Find the smallest positive integer that has remainders 4, 3, and

1 when divided by 5, 7, and 9, respectively.

Solution. We have to solve the three simultaneous congruences

x ≡ 4 mod 5, x ≡ 3 mod 7, and x ≡ 1 mod 9.

The ¬rst congruence implies that x = 4 + 5t, where t ∈ Z. Substituting into the

second congruence, we have

4 + 5t ≡ 3 mod 7.

Hence 5t ≡ ’1 mod 7. Now 5’1 = 3 in Z7 , so t ≡ 3 · (’1) ≡ 4 mod 7. There-

fore, t = 4 + 7u, where u ∈ Z, and any integer satisfying the ¬rst two congru-

ences is of the form

x = 4 + 5t = 4 + 5(4 + 7u) = 24 + 35u.

Substituting this into the third congruence, we have 24 + 35u ≡ 1 mod 9 and

’u ≡ ’23 mod 9. Thus u ≡ 5 mod 9 and u = 5 + 9v for some v ∈ Z.

Hence any solution of the three congruences is of the form

x = 24 + 35u = 24 + 35(5 + 9v) = 199 + 315v.

The smallest positive solution is x = 199.

The Chinese remainder theorem was known to ancient Chinese astronomers,

who used it to date events from observations of various periodic astronomical

phenomena. It is used in this computer age as a tool for ¬nding integer solutions

to integer equations and for speeding up arithmetic operations in a computer.

Addition of two numbers in conventional representation has to be carried out

sequentially on the digits in each position; the digits in the ith position have to

200 9 POLYNOMIAL AND EUCLIDEAN RINGS

be added before the digit to be carried over to the (i + 1)st position is known.

One method of speeding up addition on a computer is to perform addition using

residue representation, since this avoids delays due to carry digits.

Let m = m1 m2 · · · mr , where the integers mi are coprime in pairs. The residue

representation or modular representation of any number x in Zm is the r-tuple

(a1 , a2 , . . . , ar ), where x ≡ ai mod mi .

For example, every integer from 0 to 29 can be uniquely represented by its

residues modulo 2, 3, and 5 in Table 9.4.

This residue representation corresponds exactly to the isomorphism

Z30 ’ Z2 — Z3 — Z5 .

Since this is a ring isomorphism, addition and multiplication are performed simply

by adding and multiplying each residue separately.

For example, to add 4 and 7 using residue representation, we have

(0, 1, 4) + (1, 1, 2) = (0 + 1, 1 + 1, 4 + 2) = (1, 2, 1).

Similarly, multiplying 4 and 7, we have

(0, 1, 4) · (1, 1, 2) = (0 · 1, 1 · 1, 4 · 2) = (0, 1, 3).

Fast adders can be designed using residue representation, because all the

residues can be added simultaneously. Numbers can be converted easily into

residue form; however, the reverse procedure of ¬nding a number with a given

residue representation requires the Chinese remainder theorem. See Knuth [19,

Sec. 4.3.2] for further discussion of the use of residue representations in com-

puters.

TABLE 9.4. Residue Representation of the Integers

from 0 to 29

Residues Residues Residues

Modulo: Modulo: Modulo:

2 3 5 2 3 5 2 3 5

x x x

0 0 0 0 10 0 1 0 20 0 2 0

1 1 1 1 11 1 2 1 21 1 0 1

2 0 2 2 12 0 0 2 22 0 1 2

3 1 0 3 13 1 1 3 23 1 2 3

4 0 1 4 14 0 2 4 24 0 0 4

5 1 2 0 15 1 0 0 25 1 1 0

6 0 0 1 16 0 1 1 26 0 2 1

7 1 1 2 17 1 2 2 27 1 0 2

8 0 2 3 18 0 0 3 28 0 1 3

9 1 0 4 19 1 1 4 29 1 2 4

EXERCISES 201

EXERCISES

For Exercises 9.1 to 9.6 calculate the quotients and remainders.

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

9.1. Divide by

x 6 + x 4 ’ 4x 3 + 5x x 3 + 2x 2 + 1 in R[x].

9.2. Divide by

x7 + x6 + x4 + x + 1 x 3 + x + 1 in Z2 [x].

9.3. Divide by

2x 5 + x 4 + 2x 3 + x 2 + 2 x 3 + 2x + 2 in Z3 [x].

9.4. Divide by

17 + 11i 3 + 4i in Z[i].

9.5. Divide by

20 + 8i 7 ’ 2i in Z[i].

9.6. Divide by

For Exercises 9.7 to 9.13, ¬nd the greatest common divisors of the elements a, b

in the given euclidean ring, and ¬nd elements s, t in the ring so that as + bt =

gcd(a, b).

= 33, b = 42 in Z.

9.7. a

= 2891, b = 1589 in Z.

9.8. a

= 2x 3 ’ 4x 2 ’ 8x + 1, b = 2x 3 ’ 5x 2 ’ 5x + 2 ∈ Q[x].

9.9. a

= x 6 ’ x 3 ’ 16x 2 + 12x ’ 2, b = x 5 ’ 2x 2 ’ 16x + 8 ∈ Q[x].

9.10. a

= x 4 + x + 1, b = x 3 + x 2 + x ∈ Z3 [x].

9.11. a

= x 4 + 2, b = x 3 + 3 ∈ Z5 [x].

9.12. a

= 4 ’ i, b = 1 + i ∈ Z[i].

9.13. a

For Exercises 9.14 to 9.17, ¬nd one solution to each equation with x, y ∈ Z.

9.14. 15x + 36y = 3. 9.15. 24x + 29y = 1.

9.16. 24x + 29y = 6. 9.17. 11x + 31y = 1.

For Exercises 9.18 to 9.21, ¬nd the inverse to the element in the given ¬eld.

9.18. [4] in Z7 . 9.19. [24] in Z29 .

9.20. [35] in Z101 . 9.21. [11] in Z31 .

Find all integral solutions to the equations in Exercises 9.22 to 9.24.

9.22. 27x + 15y = 13. 9.23. 12x + 20y = 14.

9.24. 28x + 20y = 16.

Factor the polynomials in Exercises 9.25 to 9.36 into irreducible factors in the

given ring.

x 5 ’ 1 in Q[x]. 9.26. x 5 + 1 in Z2 [x].

9.25.

x 4 + 1 in Z5 [x]. 9.28. 2x 3 + x 2 + 4x + 2 in Q[x].

9.27.

x 4 ’ 9x + 3 in Q[x]. 9.30. 2x 3 + x 2 + 4x + 2 in C[x].

9.29.

x 3 ’ 4x + 1 in Q[x]. 9.32. x 4 + 3x 3 + 9x ’ 9 in Q[x].

9.31.

x 8 ’ 16 in C[x]. 9.34. x 8 ’ 16 ∈ R[x].

9.33.

x 8 ’ 16 in Q[x]. 9.36. x 8 ’ 16 ∈ Z17 [x].

9.35.

Find all irreducible polynomials of degree 5 over Z2 .

9.37.

202 9 POLYNOMIAL AND EUCLIDEAN RINGS

9.38. Find an irreducible polynomial of degree 2 over Z5 .

9.39. Find an irreducible polynomial of degree 3 over Z7 .

9.40. Find the kernel and image of the ring morphism ψ: R[x] ’ C de¬ned by

√

ψ(p(x)) = p(i), where i = ’1.

9.41. Find the kernel and image of the ring morphism ψ: R[x] ’ C de¬ned by

√

ψ(p(x)) = p(1 + 3i).

In Exercises 9.42 to 9.47, are the polynomials irreducible in the given ring?

Give reasons.

x 3 + x 2 + x + 1 in Q[x].

9.42.

3x 8 ’ 4x 6 + 8x 5 ’ 10x + 6 in Q[x].

9.43.

x 4 + x 2 ’ 6 in Q[x]. 9.45. 4x 3 + 3x 2 + x + 1 in Z5 [x].

9.44.

x 5 + 15 in Q[x]. 9.47. x 4 ’ 2x 3 + x 2 + 1 in R[x].

9.46.

Is Z[x] a euclidean ring when δ(f (x)) = degf (x) for any nonzero poly-

9.48.

nomial? Is Z[x] a euclidean ring with any other de¬nition of δ(f (x))?

9.49. Can you de¬ne a division algorithm in R[x, y]? How would you divide

x 3 + 3xy + y + 4 by xy + y 3 + 2?

9.50. Let Lp be the set of all linear functions f : Zp ’ Zp of the form f (x) =

ax + b, where a = 0 in Zp . Show that (Lp , Ž ) is a group of order p(p ’ 1)

under composition.

9.51. If p is a prime, prove that (x ’ a)|(x p’1 ’ 1) in Zp [x] for all nonzero a

in Zp . Hence prove that

x p’1 ’ 1 = (x ’ 1)(x ’ 2) · · · (x ’ p + 1) in Zp [x].

9.52. (Wilson™s theorem) Prove that (n ’ 1)! ≡ ’1 mod n if and only if n

is prime.

√√

9.53. Prove that 2/ 3 5 is irrational.

√ √

9.54. Find a polynomial in Q[x] with 2 + 3 as a root. Then prove that

√ √

2 + 3 is irrational.

9.55. Is 5 irreducible in Z[i]?

√ √

9.56. Show that Z[ ’5] = {a + b ’5|a, b ∈ Z} does not have the unique fac-

torization property.

9.57. Prove that a gaussian integer is irreducible if and only if it is an invertible

element times one of the following gaussian integers:

(1) any prime p in Z with p ≡ 3 mod 4.

(2) 1 + i.

(3) a + bi, where a is positive and even, and a 2 + b2 = p, for some prime

p in Z such that p ≡ 1 mod 4.

9.58. If r/s is a rational root, in its lowest terms, of a polynomial p(x) with

integral coef¬cients, show that p(x) = (sx ’ r)g(x) for some polynomial

g(x) with integral coef¬cients.

EXERCISES 203

9.59. Prove that r/s, in its lowest terms, cannot be a root of the integral poly-

nomial p(x) unless (s ’ r)|p(1). This can be used to shorten the list of

possible rational roots of an integral polynomial.

9.60. Let m = m1 m2 · · · mr and Mi = m/mi . If gcd(mi , mj ) = 1 for i = j , each

of the congruences Mi y ≡ 1 mod mi has a solution y ≡ bi mod mi . Prove

that the solution to the simultaneous congruences

x ≡ a1 mod m1 , x ≡ a2 mod m2 , x ≡ ar mod mr

...,

r

is x ≡ Mi bi ai mod m.

i=1

For Exercises 9.61 to 9.64, solve the simultaneous congruences.

≡5 9.62. x ≡ 41 mod 65

9.61. x mod 7

≡4 x ≡ 35 mod 72.

mod 6.

x

≡0 9.64. x ≡ 9 mod 12

9.63. x mod 2

≡1 x ≡ 3 mod 13

mod 3

x

≡2 x ≡ 6 mod 25.

mod 5.

x

®

320 461 5264 72

702 1008 ’967 ’44

9.65. Prove that det is nonzero.

° ’91 2333 127 »

46

164 ’216 1862 469

9.66. Solve the following simultaneous equations:

26x ’ 141y = ’697

55x ’ 112y = 202

(a) in Z2 , (b) in Z3 , and (c) in Z5 . Then use the Chinese remainder theorem

to solve them in Z assuming they have a pair of integral solutions between

0 and 29. ®

676 117 522

9.67. The value of det ° 375 65 290 » is positive and less than 100.

825 143 639

Find its value without using a calculator. (If you get tired of doing arith-

metic, calculate its value mod 10 and mod 11 and then use the Chinese

remainder theorem.)

9.68. The polynomial x 3 + 5x ∈ Z6 [x] has six roots. Does this contradict Theo-

rem 9.6?

9.69. If R is an integral domain and R[x] is euclidean, show that R must be

a ¬eld.

9.70. Assume that R is a euclidean domain in which δ(a + b) max{δ(a), δ(b)}

whenever a, b, and a + b are all nonzero. Show that the quotient and

remainder in the division algorithm are uniquely determined.

10

QUOTIENT RINGS

In this chapter we de¬ne a quotient ring in a way similar to our de¬nition of

a quotient group. The analogue of a normal subgroup is called an ideal, and

a quotient ring consists of the set of cosets of the ring by one of its ideals.

As in groups, we have a morphism theorem connecting morphisms, ideals, and

quotient rings. We discover under what conditions quotient rings are ¬elds. This

will enable us to ful¬ll our long-range goal of extending the number systems by

de¬ning new ¬elds using quotient rings of some familiar rings.

IDEALS AND QUOTIENT RINGS

If (R, +, ·) is any ring and (S, +) is any subgroup of the abelian group (R, +),

then the quotient group (R/S, +) has already been de¬ned. However, R/S does

not have a ring structure induced on it by R unless S is a special kind of subgroup

called an ideal.

A nonempty subset I of a ring R is called an ideal of R if the following

conditions are satis¬ed for all x, y ∈ I and r ∈ R:

(i) x ’ y ∈ I .

(ii) x · r and r · x ∈ I .

Condition (i) implies that (I, +) is a subgroup of (R, +). In any ring R, R itself

is an ideal, and {0} is an ideal.

Proposition 10.1. Let a be an element of a commutative ring R. The set

{ar|r ∈ R} of all multiples of a is an ideal of R called the principal ideal

generated by a. This ideal is denoted by (a).

Proof. Let ar, as ∈ (a) and t ∈ R. Then ar ’ as = a(r ’ s) ∈ (a) and (ar)t =

a(rt) ∈ (a). Hence (a) is an ideal of R.

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.

204

IDEALS AND QUOTIENT RINGS 205

For example, (n) = nZ, consisting of all integer multiples of n, is the principal

ideal generated by n in Z.

The set of all polynomials in Q[x] that contain x 2 ’ 2 as a factor is the

principal ideal (x 2 ’ 2) = {(x 2 ’ 2) · p(x)|p(x) ∈ Q[x]} generated by x 2 ’ 2 in

Q[x]. The set of all real polynomials that have zero constant term is the principal

ideal (x) = {x · p(x)|p(x) ∈ R[x]} generated by x in R[x]. It is also the set of

real polynomials with 0 as a root.

The set of all real polynomials, in two variables x and y, that have a zero

constant term is an ideal of R[x, y]. However, this ideal is not principal (see

Exercise 10.30).

However, every ideal is principal in many commutative rings; these are called

principal ideal rings.

Theorem 10.2. A euclidean ring is a principal ideal ring.

Proof. Let I be any ideal of the euclidean ring R. If I = {0}, then I = (0),

the principal ideal generated by 0. Otherwise, I contains nonzero elements. Let

b be a nonzero element of I for which δ(b) is minimal. If a is any other element

in I , then, by the division algorithm, there exist q, r ∈ R such that

a =q ·b+r where r = 0 or δ(r) < δ(b).

Now r = a ’ q · b ∈ I . Since b is a nonzero element of I for which δ(b) is

minimal, it follows that r must be zero and a = q · b. Therefore, a ∈ (b) and

I ⊆ (b).

Conversely, any element of (b) is of the form q · b for some q ∈ R, so q · b ∈

I . Therefore, I ⊇ (b), which proves that I = (b). Hence R is a principal ideal

ring.

Corollary 10.3. Z is a principal ideal ring, so is F [x], if F is a ¬eld.

Proof. This follows because Z and F [x] are euclidean rings.

Proposition 10.4. Let I be ideal of the ring R. If I contains the identity 1, then

I is the entire ring R.

Proof. Let 1 ∈ I and r ∈ R. Then r = r · 1 ∈ I , so I = R.

Let I be any ideal in a ring R. Then (I, +) is a normal subgroup of (R, +),

and we denote the coset of I in R that contains r by I + r. Hence

I + r = {i + r ∈ R|i ∈ I }.

The cosets of I in R are the equivalence classes under the congruence relation

modulo I . We have

r1 ≡ r2 modI r1 ’ r2 ∈ I.

if and only if

206 10 QUOTIENT RINGS

By Theorem 4.18, the set of cosets R/I = {I + r|r ∈ R} is an abelian group

under the operation de¬ned by

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

In fact, we get a ring structure in R/I .

Theorem 10.5. Let I be an ideal in the ring R. Then the set of cosets forms a

ring (R/I, +, ·) under the operations de¬ned by

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

and

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

This ring (R/I, +, ·) is called the quotient ring (or factor ring) of R by I .

Proof. As mentioned above, (R/I, +) is an abelian group; thus we only have

to verify the axioms related to multiplication.

We ¬rst show that multiplication is well de¬ned on cosets. Let I + r1 = I + r1

and I + r2 = I + r2 , so that r1 ’ r1 = i1 ∈ I and r2 ’ r2 = i2 ∈ I . Then

r1 r2 = (i1 + r1 )(i2 + r2 ) = i1 i2 + r1 i2 + i1 r2 + r1 r2 .

Now, since I is an ideal, i1 i2 , r1 i2 and i1 r2 ∈ I . Hence r1 r2 ’ r1 r2 ∈ I , so

I + r1 r2 = I + r1 r2 , which shows that multiplication is well de¬ned on R/I .

Multiplication is associative and distributive over addition. If r1 , r2 , r3 ∈

R, then

(I + r1 ){(I + r2 )(I + r3 )} = (I + r1 )(I + r2 r3 ) = I + r1 (r2 r3 ) = I + (r1 r2 )r3

= (I + r1 r2 )(I + r3 ) = {(I + r1 )(I + r2 )}(I + r3 ).

Also,

(I + r1 ){(I + r2 ) + (I + r3 )} = (I + r1 ){I + (r2 + r3 )} = I + r1 (r2 + r3 )

= I + (r1 r2 + r1 r3 ) = (I + r1 r2 ) + (I + r1 r3 )

= {(I + r1 )(I + r2 )} + {(I + r1 )(I + r3 )}.

The other distributive law can be proved similarly. The multiplicative identity is

I + 1. Hence (R/I, +, ·) is a ring.

COMPUTATIONS IN QUOTIENT RINGS 207