where δ ∈ C with N (δ) ¤ 1/4 + 1/4 = 1/2, and

ρ = ± ’ βξ = ± ’ β(±β ’1 ’ δ) = δβ,

and hence

1

N (ρ) = N (δβ) = N (δ)N (β) ¤ N (β). 2

2

Theorem 17.29. If D is a Euclidean domain and I is an ideal of D, then

there exists d ∈ D such that I = dD.

Proof. If I = {0}, then d = 0 does the job, so let us assume that I = {0}.

Let d be an non-zero element of I such that S(d) is minimal, where S is a

size function that makes D into a Euclidean domain. We claim that I = dD.

It will su¬ce to show that for all c ∈ I, we have d | c. Now, we know

388 More rings

that there exists q, r ∈ D such that c = qd + r, where either r = 0 or

S(r) < S(d). If r = 0, we are done; otherwise, r is a non-zero element of I

with S(r) < S(d), contradicting the minimality of S(d). 2

Recall that an ideal of the form I = dD is called a principal ideal. If

all ideals of D are principal, then D is called a principal ideal domain

(PID). Theorem 17.29 says that any Euclidean domain is a PID.

PIDs enjoy many nice properties, including:

Theorem 17.30. If D is a PID, then D is a UFD.

For the rings Z and F [X], the proof of part (i) of De¬nition 17.25 was

a quite straightforward induction argument (as it also would be for any

Euclidean domain). For a general PID, however, this requires a di¬erent

sort of argument. We begin with the following fact:

Theorem 17.31. If D is a PID, and I1 ⊆ I2 ⊆ · · · is an ascending chain

of ideals of D, then there exists an integer k such that Ik = Ik+1 = · · · .

Proof. Let I := ∞ Ii . It is easy to see that I is an ideal. Thus, I = dD for

i=1

some d ∈ D. But d ∈ ∞ Ii implies that d ∈ Ik for some k, which shows

i=1

that I = dD ⊆ Ik . It follows that I = Ik = Ik+1 = · · · . 2

We can now prove the existence part of Theorem 17.30:

Theorem 17.32. If D is a PID, then every non-zero, non-unit element of

D can be expressed as a product of irreducibles in D.

Proof. Let n ∈ D, n = 0, and n not a unit. If n is irreducible, we are done.

Otherwise, we can write n = ab, where neither a nor b are units. As ideals,

we have nD aD and nD bD. If we continue this process recursively,

building up a “factorization tree” where n is at the root, a and b are the

children of n, and so on, then the recursion must stop, since any in¬nite

path in the tree would give rise to a chain of ideals

··· ,

nD = I1 I2

contradicting Theorem 17.31. 2

The proof of the uniqueness part of Theorem 17.30 is essentially the same

as for proofs we gave for Z and F [X].

Analogous to Theorems 1.6 and 17.8, we have:

Theorem 17.33. Let D be a PID. For any a, b ∈ D, there exists a greatest

common divisor d of a and b, and moreover, aD + bD = dD.

17.8 Unique factorization domains (—) 389

Proof. Exercise. 2

As an immediate consequence of the previous theorem, we see that in a

PID D, for all a, b ∈ D with greatest common divisor d, there exist s, t ∈ D

such that as + bt = d; moreover, a, b ∈ D are relatively prime if and only if

there exist s, t ∈ D such that as + bt = 1.

Analogous to Theorems 1.7 and 17.9, we have:

Theorem 17.34. Let D be a PID. For a, b, c ∈ D such that c | ab and a

and c are relatively prime, we have c | b.

Proof. Exercise. 2

Analogous to Theorems 1.8 and 17.10, we have:

Theorem 17.35. Let D be a PID. Let p ∈ D be irreducible, and let a, b ∈ D.

Then p | ab implies that p | a or p | b. That is, all irreducibles in D are

prime.

Proof. Exercise. 2

Theorem 17.30 now follows immediately from Theorems 17.32, 17.35, and

17.27.

√

Exercise 17.25. Show that Z[ ’2] is a Euclidean domain.

Exercise 17.26. Consider the polynomial

X3 ’ 1 = (X ’ 1)(X2 + X + 1).

√ √

Over C, the roots of X3 ’ 1 are 1, (’1 ± ’3)/2. Let ω := (’1 + ’3)/2,

√

and note that ω 2 = ’1 ’ ω = (’1 ’ ’3)/2, and ω 3 = 1.

(a) Show that the ring Z[ω] consists of all elements of the form a + bω,

where a, b ∈ Z, and is an integral domain. This ring is called the ring

of Eisenstein integers.

(b) Show that the only units in Z[ω] are ±1, ±ω, and ±ω 2 .

(c) Show that Z[ω] is a Euclidean domain.

Exercise 17.27. Show that in a PID, all non-zero prime ideals are maximal.

Recall that for a complex number ± = a + bi, with a, b ∈ R, the norm of

± was de¬ned as N (±) = ±± = a2 + b2 (see Example 9.5). There are other

¯

measures of the “size” of a complex number that are useful. The absolute

√

value of ± is de¬ned as |±| := N (±) = a2 + b2 . The max norm of ± is

de¬ned as M (±) := max{|a|, |b|}.

390 More rings

Exercise 17.28. Let ±, β ∈ C. Prove the following statements.

(a) |±β| = |±||β|.

(b) |± + β| ¤ |±| + |β|.

(c) N (± + β) ¤ 2(N (±) + N (β)).

√

(d) M (±) ¤ |±| ¤ 2M (±).

The following exercises develop algorithms for computing with Gaussian

integers. We shall assume that for computational purposes, a Gaussian

integer ± = a + bi, with a, b ∈ Z, is represented as the pair of integers (a, b).

Exercise 17.29. Let ±, β ∈ Z[i].

(a) Show how to compute M (±) in time O(len(M (±))) and N (±) in time

O(len(M (±))2 ).

(b) Show how to compute ± + β in time O(len(M (±)) + len(M (β))).

(c) Show how to compute ± · β in time O(len(M (±)) · len(M (β))).

(d) Assuming β = 0, show how to compute ξ, ρ ∈ Z[i] such that ± = βξ +

ρ, N (ρ) ¤ 1 N (β), and N (ξ) ¤ 4N (±)/N (β). Your algorithm should

2

run in time O(len(M (±))·len(M (β))). Hint: see Example 17.14; also,

to achieve the stated running time bound, your algorithm should ¬rst

test if M (β) ≥ 2M (±).

Exercise 17.30. Using the division with remainder algorithm from part

(d) of the previous exercise, adapt the Euclidean algorithm for (ordinary)

integers to work with Gaussian integers. On inputs ±, β ∈ Z[i], your algo-

rithm should compute a greatest common divisor δ ∈ Z[i] of ± and β in time

O( 3 ), where := max{len(M (±)), len(M (β))}.

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

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

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

are O( ).

The algorithms in the previous two exercises for computing greatest com-

mon divisors in Z[i] run in time cubic in the length of their input, whereas

the corresponding algorithms for Z run in time quadratic in the length of

their input. This is essentially because the running time of the algorithm

for division with remainder discussed in Exercise 17.29 is insensitive to the

size of the quotient.

To get a quadratic-time algorithm for computing greatest common divisors

in Z[i], in the following exercises we shall develop an analog of the binary

gcd algorithm for Z.

17.8 Unique factorization domains (—) 391

Exercise 17.32. Let π := 1 + i ∈ Z[i].

(a) Show that 2 = π¯ = ’iπ 2 , that N (π) = 2, and that π is irreducible

π

in Z[i].

(b) Let ± ∈ Z[i], with ± = a + bi for a, b ∈ Z. Show that π | ± if and only

if a ’ b is even, in which case

a+b b’a

±

= + i.