Proof that the integers are a Euclidean domain

Proof

We use the well-ordering principle. Let $\Z$ be the ring of integers.

1. The ring $\Z$ is commutative and $1 \neq 0$. If $a \neq 0$ and $b \neq 0$, then $\abs{a b} = \abs{a} \abs{b} \ge 1$, so $a b \neq 0$. So $\Z$ is an integral domain.
2. For $n \neq 0$, $\delta(n) = \abs{n}$ is a natural number. So $\delta$ is a function $\Z \setminus \set{0} \to \N$.
3. Let $a, b \in \Z$ with $b \neq 0$. Let $S = \set{a - b q : q \in \Z} \cap \N$, where $\N$ contains $0$.
4. Let $q_0 = -\abs{a}$ if $b > 0$ and $q_0 = \abs{a}$ if $b < 0$. In both cases $b q_0 = -\abs{a} \abs{b}$.
5. Then $a - b q_0 = a + \abs{a} \abs{b} \ge a + \abs{a} \ge 0$, because $\abs{b} \ge 1$. So $a - b q_0 \in S$, and $S$ is nonempty.
6. By the well-ordering principle, $S$ has a least element $r$. Write $r = a - b q$ with $q \in \Z$, so $a = b q + r$ and $r \ge 0$.
7. Suppose that $r \ge \abs{b}$. Let $e = 1$ if $b > 0$ and $e = -1$ if $b < 0$, so that $b e = \abs{b}$.
8. Then $a - b (q + e) = r - \abs{b} \ge 0$, so $r - \abs{b} \in S$. But $r - \abs{b} < r$, because $\abs{b} \ge 1$. This contradicts the choice of $r$.
9. Hence $0 \le r < \abs{b}$. This proves the division with remainder in the statement.
10. If $r \neq 0$, then $\delta(r) = r < \abs{b} = \delta(b)$. So $r = 0$ or $\delta(r) < \delta(b)$.
11. By steps 1, 2 and 10, $\Z$ is a Euclidean domain with Euclidean function $\delta(n) = \abs{n}$.