# Gaussian Integers form an Euclidean Ring

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).

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) 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?

• I get the impression that you're confusing two different things. The $a$ and $b$ in (i) are two complex numbers, and have nothing to do with the $a$ and $b$ in $a^2+b^2$ which are two real numbers. – saulspatz Jan 5 at 16:32
• You have to find $q\in\mathbf Z[i]$ such that the norm of $a-qb$ is less that the norm of $b$. – Bernard Jan 5 at 16:33
• I don't know if you want to do this as an exercise. If not I can also post a complete solution. – 0x539 Jan 5 at 16:33
• You are using $b$ in two different ways. One is as an element of the ring in the first paragraph and one is as the imaginary component of an element in the second paragraph. In neither case is $b$ given to be $i$ – Ross Millikan Jan 5 at 16:36
• @KingDingeling A complete solution can also be found in the book by Dummit & Foote, somewhere in chapter $8$. The outline goes like this: if you're trying to divide $a+bi$ by $c+di$, first compute $\dfrac {a+bi}{c+di} = r+qi$ where $r, q$ are rational (you can do this by multiplying the top and bottom of the LHS by $c-di$). So we can write $a+bi = (c+di)(r+qi)$. Now let $x$ be the closest integer to $r$ and $y$ be the closest integer to $q$. We can write then $a+bi = (c+di)(x+yi) + remainder$. Your job now is to show that $|remainder| < |c+di|$. – Ovi Jan 5 at 17:21

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).

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.

"$$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$$.