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

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 '19 at 15:23
• @HritRoy r/b = bq-a, and both a, b, and q are elements of Z[i]. – Alex Li Nov 19 '19 at 15:06
• Shouldn't $-\frac{r}{\overline{b}}$ be considered the remainder, since I believe the convention is that $a = bq + r$? – del42z Dec 5 '19 at 22:25
• $\frac{b}{N(b)} = \frac{1}{\bar{b}}$ so it's $a = bq + \frac{r}{\bar{b}}$ instead of minus. That said, this is one of the worst written proofs I have ever read. – AMRO Jan 3 at 21:24

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.

• Very nice proof. +1. – Anacardium Oct 23 at 19:14

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

• Uniqueness in your lemma doesn't hold unless $\leq$ is switched to $<$. Counterexample: $x = 2.5,u_1 = 2, u_2 = 3$, then $|x-u_1| = |x-u_2| = 1/2 \leq 1/2$ but $u_1 \neq u_2$. When the inequality is changed to a strict inequality it can be shown to hold via the triangle inequality and the fact that the distance between two integers cannot be less than one. You don't appear to use uniqueness in this proof though so I believe its a fairly inconsequential error. – David Reed Nov 6 '19 at 6:02
• Of course, thank you for the remark. the strict inequality appears in the proof. – Guy Fsone Nov 6 '19 at 17:39

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