Euclidean Domains

In the previous section we proved that a principal ideal domain possesses the property of unique factorization. Now we are faced with the problem of determining whether or not a given integral domain is a principal ideal domain. This is generally a very difficult question. However, a partial solution is available. Notice that we were able to prove that Z and F[X] are PIDs by using the division algorithm in Z and F[X] respectively. In this section let us introduce a class of integral domains in which an analogue of the division algorithm holds. We will show that every such ring is a PID.

Definition 1: Let R be an integral domain. Then R is called a Euclidean domain if there exists a function :RZ such that

(1) (x) > 0 for all x R.

(2) (x) = 0 if and only if x = 0.

(3) (xy) = (x)(y) for all x,y R.

(4) Let x,y R, y0. Then there exist q,r R such that x = qy + r, 0 < (r) < (y). (This is a generalization of the division algorithm.)

Example 1: Let R = Z, (x) = |x|. Then conditions (1)-(3) are elementary properties of absolute values. Condition (4) is just the division algorithm in Z.

Example 2: Let R = F[X]. Set (x) = 2^deg(x) (x0), and and = 0 (x = 0). Then (1)-(3) are easy to check. Moreover, by the division algorithm in F[X], given x,y R, y 0, there exist q,r R such that x = qy + r, deg(r) < deg(y). But then 0 < (r) < (y) and condition (4) holds.

Theorem 2: Let R be a Euclidean domain. Then R is a principal ideal domain.

Proof: Let I be a nonzero ideal of R. It suffices to show that I is principal. Let a I be chosen so that a0 and (a) is a small as possible. We assert that I = (a). It is clear that (a) I. Let x I. Since R is a Euclidean domain, there exist q,t R so that

x = qa + r,    0 < (r) < (a).

Note that r = x - qa I If r0, then (r) < (a), r I, which contradicts the choice of a. Therefore, r = 0 and x = qa (a). Thus I (a).

Let us now give an example of a Euclidean domain which is connected with Fermat's last theorem.

Theorem 3: Let = (-1 + i)/2. Then is a primitive cube root of 1 and Z[] is a Euclidean domain.

Before proving Theorem 3, it is necessary to describe Z[] more explicitly. Note that ² + + 1 = 0, so that

² {a + b | a,b Z}.

Also, ³ = -² - , so that

³ {a + b | a,b Z}.

Proceeding by induction, we see that

ⁿ {a + b | a,b Z}

for all n > 1. Therefore,

Z[] = {a + b | a,b Z}.

Moreover, every element of Z[] can be written uniquely in the form a + b, since

a + b = a' + b' a - a' = (b' - b)

(b' - b) Z

b' - b = 0

a - a' =0.

And we have proved the following

Lemma 4: Every element of Z[] can be uniquely written in the form a + b, a,b Z.

Proof of Theorem 3: If a,b Q, define (a + b) = (a + b)(a + b) = a² - ab + b², where denotes the complex conjugate of . Since a + b = a + b, we see that (a + b) = |a + b|² > 0. Moreover, (a + b) = 0 a + b = 0. Further, if a,b Z, (a + b) = a² - ab + b² Z. We leave it as an exercise to verify that () = ()() for , {a + b | a,b Q}. Let us verify the division algorithm. This is where we use the special properties of . Let x = a + b, y = c + d Z[], y0. Then, in C, we have

where

,

belong to Q. There exist integers and such that

|e - | < 1/2,  |f - | < 1/2.

Set q = + , r = [(e - ) + (f - )]y. Then q Z[] and

so that r = x - qy Z[]. Finally

(r) = ((e - ) + (f - ))(y)

= {(e - )² - (e - )(f - ) + (f - )²}(y)

< {1/4 + 1/4 + 1/4}(y)

< (y).

Corollary 5: If = (-1 + i)/2 is a primitive cube root of 1, then Z[] is a unique factorization domain.