The Gaussian integers are a Euclidean domain

Statement

The ring of Gaussian integers $\mathbb{Z}[i]$ is a Euclidean domain, with the norm $N(a + b i) = a^2 + b^2$ as Euclidean function. That is, for all $z, w \in \mathbb{Z}[i]$ with $w \neq 0$, there are $q, r \in \mathbb{Z}[i]$ with $z = q w + r$ and $N(r) < N(w)$.

Remarks

The proof: write $z / w = x + y i$ in $\mathbb{C}$. Let $q = m + n i$, where $m$ and $n$ are integers nearest to $x$ and $y$. Then $|z/w - q|^2 \le \tfrac{1}{4} + \tfrac{1}{4} = \tfrac{1}{2}$, so $r = z - q w$ has $N(r) \le \tfrac{1}{2} N(w) < N(w)$. A consequence is that $\mathbb{Z}[i]$ is a principal ideal domain and a unique factorization domain.

Explanations

L1 human

To divide $z$ by $w$, compute the complex quotient and round both coordinates to the nearest integer. The rounding error is small, so the remainder is smaller than $w$ in norm. This makes the Euclidean algorithm work for Gaussian integers.