A common theme in ring theory is the idea that we identify a property of the integers, and work out what that property means in a more general setting. The idea of the euclidean domain captures the fact that in \(\mathbb{Z}\), we may perform the division algorithm (which can then be used to work out greatest common divisors and other such nice things from \(\mathbb{Z}\)). Here, we will prove that this simple property actually imposes a lot of structure on a ring: it forces the ring to be a principal ideal domain, so that every ideal has just one generator.

In turn, this forces the ring to have unique factorisation (proof), so in some sense the Fundamental Theorem of Arithmetic (i.e. the statement that \(\mathbb{Z}\) is a unique factorisation domain) is true entirely because the division algorithm works in \(\mathbb{Z}\).

This result is essentially why we care about Euclidean domains: because if we know a Euclidean function for an integral domain, we have a very easy way of recognising that the ring is a principal ideal domain.

Formal statement

Let \(R\) be a euclidean domain. Then \(R\) is a principal ideal domain.

Proof

This proof essentially mirrors the first proof one might find in the concrete case of the integers, if one sat down to discover an integer-specific proof; but we cast it into slightly different language using an equivalent definition of “ideal”, because it is a bit cleaner that way. It is a very useful exercise to work through the proof, using \(\mathbb{Z}\) instead of the general ring \(R\) and using “size” noteThat is, if \(n > 0\) then the size is \(n\); if \(n < 0\) then the size is \(-n\). We just throw away the sign. as the Euclidean function.

Let \(R\) be a Euclidean domain, and say \(\phi: \mathbb{R} \setminus \{ 0 \} \to \mathbb{N}^{\geq 0}\) is a Euclidean function. That is,

• if \(a\) divides \(b\) then \(\phi(a) \leq \phi(b)\);

• for every \(a\), and every \(b\) not dividing \(a\), we can find \(q\) and \(r\) such that \(a = qb+r\) and \(\phi(r) < \phi(b)\).

We need to show that every ideal is principal, so take an ideal \(I \subseteq R\). We’ll view \(I\) as the kernel of a homomorphism \(\alpha: R \to S\); recall that this is the proper way to think of ideals. (Proof of the equivalence.) Then we need to show that there is some \(r \in R\) such that \(\alpha(x) = 0\) if and only if \(x\) is a multiple of \(r\).

If \(\alpha\) only sends \(0\) to \(0\) (that is, everything else doesn’t get sent to \(0\)), then we’re immediately done: just let \(r = 0\).

Otherwise, \(\alpha\) sends something nonzero to \(0\); choose \(r\) to be nonzero with minimal \(\phi\). We claim that this \(r\) works.

Indeed, let \(x\) be a multiple of \(r\), so we can write it as \(ar\), say. Then \(\alpha(ar) = \alpha(a) \alpha(r) = \alpha(a) \times 0 = 0\). Therefore multiples of \(r\) are sent by \(\alpha\) to \(0\).

Conversely, if \(x\) is not a multiple of \(r\), then we can write \(x = ar+b\) where \(\phi(b) < \phi(r)\) and \(b\) is nonzero. noteThe fact that we can do this is part of the definition of the Euclidean function \(\phi\). Then \(\alpha(x) = \alpha(ar)+\alpha(b)\); we already have \(\alpha(r) = 0\), so \(\alpha(x) = \alpha(b)\). But \(b\) has a smaller \(\phi\)-value than \(r\) does, and we picked \(r\) to have the smallest \(\phi\)-value among everything that \(\alpha\) sent to \(0\); so \(\alpha(b)\) cannot be \(0\), and hence nor can \(\alpha(x)\).

So we have shown that \(\alpha(x) = 0\) if and only if \(x\) is a multiple of \(r\), as required.

The converse is false

There do exist principal ideal domains which are not Euclidean domains: \(\mathbb{Z}[\frac{1}{2} (1+\sqrt{-19})]\) is an example. (Proof.)