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 6


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

  • $\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, 2013 at 11:24
  • $\begingroup$ Why is $\frac{r}{\bar b}\in \Bbb Z[i]$? $\endgroup$
    – Not Euler
    May 10, 2019 at 15:23
  • $\begingroup$ @HritRoy r/b = bq-a, and both a, b, and q are elements of Z[i]. $\endgroup$
    – Alex Li
    Nov 19, 2019 at 15:06
  • $\begingroup$ Shouldn't $-\frac{r}{\overline{b}}$ be considered the remainder, since I believe the convention is that $a = bq + r$? $\endgroup$
    – del42z
    Dec 5, 2019 at 22:25

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!


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


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.

  • $\begingroup$ Very nice proof. +1. $\endgroup$
    – Anacardium
    Oct 23, 2020 at 19:14
  • $\begingroup$ See also here $\endgroup$ Feb 11, 2023 at 18:25

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

  • 1
    $\begingroup$ 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. $\endgroup$
    – David Reed
    Nov 6, 2019 at 6:02
  • $\begingroup$ Of course, thank you for the remark. the strict inequality appears in the proof. $\endgroup$
    – Guy Fsone
    Nov 6, 2019 at 17:39
  • $\begingroup$ @DavidReed The lemma still fails even if you change the inequality sign into a strict one. For $x=2.5$, there is no $u\in \mathbb Z$ such that $|x-u|<1/2$. $\endgroup$
    – Sam Wong
    Dec 22, 2022 at 2:56
  • $\begingroup$ We may need to remove the adjective "unique" in the lemma. Your proof only used the existence but not the uniqueness (which we don't actually have). $\endgroup$
    – Sam Wong
    Dec 22, 2022 at 3:07
  • $\begingroup$ @DavidReed You are right. Problem fixed. The uniqueness is useless anyway. $\endgroup$
    – Guy Fsone
    Dec 22, 2022 at 15:40

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

  • $\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, 2013 at 11:17

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .