## Definition and basic properties of k-stage Euclidean domains

Let $R$ be an integral domain and let $N : R \rightarrow \mathbb{N}$ be a bounded divisibility norm. (That is, $N(ab) = N(a)N(b)$, $N(0) = 0$ and $N(1) = 1$.) We say that $R$ is 2-stage Euclidean with respect to $N$ if for all $a,b \in R$ with $b \neq 0$, there exist $q_1,q_2,r_1,r_2 \in R$ such that $a = q_1b + r_1$, $b = q_2r_1 + r_2$, and either $r_2 = 0$ or $N(r_2) < N(b)$.

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

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

We begin with a definition.

Let $R$ be an integral domain. Let $\mathcal{A}(R) = \{ (\lambda,\theta) \ |\ \lambda,\theta : \mathbb{N} \rightarrow R, \lambda_k = \theta_k \lambda_{k+1} + \lambda_{k+2}\ \mathrm{for\ all}\ k \}$. We will call elements of $\mathcal{A}(R)$ division sequences in $R$. A division sequence $(\lambda,\theta)$ is said to terminate if $\lambda_k = 0$ for some $k$. Next we prove some basic properties of division sequences.

Lemma: Let $R$ be an integral domain and let $(\lambda,\theta) \in \mathcal{A}(R)$.

1. $\lambda_{k+2} \in (\lambda_k, \lambda_{k+1})$ for all $k$.
2. $(\lambda_{k+1},\lambda_{k+2}) \subseteq (\lambda_k,\lambda_{k+1})$ for all $k$.
3. $\lambda_k \in (\lambda_0,\lambda_1)$ for all $k$.
4. If $q|\lambda_{k+1}$ and $q|\lambda_{k+2}$, then $q|\lambda_k$ for all $k$.
5. If $\lambda_{k+2} = 0$, then $\lambda_{k+1}|\lambda_k$ for all $k$.
6. If $(\lambda,\theta)$ terminates, then $\lambda_0$ and $\lambda_1$ have a greatest common divisor, which is contained in $(\lambda_0,\lambda_1)$.

Proof:

1. We have $\lambda_{k+2} = \lambda_k - \theta_k\lambda_{k+1}$.
2. $(\lambda_{k+1},\lambda_{k+2}) \subseteq (\lambda_{k+1}, \lambda_k, \lambda_{k+1}) = (\lambda_k,\lambda_{k+1})$.
3. Certainly $\lambda_0,\lambda_1 \in (\lambda_0,\lambda_1)$. Then $\lambda_{k+2} \in (\lambda_k,\lambda_{k+1}) \subseteq (\lambda_0,\lambda_1)$.
4. Follows since $\lambda_k = \theta_k\lambda_{k+1} + \lambda_{k+2}$.
5. Follows since $\lambda_k = \theta_k\lambda_{k+1}$.
6. Let $t$ be minimal such that $\lambda_{t+1} = 0$. If $t = 0$, then $\lambda_1 = 0$ so that $\lambda_0$ is a greatest common divisor of $\lambda_0$ and $\lambda_1$, and certainly $\lambda_0 \in (\lambda_0,\lambda_1)$. If $t \geq 1$, then $\lambda_t|\lambda_{t-1}$ by (5). Since $\lambda_t|\lambda_t$, using (4) and induction, $\lambda_t|\lambda_k$ for all $0 \leq k \leq t$. In particular, $\lambda_t|\lambda_0$ and $\lambda_t|\lambda_1$. By (3), $(\lambda_t) = (\lambda_0,\lambda_1)$. If $q|\lambda_0$ and $q|\lambda_1$, then $(\lambda_t) = (\lambda_0,\lambda_1) \subseteq (q)$, so that $q|\lambda_t$. So $\lambda_t$ is a greatest common divisor of $\lambda_0$ and $\lambda_1$.

Evidently, then, if $a,b \in R$ with $b \neq 0$ and there exists a terminating division sequence $(\lambda,\theta)$ such that $\lambda_0 = a$ and $\lambda_1 = b$, then $(a,b)$ is principal; that is, $a$ and $b$ have a greatest common divisor which is a linear combination of $a$ and $b$. We are now in a position to define $k$-stage Euiclidean domains.

Let $R$ be an integral domain and let $N : R \rightarrow \mathbb{N}$ be a divisibility norm. We say that $R$ is $k$-stage Euclidean with respect to $N$ if for all $a,b \in R$ such that $b \neq 0$, there exists a division sequence $(\lambda,\theta) \in \mathcal{A}(R)$ such that $\lambda_0 = a$, $\lambda_1 = b$, and either $\lambda_{k+1} = 0$ or $N(\lambda_{k+1}) < N(b)$.

The significance of the $k$-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 $R$ be a $k$-stage Euclidean domain with respect to $N$ and let $a,b \in R$ with $b \neq 0$. We claim that there is a terminating division sequence whose first two terms are $a$ and $b$; we proceed by induction on $N(b)$. Let $b \in R$ be nonzero and of minimal norm. By the $k$-stage condition, there is a division sequence $(\lambda,\theta)$ such that $\lambda_0 = a$, $\lambda_1 = b$, and $\lambda_{k+1} = 0$ or $N(\lambda_{k+1}) < N(b)$. Since $b$ has minimal norm, $\lambda_{k+1} = 0$, and thus $(\lambda,\theta)$ terminates. Suppose that for some $k \in \mathbb{N}$, for all $a$ and $b$ such that $b \neq 0$ and $N(b) \leq k$, there is a terminating division sequence whose first two terms are $a$ and $b$. Let $b$ be nonzero and of minimal norm greater than $k$. We have $(\lambda,\theta)$ such that $\lambda_0 = a$, $\lambda_1 = b$, and either $\lambda_{k+1} = 0$ or $N(\lambda_{k+1}) < N(b)$. If $\lambda_{k+1} = 0$, then $(\lambda,\theta)$ terminates. If $N(\lambda_{k+1}) < N(b)$, then by the induction hypothesis there is a terminating division sequence $(\lambda^\prime,\theta^\prime)$ such that $\lambda^\prime_0 = \lambda_k$ and $\lambda^\prime_1 = \lambda_{k+1}$. Then $(\lambda^{\prime\prime},\theta^{\prime\prime})$ defined by $\lambda^{\prime\prime}_i = \lambda_i$ if $i < k$ and $\lambda^\prime_{i-k}$ otherwise and $\theta^{\prime\prime}_i = \theta_i$ if $i < k$ and $\theta^\prime_{i-k}$ otherwise is a terminating division sequence whose first two terms are $a$ and $b$.

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

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

First we will show that every irreducible in $R$ is prime. To that end, let $x \in R$ be irreducible and suppose $x|ab$. Consider the ideal $(a,x)$; by the previous discussion, $(a,x) = (d)$ is principal, and so $x = du$ for some $u$. Since $x$ is irreducible, either $u$ is a unit, so that $(a,x) = (x)$ and $x|a$, or $d$ is a unit and $(a,x) = (1)$. Then $as + xt = 1$ for some $s,t \in R$. Multiplying by $b$, we have $abs + bxt = b$; since $x|ab$, we have $x|b$. Thus $x$ is prime.

Now we show that if $a \in R$ is a nonzero nonunit, then any to factorizations of $a$ 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 $a = x = \prod_{i=1}^n y_i$, where $x$ and the $y_i$ are irreducible. Since $x$ is prime, then (reordering if necessary) we have $x|y_1$; since $y_1$ is irreducible, $y_1 = ux$ for some unit $u$. Then $x = xu\prod_{i=2}^n y_i$. Since $R$ is a domain, $u\prod_{i=2}^n y_i = 1$. In particular, $y_i$ is a unit for each $2 \leq i \leq n$, a contradiction, so that in fact $n = 1$. Thus $a = y_1u^{-1} = x$; so if $a$ 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 $k$, every nonzero nonunit which has an irreducible factorization of length $k$ has an essentially unique factorization. Let $a$ be a nonzero nonunit with a factorization of length $k+1$, say $a = \prod_{i=1}^{k+1}x_i$. Suppose $a = \prod_{i=1}^n y_i$ is another irreducible factorization, with $n \geq k+1$. Since $x_1$ is prime, then without loss of generality $x_1$ divides $y_1$. Since $y_1$ is irreducible, $x_1u = y_1$ for some unit $u$. From $\prod_{i=1}^{k+1} x_i = \prod_{i=1}^n y_i = x_1u\prod_{i=1}^n y_i$, we have $\prod_{i=2}^{k+1} x_i = u\prod_{i=2}^n y_i$. By the induction hypothesis, $n = k+1$ and the $x_i$ and $y_i$ are pairwise associates. Thus all factorizations of $a$ have length $k+1$ 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 $R$ is a unique factorization domain.

As a side note, the significance of the $k$-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 $R$ with divisibility norm $N$ is finite stage Euclidean if for all $a,b \in R$ with $b \neq 0$, there exists an integer $k$ and a division sequence $(\lambda,\theta)$ such that $\lambda_0 = a$, $\lambda_1 = b$, and $\lambda_{k+1} = 0$ or $N(\lambda_{k+1}) < N(b)$. (That is, for all pairs, some finite number of divisions yields a remainder of smaller norm than $b$. We still have that a terminating sequence exists for all $a,b$, but now there is no upper bound on how long such a sequence might be.