<< стр. 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
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
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  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-
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  in the п¬Ѓeld Z53 .

Solution. Let [x] = в€’1 in Z53 . Then  В· [x] = ; 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 в€’1 =  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.  in Z7 . 9.19.  in Z29 .
9.20.  in Z101 . 9.21.  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)СОДЕРЖАНИЕ >>