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 ^{2} + + 1 = 0, so that
Also, ^{3} = ^{2}  , so that
Proceeding by induction, we see that
for all n > 1. Therefore,
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 = 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^{2}  ab + b^{2}, where denotes the complex conjugate of . Since a + b = a + b, we see that (a + b) = a + b^{2} > 0. Moreover, (a + b) = 0 a + b = 0. Further, if a,b Z, (a + b) = a^{2}  ab + b^{2} 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
x = qy + r,
so that r = x  qy Z[]. Finally
(r) = ((e  ) + (f  ) ) (y)
= {(e  ) ^{2}  (e  )(f  ) + (f  ) ^{2}} (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.
