[summary: The [-division_algorithm] is a fundamental property of the integers, and it turns out that almost all of the nicest properties of the integers stem from the division algorithm. All rings which have the division algorithm (that is, [euclidean_domain Euclidean domains]) are principal ideal domains: they have the property that every [ideal_ring_theory ideal] has just one generator.]
[summary(Technical): Let $~$R$~$ be a [euclidean_domain]. Then $~$R$~$ is a Principal ideal domain.]
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_ring_theory ideal] has just one generator.
In turn, this forces the ring to have unique factorisation ([pid_implies_ufd 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" %%note:That 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_ring_theory ideal] is principal, so take an ideal $~$I \subseteq R$~$. We'll view $~$I$~$ as the kernel of a [ring_homomorphism 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. %%note: The 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.)