# Prove that the Gaussian Integer's ring is a Euclidean domain

I'm having some trouble proving that the Gaussian Integer's ring ($\mathbb{Z}[ i ]$) is an Euclidean domain. Here is what i've got so far.

To be a Euclidean domain means that there is a defined application (often called norm) that verifies this two conditions:

• $\forall a, b \in \mathbb{Z}[i] \backslash {0} \hspace{2 mm} a \mid b \hspace{2 mm} \rightarrow N(a) \leq N (b)$
• $\forall a, b \in \mathbb{Z}[i] \hspace{2 mm} b \neq 0 \rightarrow \exists c,r \in \mathbb{Z}[i] \hspace {2 mm}$ so that $\hspace{2 mm} a = bc + r \hspace{2 mm} \text{and} \hspace{2 mm} (r = 0 \hspace{2 mm} \text{or} \hspace{2 mm} r \neq 0 \hspace{2 mm} N(r) \lt N (b) )$

I have that the application meant to be the "norm" goes: $N(a +b i) = a^2 + b^2$, and I've managed to prove the first condition, given that N is a multiplicative function, but I can not find a way to prove the second condition.

I've search for a similar question but I have not found any so far, please redirect me if there's already a question about this and forgive me for my poor use of latex.

-
Thank you for the corrections @abiessu , I did not know how to insert Latex. – KirtashRiku Dec 9 '13 at 21:09
I think that you have a typo in your definition of Euclidean norm. It ought to read: either $r = 0$ or $r \ne 0$ and $N(r) < N(b)$. – Sammy Black Dec 9 '13 at 21:11
You are welcome. Note that the double-dollar-sign applies a different format than the single-dollar-sign. It did not appear (to me) that the double-DS format would be necessary for this particular question. – abiessu Dec 9 '13 at 21:11
Regarding basic $\LaTeX$ and MathJax, see this tutorial: meta.math.stackexchange.com/questions/5020/… – Sammy Black Dec 9 '13 at 21:16
Your title talks of Gaussian integers, yet the question seems to be about $\;\Bbb Z(\sqrt{-2})\;$ ...?? – DonAntonio Dec 9 '13 at 21:27

Let $a=\alpha_1+\alpha_2 i, b=\beta_1+\beta_2i$ where $\alpha_1,\alpha_2,\beta_1,\beta_2\in\Bbb Z$. Then $$\frac ab=\frac{\alpha_1+\alpha_2i}{\beta_1+\beta_2i}=\frac{(\alpha_1+\alpha_2i)(\beta_1-\beta_2i)}{N(b)}=\frac{(\alpha_1\beta_1+\alpha_2\beta_2)-(\alpha_1\beta_2-\alpha_2\beta_1)i}{N(b)}$$ By a modified form of the division algorithm on the integers, $\exists q_1,q_2,r_1,r_2\in\Bbb Z$ such that \begin{align}\alpha_1\beta_1+\alpha_2\beta_2&=N(b)q_1+r_1\\\alpha_1\beta_2-\alpha_2\beta_1&=N(b)q_2+r_2\end{align} Where $-\frac12N(b)\le r_\ell\le\frac12N(b)$.

Then our quotient is $q=q_1-q_2i$ and our remainder is $r=r_1-r_2i$. Then $\frac ab=\frac{N(b)q+r}{N(b)}$ or $$a=bq-\frac{r}{\overline b}$$ By closure, $\frac{r}{\overline b}\in\Bbb Z[i]$, so $\frac{r}{\overline b}$ is the remainder. $$N\left(\frac{r}{\overline b}\right)=N\left(\overline {b^{-1}}\right)N(r)=N(b)^{-1}N(r)$$ While $N(r)=r_1^2+r_2^2\le2\left(\frac12N(b)\right)^2=\frac12N(b)^2$. Thus the remainder satisfies $$N\left(\frac{r}{\overline b}\right)\le \frac12N(b)^{-1}N(b)^2=\frac12N(b)$$

-
Ok, as I commented to Dietrich, your answer follows the same logic as the proposition he talked about, the idea of using the division of $\mathbb{Q}[i]$ to get the structure of the remainder and verify the conditions, I'll look into it carefully and try to understand the whole proof, thank you :D – KirtashRiku Dec 10 '13 at 11:24

The norm is $N(a+bi)=a^2+b^2$, and a proof is in many books on number theory. I recommend Ireland and Rosen, "A classical Introduction to Modern Number Theory, Proposition $1.4.1$, or http://homepage.univie.ac.at/dietrich.burde/papers/burde_37_comm_alg.pdf, Proposition $1.1.12$ for $\mathbb{Z}[\sqrt{-2}]$, $\mathbb{Z}[i]$, $\mathbb{Z}[\sqrt{2}]$, and $\mathbb{Z}[\sqrt{3}]$.

-
Ok, I've read the proposition you indicate. Basically it uses the same idea as the answer @TimRatigan wrote, using the division defined in $\mathbb{Q}[i]$ to get the structure of the remainder, and then verify the condition for the remainder, I'll look into it and try to understand it thoroughly, thank you :D – KirtashRiku Dec 10 '13 at 11:17

For example : $\alpha=3+2i$ and $\beta=-10+6i$

Consider a circle of radius $\sqrt{3^2+2^2}$ by centered at $\beta$, and then move from $\alpha$ to $\beta$ !

$$\beta=\overrightarrow{AB}+\overrightarrow{BD}+\overrightarrow{DE}+\overrightarrow{Ef}+\overrightarrow{FG}+\overrightarrow{GH}+(-1-i) =$$ $$\alpha+i\alpha-\alpha+i\alpha-\alpha+i\alpha+(-1-i)=$$ $$(-1+3i)(3+2i)+(-1-i)$$

It's easy to generalize this idea to get a complete proof.
And by this way it's easy to see why $q$ and $r$ in $\beta = q\alpha+r$ are not necessarily unique. Because you can move form $\alpha$ into the circle around the $\beta$, by different ways!

-

Here is a different geometric proof. We have two Gaussian integers $a$ and $b$, and we have to prove that there exists a Gaussian integer $z$ such that

$$|az-b|<|a|$$

Well, let's consider the set $A=\{az\mid z\in\mathbb Z[i]\}$. What does it look like? Writing $z=x+yi$, we see that $az=xa+y(ai)$. But $ai$ is just $a$, rotated clockwise by $90$ degrees, so $a$ and $ai$ form a pair of orthogonal vectors of length $|a|$. We now see that our set $A$ is a square lattice, it is the set of gridpoints of a square grid of mesh size $|a|$.

We have to prove that at least one of these gridpoints is inside the open disc of radius $|a|$ centered at $b$. But in fact, something slightly stronger is true: given a square grid of mesh size $s$, any disc of radius $s$ must contain a grid point, no matter where it's placed. This is visually obvious: such a disc has diameter $2s$ whereas a square has a diameter of only $\sqrt 2 s$. There clearly isn't enough room to place a disc without overlapping a gridpoint.

-

For the ring of Gaussian integers $$\Bbb{Z}[i] = \left\{ a + bi \mid a, b \in \Bbb{Z} \right\},$$ use the norm $$N(a + bi) = a^2 + b^2.$$

-
Yes, I wanted to put this norm, but I got confused and wrote it wrong. Already corrected, thanks. – KirtashRiku Dec 10 '13 at 11:20