because F [X] is a UFD, f divides either g or h in F [X]. But Theorem 17.40

implies that f divides either g or h in D[X]. 2

Theorem 17.36 now follows immediately from Theorems 17.37, 17.38, and

17.42, together with Theorem 17.27.

In the proof of Theorem 17.36, there is a clear connection between factor-

ization in D[X] and F [X], where F is the ¬eld of fractions of D. We should

perhaps make this connection more explicit. Suppose f ∈ D[X] factors into

irreducibles in D[X] as

f = ca1 · · · car hb1 · · · hbs .

r1 s

1

where the ci are non-associate, irreducible constants, and the hi are non-

17.8 Unique factorization domains (—) 395

associate, irreducible, non-constant polynomials (and in particular, primi-

tive). By Theorem 17.41, the hi are irreducible in F [X]. Moreover, by The-

orem 17.40, the hi are non-associate in F [X]. Therefore, in F [X], f factors

as

f = chb1 · · · hbs ,

s

1

where c := ca1 · · · car is a unit in F , and the hi are non-associate irreducible

r

1

polynomials in F [X].

Example 17.15. It is important to keep in mind the distinction between

factorization in D[X] and F [X]. Consider the polynomial 2X2 ’ 2 ∈ Z[X].

Over Z[X], this polynomial factors as 2(X ’ 1)(X + 1), where each of these

three factors are irreducible in Z[X]. Over Q[X], this polynomial has two

irreducible factors, namely, X ’ 1 and X + 1. 2

The following theorem provides a useful criterion for establishing that a

polynomial is irreducible.

Theorem 17.43 (Eisenstein™s criterion). Let D be a UFD and F its

¬eld of fractions. Let f = fn Xn + fn’1 Xn’1 + · · · + f0 ∈ D[X]. If there exists

an irreducible p ∈ D such that

p fn , p | fn’1 , · · · , p | f0 , p2 f0 ,

then f is irreducible over F .

Proof. Let f be as above, and suppose it were not irreducible in F [X]. Then

by Theorem 17.41, we could write f = gh, where g, h ∈ D[X], both of degree

strictly less than that of f . Let us write

g = gr Xr + · · · + g0 and h = hs Xs + · · · + h0 ,

where gr = 0 and hs = 0, so that 0 < r < n and 0 < s < n. Now,

since fn = gr hs , and p fn , it follows that p gr and p hs . Further, since

f0 = g0 h0 , and p | f0 but p2 f0 , it follows that p divides one of g0 or h0 , but

not both ” for concreteness, let us assume that p | g0 but p h0 . Also, let t

be the smallest positive integer such that p gt ”note that 0 < t ¤ r < n.

Now consider the natural map that sends c ∈ D to c ∈ D/pD, which we

¯

can extend coe¬cient-wise to the map that sends a ∈ D[X] to a ∈ (D/pD)[X].

¯

Because D is a UFD and p is irreducible, both D/pD and (D/pD)[X] are

integral domains. Since f = gh, we have

¯ ¯ ¯¯ ¯ ¯

fn Xn = f = g h = (¯r Xr + · · · + gt Xt )(hs Xs + · · · + h0 ).

g ¯ (17.12)

396 More rings

But notice that when we multiply out the two polynomials on the right-

¯¯

hand side of (17.12), the coe¬cient of Xt is gt h0 = 0, and as t < n, this

clearly contradicts the fact that the coe¬cient of Xt in the polynomial on

the left-hand side of (17.12) is zero. 2

As an application of Eisenstein™s criterion, we have:

Theorem 17.44. For any prime number q, the qth cyclotomic polynomial

Xq ’ 1

= Xq’1 + Xq’2 + · · · + 1

¦q :=

X’1

is irreducible over Q.

Proof. Let

(X + 1)q ’ 1

f := ¦q X + 1 = .

(X + 1) ’ 1

It is easy to see that

q’1

q

(i = 0, . . . , q ’ 1).

f= ai Xi , where ai =

i+1

i=0

Thus, aq’1 = 1, a0 = q, and for 0 < i < q ’ 1, we have q | ai (see

Exercise 1.12). Theorem 17.43 therefore applies, and we conclude that f is

irreducible over Q. It follows that ¦q is irreducible over Q, since if ¦q = gh

were a non-trivial factorization of ¦q , then f = ¦q X + 1 = g X + 1 ·

h X + 1 would be a non-trivial factorization of f . 2

Exercise 17.36. Show that neither Z[X] nor F [X, Y] (where F is a ¬eld) are

PIDs (even though they are UFDs).

Exercise 17.37. Let f ∈ Z[X] be a monic polynomial. Show that if f has a

root ± ∈ Q, then ± ∈ Z, and ± divides the constant term of f .

Exercise 17.38. Let a be a non-zero, square-free integer, with a ∈ {±1}.

For integer n ≥ 1, show that the polynomial Xn ’ a is irreducible in Q[X].

Exercise 17.39. Show that the polynomial X4 + 1 is irreducible in Q[X].

Exercise 17.40. Let F be a ¬eld, and consider the ring of bivariate polyno-

mials F [X, Y]. Show that in this ring, the polynomial X2 +Y2 ’1 is irreducible,

provided F does not have characteristic 2. What happens if F has charac-

teristic 2?

17.9 Notes 397

Exercise 17.41. Design and analyze an e¬cient algorithm for the following

problem. The input is a pair of polynomials a, b ∈ Z[X], along with their

greatest common divisor d in the ring Q[X]. The output is the greatest

common divisor of a and b the ring Z[X].

Exercise 17.42. Let a, b ∈ Z[X] be non-zero polynomials with d :=

gcd(a, b) ∈ Z[X]. Show that for any prime p not dividing lc(a) lc(b), we have

d | gcd(¯, ¯ and except for ¬nitely many primes p, we have d = gcd(¯, ¯

¯ ¯

a b), a b).

Here, d, a, and ¯ denote the images of d, a, and b in Zp [X].

¯¯ b

Exercise 17.43. Let F be a ¬eld, and let f, g ∈ F [X, Y]. De¬ne V (f, g) :=

{(x, y) ∈ F — F : f (x, y) = g(x, y) = 0F }. Show that if f and g are

relatively prime, then V (f, g) is a ¬nite set. Hint: consider the rings F (X)[Y]

and F (Y)[X].

17.9 Notes

The “(1 + i)-ary gcd algorithm” in Exercise 17.33 for computing greatest

common divisors of Gaussian integers is based on algorithms in Weilert

[100] and Damg˚ and Frandsen [31]. The latter paper also develops a

ard

corresponding algorithm for Eisenstein integers (see Exercise 17.26). Weilert

[101] presents an asymptotically fast algorithm that computes the greatest

common divisor of -bit Gaussian integers in time O( 1+o(1) ).

18

Polynomial arithmetic and applications

In this chapter, we study algorithms for performing arithmetic on poly-

nomials. Initially, we shall adopt a very general point of view, discussing

polynomials whose coe¬cients lie in an arbitrary ring R, and then specialize