26
$\begingroup$

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.

$\endgroup$
23
$\begingroup$

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

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

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

enter image description here

$$\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!

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Rmongeca Dec 10 '13 at 11:17
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yes, I wanted to put this norm, but I got confused and wrote it wrong. Already corrected, thanks. $\endgroup$ – Rmongeca Dec 10 '13 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.