Ytdyklly

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

(i) $a=qb+r$ and

(ii) $r=0$ or $fleft(r right)<fleft(bright)$.

The Gaussian Integers are a Ring $G:= {a+bi:a,b inmathbb{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 $fleft(a right)<fleft(iright)$ 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

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+bmathrm{i}) = a^2 + b^2$" is what "$a+bmathrm{i} mapsto a^2+b^2$" means. So $f(mathrm{i}) = f(0+1mathrm{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$.