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

Question

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.

Answer 1

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

Answer 2

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!

Answer 3

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.

Answer 4

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$ defines 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|<\frac{1}{2}}$ or $\color{blue}{x-u= -\frac12}$.

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}\rfloor$, then either $x-u= -\frac12$ or $|x-u|<\frac12$.

The uniqueness follows from the uniqueness 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[i], t\in \Bbb Q[i].}$$ 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[i].}$$

Hence $\color{red}{z= qw +r}$ with $q,r \in \Bbb Z[i]$ 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].$

Answer 5

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

Answer 6

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