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

## 6 Answers

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 – Rmongeca Dec 10 '13 at 11:24
• Why is $\frac{r}{\bar b}\in \Bbb Z[i]$? – Hrit Roy May 10 at 15:23

Think about this problem geometrically:

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.

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 – Rmongeca Dec 10 '13 at 11:17

## Here is an Elegant Proof

It is well known that $(\mathbb{Z}[i]=\{a+bi \mid a,b \in \mathbb{Z}\},+,\cdot )$ in integral domain. Consider, $N:\Bbb Z[i] \to \Bbb N$ defined by $$\color{blue}{N(z) = z\bar{z}=|z|^2 =a^2+b^2~~~ \text{for}~~z= a+ib.}$$ We want to show that $N$ define an integral function for our Ring $\Bbb Z[i].$

• $N(0) = 0$ and $N(z) \gt 0$ for $z\neq 0.$
• $z,w,q\in \Bbb Z[i]\setminus\{0\}$ such that $z=wq$ i.e $w|z$ we have $N(q) \gt 0 \implies N(q) \ge 1$ since $N(q) \in \Bbb N$ Then, $$N(w) \le N(w)N(q) = |w|^2|q|^2 = |wq|^2 =N(wq) =N(z)$$

So, if $w|z$ then $N(w) \le N(z)$.

• Now we want to show the Euclidean division property. we use the following

Lemma: for every $x\in \Bbb R$ there exists a unique $u\in \Bbb Z$ such that $\color{blue}{ |x-u|\le \frac{1}{2}}$

Proof: Let denote by $\lfloor \ell \rfloor$ is the floor of $\ell$. Then We know that $$\lfloor x+\frac{1}{2} \rfloor\le x+\frac{1}{2} \lt \lfloor x+\frac{1}{2}\rfloor +1\implies-\frac{1}{2}\le x -\lfloor x+\frac{1}{2} \rfloor\lt \frac{1}{2}$$ Taking $u= \lfloor x+\frac{1}{2}$ The unicity follows from the unicity follows from the unicity of the floor.

Now let $z,w\in \Bbb Z[i]\setminus\{0\}$ then $\frac{z}{w}$ can be written as

$$\color{red}{ \frac{z}{w}= x+iy :=\frac{z\bar{w}}{|w|^2}~~~~~ \text{with }~~~x,y\in \Bbb Q.}$$

From the Lemma there exist $u,v\in \Bbb Z$ such that $\color{blue}{ |x-u|\le \frac{1}{2}~~~~\text{and}~~~|y-v|\le \frac{1}{2}}.$ Then,we can write $$\color{red}{ \frac{z}{w}= x+iy = q +t~~~~~ \text{with }~~~q\in \Bbb Z, t\in \Bbb Q.}$$ Where, $\color{blue}{q= u+iv ~~\text{and}~~~t =x-u+i(y-v)}$. Then we have, $$\color{blue}{ z= qw +tw \implies r:= tw = z-qw \in \Bbb Z.}$$

Hence $\color{red}{z= qw +r}$ with $q,r \in \Bbb Z$ with $r=tw$ where we have, $$\color{blue}{ t =x-u+i(y-v),~~~|x-u|\le \frac{1}{2}~~~~\text{and}~~~|y-v|\le \frac{1}{2}}$$

Which means that, $$N(t) =|x-u|^2+|y-v|^2\le \frac{1}{2}$$

Therefore, $$N(r) =N(tw) =N(t)N(w) \le \frac12N(w) \lt N(w)$$

That is $$\color{red}{N(r) \lt N(w).}$$

conclusion N is divivion for the Ring $\Bbb Z[i].$

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. – Rmongeca Dec 10 '13 at 11:20