Gaussian Integers form an Euclidean Ring

Question

A Ring $R$ is called euclidean if a map $f:R\backslash {0} \rightarrow \mathbb{N}$ exists with the following properties: For two elements $a,b \in R$ with $b\neq 0$ there exist $q,r\in R$ with:

(i) $a=qb+r$ and

(ii) $r=0$ or $f\left(r \right)<f\left(b\right)$.

The Gaussian Integers are a Ring $G:= \{a+bi:a,b \in\mathbb{Z}\}$. I want to show that $G$ is an euclidean Ring. Because $G$ is obviously an Integral domain, I would be able to show that $G$ is a Principal ideal domain.

My problem is with the second part (ii). I saw that such a mapping can be defined with $a+bi \mapsto a^2 + b^2$. Here is what I don't get: In our case the $b$ in (ii) is i, so I want to find a $f$ with $f\left(a \right)<f\left(i\right)$ for the Gaussian Integers right? How is $a+bi \mapsto a^2 + b^2$ helping here? I am sorry if the notation is a bit odd. For the Gaussian integers I get (to put them into the frame like in (i)) that $a=q$, $b=i$ and $r=a$ right?

Appreciate your help, KingDingeling

Answer 1

You seem to be a bit confused. $b$ could be any element of $G$ except $0$. You have already found a good choice for $f$ so the only part left is, given arbitrary $a, b, \in G$ with $b \neq 0$, to find $q, r \in G$ satisfying (i) and (ii).

Answer 2

It might help you to understand what can happen when a ring is not Euclidean. For example, consider $\mathbb Z[\sqrt{-5}]$, consisting of all numbers of the form $m + n \sqrt{-5}$, with $m, n \in \mathbb Z$.

The natural choice of Euclidean function is $$f(m + n \sqrt{-5}) = m^2 + 5n^2.$$ Note that $f(m + n \sqrt{-5})$ can never be negative, but it can be 0. Now try $\gcd(2, 1 + \sqrt{-5})$.

Since $f(1 + \sqrt{-5}) > f(2)$, we assign $a = 1 + \sqrt{-5}$ and $b = 2$. Now we wish to express $a = qb + r$ with $f(r) < f(b)$, meaning $f(r) < 4$. Then the only possibilities for $r$ are $-1$, 0 and 1, as all other numbers in this ring have norms of at least 4.

But then we see that none of the numbers $\sqrt{-5}$, $1 + \sqrt{-5}$, $2 + \sqrt{-5}$ are divisible by 2. Therefore the Euclidean algorithm has failed in this ring, and therefore this domain is not Euclidean for the function $f$.

Your task then is to prove that this can never happen in $G$, or $\mathbb G$, or $\mathbb Z[\sqrt{-1}]$, or as it's more commonly notated, $\mathbb Z[i]$, to prove that a suitable choice of $r$ can always be found. The Euclidean function is $f(m + ni) = m^2 + 1n^2$.

A complete solution is to be found in certain number theory books, such as An Introduction to the Theory of Numbers by Ivan Niven and Herb Zuckermann.

Answer 3

"$f(a+b\mathrm{i}) = a^2 + b^2$" is what "$a+b\mathrm{i} \mapsto a^2+b^2$" means. So $f(\mathrm{i}) = f(0+1\mathrm{i}) = 0^2+1^2 = 1$. So, among other things, we find that $\mathrm{i}$ is a unit in $\mathbb{Z}[\mathrm{i}]$.

This means in your quotient and remainder expression in (ii), if $b = \mathrm{i}$, you are dividing by a unit, so you expect the remainder to be zero, which is the case : $a = q \mathrm{i} + 0$, where $q = -\mathrm{i}a$.