<<

. 8
( 13)



>>

in a group.
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

(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

<<

. 8
( 13)



>>