(c) Show that for any ± ∈ Z[i], we have ± ≡ 0 (mod π) or ± ≡ 1 (mod π).

(d) Show that the quotient ring Z[i]/πZ[i] is isomorphic to the ring Z2 .

(e) Show that for any ± ∈ Z[i] with ± ≡ 1 (mod π), there exists a unique

∈ {±1, ±i} such that ± ≡ (mod 2π).

(f) Show that for any ±, β ∈ Z[i] with ± ≡ β ≡ 1 (mod π), there exists a

unique ∈ {±1, ±i} such that ± ≡ β (mod 2π).

Exercise 17.33. We now present a “(1+i)-ary gcd algorithm” for Gaussian

integers. Let π := 1 + i ∈ Z[i]. The algorithm takes non-zero ±, β ∈ Z[i] as

input, and runs as follows:

ρ ← ±, ρ ← β, e ← 0

while π | ρ and π | ρ do ρ ← ρ/π, ρ ← ρ /π, e ← e + 1

repeat

while π | ρ do ρ ← ρ/π

while π | ρ do ρ ← ρ /π

if M (ρ ) < M (ρ) then (ρ, ρ ) ← (ρ , ρ)

determine ∈ {±1, ±i} such that ρ ≡ ρ (mod 2π)

ρ ←ρ ’ ρ

(—)

until ρ = 0

δ ← πe · ρ

output δ

Show that this algorithm correctly computes a greatest common divisor

of ± and β, and can be implemented so as to run in time O( 2 ), where

:= max(len(M (±)), len(M (β))). Hint: to analyze the running time, for

i = 1, 2, . . . , let vi (respectively, vi ) denote the value of |ρρ | just before

(respectively, after) the execution of the line marked (—) in loop iteration i,

and show that

√ √

vi ¤ (1 + 2)vi and vi+1 ¤ vi /2 2.

Exercise 17.34. Extend the algorithm of the previous exercise, so that it

computes σ, „ ∈ Z[i] such that ±σ + β„ = δ. Your algorithm should run in

392 More rings

time O( 2 ), and it should also be the case that len(M (σ)) and len(M („ ))

are O( ). Hint: adapt the algorithm in Exercise 4.2.

Exercise 17.35. In Exercise 17.32, we saw that 2 factors as ’iπ 2 in Z[i],

where π := 1 + i is irreducible. This exercise examines the factorization in

Z[i] of prime numbers p > 2.

(a) Suppose ’1 is not congruent to the square of any integer modulo p.

Show that p is irreducible in Z[i].

(b) Suppose that c2 ≡ ’1 (mod p) for some c ∈ Z. Let γ := c + i ∈ Z[i]

and let δ be a greatest common divisor in Z[i] of γ and p. Show that

¯ ¯

p = δ δ, and that δ and δ are non-associate, irreducible elements of

Z[i].

17.8.2 Unique factorization in D[X]

In this section, we prove the following:

Theorem 17.36. If D is a UFD, then so is D[X].

This theorem implies, for example, that Z[X] is a UFD. Applying the

theorem inductively, one also sees that for any ¬eld F , the ring F [X1 , . . . , Xn ]

of multi-variate polynomials over F is also a UFD.

We begin with some simple observations. First, recall that for an integral

domain D, D[X] is an integral domain, and the units in D[X] are precisely the

units in D. Second, it is easy to see that an element of D is irreducible in D if

and only if it is irreducible in D[X]. Third, for c ∈ D and f = i ai Xi ∈ D[X],

we have c | f if and only if c | ai for all i.

We call a non-zero polynomial f ∈ D[X] primitive if the only elements

in D that divide f are units. If D is a UFD, then given any non-zero

polynomial f ∈ D[X], we can write it as f = cf , where c ∈ D and f ∈ D[X]

is a primitive polynomial: just take c to be a greatest common divisor of all

the coe¬cients of f .

It is easy to prove the existence part of Theorem 17.36:

Theorem 17.37. Let D be a UFD. Any non-zero, non-unit element of D[X]

can be expressed as a product of irreducibles in D[X].

Proof. Let f be a non-zero, non-unit polynomial in D[X]. If f is a constant,

then because D is a UFD, it factors into irreducibles in D. So assume f

is not constant. If f is not primitive, we can write f = cf , where c is a

non-zero, non-unit in D, and f is a primitive, non-constant polynomial in

D[X]. Again, as D is a UFD, c factors into irreducibles in D.

17.8 Unique factorization domains (—) 393

From the above discussion, it su¬ces to prove the theorem for non-

constant, primitive polynomials f ∈ D[X]. If f is itself irreducible, we are

done. Otherwise, then we can write f = gh, where g, h ∈ D[X] and nei-

ther g nor h are units. Further, by the assumption that f is a primitive,

non-constant polynomial, both g and h must also be primitive, non-constant

polynomials; in particular, both g and h have degree strictly less than deg(f ),

and the theorem follows by induction on degree. 2

The uniqueness part of Theorem 17.36 is (as usual) more di¬cult. We

begin with the following fact:

Theorem 17.38. Let D be a UFD, let p be an irreducible in D, and let

f, g ∈ D[X]. Then p | f g implies p | f or p | g.

Proof. Consider the quotient ring D/pD, which is an integral domain (be-

cause D is a UFD), and the corresponding ring of polynomials (D/pD)[X],

which is also an integral domain. Consider the natural map from D[X] to

(D/pD)[X] that sends a ∈ D[X] to the polynomial a ∈ (D/pD)[X] obtained

¯

by mapping each coe¬cient of a to its residue class modulo p. If p | f g, then

we have

¯¯

0 = f g = f g,

¯

and since (D/pD)[X] is an integral domain, it follows that f = 0 or g = 0,

¯

which means that p | f or p | g. 2

Theorem 17.39. Let D be a UFD. The product of two primitive polynomi-

als in D[X] is also primitive.

Proof. Let f, g ∈ D[X] be primitive polynomials, and let h := f g. If h is

not primitive, then m | h for some non-zero, non-unit m ∈ D, and as D is a

UFD, there is some irreducible element p ∈ D that divides m, and therefore,

divides h as well. By Theorem 17.38, it follows that p | f or p | g, which

implies that either f is not primitive or g is not primitive. 2

Suppose that D is a UFD and that F is its ¬eld of fractions. Any non-zero

polynomial f ∈ F [X] can always be written as f = (c/d)f , where c, d ∈ D,

with d = 0, and f ∈ D[X] is primitive. To see this, clear the denominators

of the coe¬cients of f , writing df = f , where 0 = d ∈ D and f ∈ D[X].

Then take c to be a greatest common divisor of the coe¬cients of f , so

that f = cf , where f ∈ D[X] is primitive. Then we have f = (c/d)f , as

required. Of course, we may assume that c and d are relatively prime ” if

not, we may divide c and d by a greatest common divisor.

As a consequence of the previous theorem, we have:

394 More rings

Theorem 17.40. Let D be a UFD and let F be its ¬eld of fractions. Let

f, g ∈ D[X] and h ∈ F [X] be non-zero polynomials such that f = gh and g is

primitive. Then h ∈ D[X].

Proof. Write h = (c/d)h , where c, d ∈ D and h ∈ D[X] is primitive. Let us

assume that c and d are relatively prime. Then we have

d · f = c · gh . (17.11)

We claim that d ∈ D— . To see this, note that (17.11) implies that d |

(c · gh ), and the assumption that c and d are relatively prime implies that

d | gh . But by Theorem 17.39, gh is primitive, from which it follows that

d is a unit. That proves the claim.

It follows that c/d ∈ D, and hence h = (c/d)h ∈ D[X]. 2

Theorem 17.41. Let D be a UFD and F its ¬eld of fractions. If f ∈ D[X]

with deg(f ) > 0 is irreducible, then f is also irreducible in F [X].

Proof. Suppose that f is not irreducible in F [X], so that f = gh for non-

constant polynomials g, h ∈ F [X], both of degree strictly less than that of f .

We may write g = (c/d)g , where c, d ∈ D and g ∈ D[X] is primitive. Set

h := (c/d)h, so that f = gh = g h . By Theorem 17.40, we have h ∈ D[X],

and this shows that f is not irreducible in D[X]. 2

Theorem 17.42. Let D be a UFD. Let f ∈ D[X] with deg(f ) > 0 be

irreducible, and let g, h ∈ D[X]. If f divides gh in D[X], then f divides

either g or h in D[X].

Proof. Suppose that f ∈ D[X] with deg(f ) > 0 is irreducible. This implies

that f is a primitive polynomial. By Theorem 17.41, f is irreducible in F [X],