Let be an integral domain and let be a bounded divisibility norm. (That is, , and .) We say that is 2-stage Euclidean with respect to if for all with , there exist such that , , and either or .

Generalize this definition to “-stage Euclidean domains” and prove the following.

- For all in a -stage Euclidean domain with , then and have a greatest common divisor which is a linear combination of and . Conclude that every finitely generated ideal of is principal.
- Prove that if is a -stage Euclidean domain in which every nonzero nonunit is a finite product of irreducibles, then is a unique factorization domain.

We begin with a definition.

Let be an integral domain. Let . We will call elements of *division sequences* in . A division sequence is said to *terminate* if for some . Next we prove some basic properties of division sequences.

Lemma: Let be an integral domain and let .

- for all .
- for all .
- for all .
- If and , then for all .
- If , then for all .
- If terminates, then and have a greatest common divisor, which is contained in .

Proof:

- We have .
- .
- Certainly . Then .
- Follows since .
- Follows since .
- Let be minimal such that . If , then so that is a greatest common divisor of and , and certainly . If , then by (5). Since , using (4) and induction, for all . In particular, and . By (3), . If and , then , so that . So is a greatest common divisor of and .

Evidently, then, if with and there exists a terminating division sequence such that and , then is principal; that is, and have a greatest common divisor which is a linear combination of and . We are now in a position to define -stage Euiclidean domains.

Let be an integral domain and let be a divisibility norm. We say that is -stage Euclidean with respect to if for all such that , there exists a division sequence such that , , and either or .

The significance of the -stage condition is that it allows us to patch together a terminating division sequence for all pairs of elements, and moreover to give an upper bound on its length.

Let be a -stage Euclidean domain with respect to and let with . We claim that there is a terminating division sequence whose first two terms are and ; we proceed by induction on . Let be nonzero and of minimal norm. By the -stage condition, there is a division sequence such that , , and or . Since has minimal norm, , and thus terminates. Suppose that for some , for all and such that and , there is a terminating division sequence whose first two terms are and . Let be nonzero and of minimal norm greater than . We have such that , , and either or . If , then terminates. If , then by the induction hypothesis there is a terminating division sequence such that and . Then defined by if and otherwise and if and otherwise is a terminating division sequence whose first two terms are and .

Thus every pair of elements in a -stage Euclidean domain are the first two terms of a terminating division sequence, and thus have a greatest common divisor which is contained in . By an easy induction argument, every finitely generated ideal is principal.

Suppose now that is -stage Euclidean with respect to and that every nonzero nonunit in is a finite product of irreducibles.

First we will show that every irreducible in is prime. To that end, let be irreducible and suppose . Consider the ideal ; by the previous discussion, is principal, and so for some . Since is irreducible, either is a unit, so that and , or is a unit and . Then for some . Multiplying by , we have ; since , we have . Thus is prime.

Now we show that if is a nonzero nonunit, then any to factorizations of have the same length and are unique up to units. We proceed by induction on the length of the shortest factorization. For the base case, suppose , where and the are irreducible. Since is prime, then (reordering if necessary) we have ; since is irreducible, for some unit . Then . Since is a domain, . In particular, is a unit for each , a contradiction, so that in fact . Thus ; so if has an irreducible factorization of length 1, then all factorizations have length 1 and are unique up to units. For the inductive step, suppose that for some , every nonzero nonunit which has an irreducible factorization of length has an essentially unique factorization. Let be a nonzero nonunit with a factorization of length , say . Suppose is another irreducible factorization, with . Since is prime, then without loss of generality divides . Since is irreducible, for some unit . From , we have . By the induction hypothesis, and the and are pairwise associates. Thus all factorizations of have length and (up to a reordering) the irreducible factors are associates.

Thus if every nonzero nonunit has a factorization into irreducibles, then every element has an essentially unique factorization. Thus is a unique factorization domain.

As a side note, the significance of the -stage Euclidean condition is that it guarantees the existence of a terminating division sequence and gives an upper bound on its length. We could weaken this condition as follows: say an integral domain with divisibility norm is finite stage Euclidean if for all with , there exists an integer and a division sequence such that , , and or . (That is, for all pairs, some finite number of divisions yields a remainder of smaller norm than . We still have that a terminating sequence exists for all , but now there is no upper bound on how long such a sequence might be.