Euclidean domains are principal ideal domains

A com­mon theme in ring the­ory is the idea that we iden­tify a prop­erty of the in­te­gers, and work out what that prop­erty means in a more gen­eral set­ting. The idea of the eu­clidean do­main cap­tures the fact that in \(\mathbb{Z}\), we may perform the di­vi­sion al­gorithm (which can then be used to work out great­est com­mon di­vi­sors and other such nice things from \(\mathbb{Z}\)). Here, we will prove that this sim­ple prop­erty ac­tu­ally im­poses a lot of struc­ture on a ring: it forces the ring to be a prin­ci­pal ideal do­main, so that ev­ery ideal has just one gen­er­a­tor.

In turn, this forces the ring to have unique fac­tori­sa­tion (proof), so in some sense the Fun­da­men­tal The­o­rem of Arith­metic (i.e. the state­ment that \(\mathbb{Z}\) is a unique fac­tori­sa­tion do­main) is true en­tirely be­cause the di­vi­sion al­gorithm works in \(\mathbb{Z}\).

This re­sult is es­sen­tially why we care about Eu­clidean do­mains: be­cause if we know a Eu­clidean func­tion for an in­te­gral do­main, we have a very easy way of recog­nis­ing that the ring is a prin­ci­pal ideal do­main.

For­mal statement

Let \(R\) be a eu­clidean do­main. Then \(R\) is a prin­ci­pal ideal do­main.


This proof es­sen­tially mir­rors the first proof one might find in the con­crete case of the in­te­gers, if one sat down to dis­cover an in­te­ger-spe­cific proof; but we cast it into slightly differ­ent lan­guage us­ing an equiv­a­lent defi­ni­tion of “ideal”, be­cause it is a bit cleaner that way. It is a very use­ful ex­er­cise to work through the proof, us­ing \(\mathbb{Z}\) in­stead of the gen­eral ring \(R\) and us­ing “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 Eu­clidean func­tion.

Let \(R\) be a Eu­clidean do­main, and say \(\phi: \mathbb{R} \setminus \{ 0 \} \to \mathbb{N}^{\geq 0}\) is a Eu­clidean func­tion. That is,

  • if \(a\) di­vides \(b\) then \(\phi(a) \leq \phi(b)\);

  • for ev­ery \(a\), and ev­ery \(b\) not di­vid­ing \(a\), we can find \(q\) and \(r\) such that \(a = qb+r\) and \(\phi(r) < \phi(b)\).

We need to show that ev­ery ideal is prin­ci­pal, so take an ideal \(I \subseteq R\). We’ll view \(I\) as the ker­nel of a ho­mo­mor­phism \(\alpha: R \to S\); re­call that this is the proper way to think of ideals. (Proof of the equiv­alence.) Then we need to show that there is some \(r \in R\) such that \(\alpha(x) = 0\) if and only if \(x\) is a mul­ti­ple of \(r\).

If \(\alpha\) only sends \(0\) to \(0\) (that is, ev­ery­thing else doesn’t get sent to \(0\)), then we’re im­me­di­ately done: just let \(r = 0\).

Other­wise, \(\alpha\) sends some­thing nonzero to \(0\); choose \(r\) to be nonzero with min­i­mal \(\phi\). We claim that this \(r\) works.

In­deed, let \(x\) be a mul­ti­ple of \(r\), so we can write it as \(ar\), say. Then \(\alpha(ar) = \alpha(a) \alpha(r) = \alpha(a) \times 0 = 0\). There­fore mul­ti­ples of \(r\) are sent by \(\alpha\) to \(0\).

Con­versely, if \(x\) is not a mul­ti­ple 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 defi­ni­tion of the Eu­clidean func­tion \(\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 small­est \(\phi\)-value among ev­ery­thing that \(\alpha\) sent to \(0\); so \(\alpha(b)\) can­not be \(0\), and hence nor can \(\alpha(x)\).

So we have shown that \(\alpha(x) = 0\) if and only if \(x\) is a mul­ti­ple of \(r\), as re­quired.

The con­verse is false

There do ex­ist prin­ci­pal ideal do­mains which are not Eu­clidean do­mains: \(\mathbb{Z}[\frac{1}{2} (1+\sqrt{-19})]\) is an ex­am­ple. (Proof.)