that r = c ’ qd is also an element of I, and by the minimality of the degree

of d, we must have r = 0. Thus, d | c.

We next show that dF [X] ⊆ I. This follows immediately from the fact

that d ∈ I and the closure properties of ideals.

That proves the existence part of the theorem. As for uniqueness, note

that if dF [X] = d F [X], we have d | d and d | d, from which it follows that d

and d are associate, and so if d and d are both either monic or zero, they

must be equal. 2

For a, b ∈ F [X], we call d ∈ F [X] a common divisor of a and b if d | a

and d | b; moreover, we call such a d a greatest common divisor of a and

b if d is monic or zero, and all other common divisors of a and b divide d.

Analogous to Theorem 1.6, we have:

Theorem 17.8. For any a, b ∈ F [X], there exists a unique greatest common

divisor d of a and b, and moreover, aF [X] + bF [X] = dF [X].

Proof. We apply the previous theorem to the ideal I := aF [X] + bF [X]. Let

d ∈ F [X] with I = dF [X], as in that theorem. Note that a, b, d ∈ I and d is

monic or zero.

It is clear that d is a common divisor of a and b. Moreover, there exist

s, t ∈ F [X] such that as + bt = d. If d | a and d | b, then clearly d | (as + bt),

and hence d | d.

Finally, for uniqueness, if d is a greatest common divisor of a and b, then

d | d and d | d, and hence d is associate to d, and the requirement that

d is monic or zero implies that d = d. 2

For a, b ∈ F [X], we denote by gcd(a, b) the greatest common divisor of

a and b. Note that as we have de¬ned it, lc(a) gcd(a, 0) = a. Also note

that when at least one of a or b are non-zero, gcd(a, b) is the unique monic

polynomial of maximal degree that divides both a and b.

An immediate consequence of Theorem 17.8 is that for all a, b ∈ F [X],

there exist s, t ∈ F [X] such that as + bt = gcd(a, b), and that when at

least one of a or b are non-zero, gcd(a, b) is the unique monic polynomial of

minimal degree that can be expressed as as + bt for some s, t ∈ F [X].

We say that a, b ∈ F [X] are relatively prime if gcd(a, b) = 1, which is

the same as saying that the only common divisors of a and b are units. It is

immediate from Theorem 17.8 that a and b are relatively prime if and only

if aF [X] + bF [X] = F [X], which holds if and only if there exist s, t ∈ F [X] such

that as + bt = 1.

17.3 Unique factorization of polynomials 369

Analogous to Theorem 1.7, we have:

Theorem 17.9. For a, b, c ∈ F [X] such that c | ab and gcd(a, c) = 1, we

have c | b.

Proof. Suppose that c | ab and gcd(a, c) = 1. Then since gcd(a, c) = 1, by

Theorem 17.8 we have as + ct = 1 for some s, t ∈ F [X]. Multiplying this

equation by b, we obtain abs + cbt = b. Since c divides ab by hypothesis, it

follows that c | (abs + cbt), and hence c | b. 2

Analogous to Theorem 1.8, we have:

Theorem 17.10. Let p ∈ F [X] be irreducible, and let a, b ∈ F [X]. Then

p | ab implies that p | a or p | b.

Proof. Assume that p | ab. The only divisors of p are associate to 1 or p.

Thus, gcd(p, a) is either 1 or the monic associate of p. If p | a, we are done;

otherwise, if p a, we must have gcd(p, a) = 1, and by the previous theorem,

we conclude that p | b. 2

Now to prove the uniqueness part of Theorem 17.5. Suppose we have

p1 · · · p r = p 1 · · · ps ,

where p1 , . . . , pr and p1 , . . . , ps are monic irreducible polynomials (duplicates

are allowed among the pi and among the pj ). If r = 0, we must have s = 0

and we are done. Otherwise, as p1 divides the right-hand side, by inductively

applying Theorem 17.10, one sees that p1 is equal to pj for some j. We can

cancel these terms and proceed inductively (on r).

That completes the proof of Theorem 17.5.

Analogous to Theorem 1.9, we have:

Theorem 17.11. There are in¬nitely many monic irreducible polynomials

in F [X].

If F is in¬nite, then this theorem is true simply because there are in¬nitely

many monic, linear polynomials; in any case, one can also just prove this

theorem by mimicking the proof of Theorem 1.9 (verify).

For a monic irreducible polynomial p, we may de¬ne the function νp , map-

ping non-zero polynomials to non-negative integers, as follows: for polyno-

mial n = 0, if n = pe m, where p m, then νp (n) := e. We may then write

the factorization of n into irreducibles as

pνp (n) ,

n=u

p

370 More rings

where the product is over all monic irreducible polynomials p, with all but

¬nitely many of the terms in the product equal to 1.

Just as for integers, we may extend the domain of de¬nition of νp to

include 0, de¬ning νp (0) := ∞. For all polynomials a, b, we have

νp (a · b) = νp (a) + νp (b) for all p. (17.1)

From this, it follows that for all polynomials a, b, we have

b|a νp (b) ¤ νp (a) for all p,

if and only if (17.2)

and

νp (gcd(a, b)) = min(νp (a), νp (b)) for all p. (17.3)

For a, b ∈ F [X] a common multiple of a and b is a polynomial m such

that a | m and b | m; moreover, such an m is the least common multiple

of a and b if m is monic or zero, and m divides all common multiples of a

and b. In light of Theorem 17.5, it is clear that the least common multiple

exists and is unique, and we denote the least common multiple of a and

b by lcm(a, b). Note that as we have de¬ned it, lcm(a, 0) = 0, and that

when both a and b are non-zero, lcm(a, b) is the unique monic polynomial

of minimal degree that is divisible by both a and b. Also, for all a, b ∈ F [X],

we have

νp (lcm(a, b)) = max(νp (a), νp (b)) for all p, (17.4)

and

lc(ab) · gcd(a, b) · lcm(a, b) = ab. (17.5)

Just as in §1.3, the notions of greatest common divisor and least common

multiple generalize naturally from two to any number of polynomials. We

also say that polynomials a1 , . . . , ak ∈ F [X] are pairwise relatively prime

if gcd(ai , aj ) = 1 for all i, j with i = j.

Also just as in §1.3, any rational function a/b ∈ F (X) can be expressed

as a fraction a /b in lowest terms, that is, a/b = a /b and gcd(a , b ) = 1,

and this representation is unique up to multiplication by units.

Many of the exercises in Chapter 1 carry over naturally to polynomials ”

the reader is encouraged to look over all of the exercises in that chapter,

determining which have natural polynomial analogs, and work some of these

out.

Exercise 17.7. Show that for f ∈ F [X] of degree 2 or 3, we have f irre-

ducible if and only if f has no roots in F .

17.4 Polynomial congruences 371

17.4 Polynomial congruences

Throughout this section, F denotes a ¬eld.

Specializing the congruence notation introduced in §9.3 for arbitrary rings

to the ring F [X], for polynomials a, b, n ∈ F [X], we write a ≡ b (mod n) when

n | (a’b). Because of the division with remainder property for polynomials,

we have the analog of Theorem 2.1:

Theorem 17.12. Let n ∈ F [X] be a non-zero polynomial. For every a ∈

F [X], there exists a unique b ∈ F [X] such that a ≡ b (mod n) and deg(b) < n,

namely, b := a mod n.

For a non-zero n ∈ F [X], and a ∈ F [X], we say that a ∈ F [X] is a multi-

plicative inverse of a modulo n if aa ≡ 1 (mod n).

All of the results we proved in §2.2 for solving linear congruences over the

integers carry over almost identically to polynomials. As such, we do not

give proofs of any of the results here. The reader may simply check that the

proofs of the corresponding results translate almost directly.

Theorem 17.13. Let a, n ∈ F [X] with n = 0. Then a has a multiplicative

inverse modulo n if and only if a and n are relatively prime.

Theorem 17.14. Let a, n, z, z ∈ F [X] with n = 0. If a is relatively prime

to n, then az ≡ az (mod n) if and only if z ≡ z (mod n). More generally,

if d := gcd(a, n), then az ≡ az (mod n) if and only if z ≡ z (mod n/d).

Theorem 17.15. Let a, b, n ∈ F [X] with n = 0. If a is relatively prime

to n, then the congruence az ≡ b (mod n) has a solution z; moreover, any

polynomial z is a solution if and only if z ≡ z (mod n).

As for integers, this theorem allows us to generalize the “ mod ” operation

as follows: if n ∈ F [X] is a non-zero polynomial, and s ∈ F (X) is a rational

function of the form b/a, where a, b ∈ F [X], a = 0, and gcd(a, n) = 1, then