# An algorithm for Gaussian integers

Question : Let $i^2=-1$. If a pair $(a+bi, c+di) (a,b,c,d\in\mathbb Z, a\not\equiv b, c\not\equiv d\ \text{(mod 2)})$ such that $a+bi$ and $c+di$ are relatively prime is given, then can we say that repeating the following operation leads $(1,1)$ in finitely many steps?

Suppose that $a+bi$ and $c+di$ are relatively prime if and only if $a+bi$ and $c+di$ don't have any common divisor except for $\pm 1,\pm i$.

Operation : If a pair $(a+bi, c+di)$ is given (we may suppose that $N(a+bi)\le N(c+di)$ where $N(a+bi)=a^2+b^2$), the next pair is defined as $(a+bi, (c+di)+\epsilon (1+i)(a+bi))$ with an appropriate choice of $\epsilon=\pm 1,\pm i$.

Example : Noting that $3+2i$ and $4+i$ are relatively prime since each of them is a prime, we know that the pair $(3+2i,4+i)$ satisfies the condition above. Noting that $N(3+2i)\le N(4+i)$, \begin{align} (3+2i,4+i) & \rightarrow (3+2i,-1+2i)\ \ \ \ (\because \ \ (4+i)+(+i)(1+i)(3+2i)=-1+2i)\\ & \rightarrow (2-i, -1+2i)\ \ \ \ (\because \ \ (3+2i)+(+i)(1+i)(-1+2i)=2-i)\\ & \rightarrow (2-i,-i)\ \ \ \ (\because \ \ (-1+2i)+(-i)(1+i)(2-i)=-i)\\ & \rightarrow (1,-i)\ \ \ \ (\because \ \ (2-i)+(-1)(1+i)(-i)=1)\\ & \rightarrow (1,1)\ \ \ \ (\because \ \ (-i)+(+1)(1+i)(+1)=1). \end{align}

Motivation : I've been looking for a similar algorithm for Gaussian integers $\mathbb Z[i]$ as Euclidean Algorithm for rational integers $\mathbb Z$. Then, I reached the operation above. However, I'm facing difficulty for proving or disproving that repeating the operation leads $(1,1)$ for any pair. Can anyone help?

Edit 1 : As Gerry Myerson pointed out, the Euclidean algorithm works fine in the Gaussian integers.

Edit 2 : I think if we can prove the following lemma, then we can say that repeating the operation leads $(1,1)$ in finitely many steps. However, I'm facing difficulty for proving the lemma. Can anyone help?

Lemma : If a pair $(a+bi, c+di) (a,b,c,d\in\mathbb Z, a\not\equiv b, c\not\equiv d\ \text{(mod 2)})$ such that $a+bi$ and $c+di$ are relatively prime with $N(a+bi)\le N(c+di)$ is given , then we can get $$N(c+di+\epsilon (1+i)(a+bi))\lt N(c+di)$$ with an appropriate choice of $\epsilon=\pm 1,\pm i$.

• The Euclidean algorithm works just fine in the Gaussian integers. Given $a,b$, $b\ne0$, there exist $q,r$ with $a=bq+r$ and norm of $r$ less than norm of $b$. – Gerry Myerson Dec 13 '13 at 11:20
• @GerryMyerson: Thank you very much for pointing it out. The algorithm of this question might be another form of the Euclidean algorithm, but I don't have any good idea. – mathlove Dec 13 '13 at 18:10
• Is it $a+b$ or $a+bi$ in your lemma ? – Ewan Delanoy Dec 15 '13 at 15:40
• @EwanDelanoy: Thank you very much for pointing it out. $a+bi$ is correct. – mathlove Dec 15 '13 at 15:42
• Your lemma is not correct if $N(a+bi)=N(c+di)$. For example let $a=b=c=d=1$, so I think it should be $N(a+bi)< N(c+di)$ or change this: $N(c+di+\epsilon (1+i)(a+bi))\leq N(c+di)$ – Farshad Nahangi Dec 15 '13 at 17:12

We need some lemmas before concentrating on what matters. We shall prove the norm is always decreasing and is always nonzero in your situation. This would imply your claim if we can guarantee the algorithm never "chokes", i.e. we rule out the equality part. This can be made with additional informations.

Lemma. Let $t=1+i$. For every complex numbers $m,n$ it is possible to find a linear combination $\alpha$ of $\varepsilon t$ such that $$N(n-\alpha m)\leqslant N(m).$$

To prove the lemma, imagine the complex plane, the number $m$ and the number $n$, possibly very far away from $m$. Write the linear combinations of the numbers $mt, mit, -mt, -mit$. They cover the complex plane with squares of sides $|m|\sqrt{2}$. By the pigeonhole principle, $n$ is at most $|m|$ from another complex number, say, $\alpha m$. This implies $N(n-\alpha m)\leqslant N(m)$, as we wanted.

Lemma. If $a$ and $b$ are relatively prime, $N(a-\alpha b)\lt N(b)$.

Suppose $N(a-\alpha b)=N(b)$. Following the idea of the first lemma, it follows that $a$ is in the center of a square of the covering we created. Now, consider the covering of all gaussian multiples of $b$. It contains all centers and all vertices, and, then, $a=kb$, contradiction.

Lemma. The norm $N(a-\alpha b)$ is always nonzero.

Suppose it is zero. Therefore, $a=\alpha b$, so they aren't relatively prime, contradiction.

Therefore, we proved the norm is decreasing and is always nonzero. This implies your algorithm always terminates in $(1,1)$.

• Thank you very much! I have two questions. 1)About the proof of $n=km\iff N(n-\alpha m)=0$. $\Leftarrow$ is easy, but in order prove $\Rightarrow$, we need to prove that $k$ is a linear combination of $\epsilon (1+i)$, don't we? I would like you to show the proof because I'm facing difficutly. (continued) – mathlove Dec 17 '13 at 5:53
• (part 2)2)About the second lemma, you use $N(a−\alpha b)=N(b)\iff N(n−\alpha m)=N(m)$, don't you? Then, I understand your second sentence "Following ⋯ created". But I can't understand the following sentences. Especially, "It contains all centers and all vertices". I don't know why you can say so. Could you please explain more about this? – mathlove Dec 17 '13 at 6:19
• @mathlove for the first question: this situation does not happen in the restrictions you wrote, so this part is unnecessary, I'm sorry. Here's why: in order to prove $k=\gamma (1+i)$, we need at least $N(k)=N(\gamma)N(1+i)=2N(\gamma).$ This would imply $N(n)$ is even, but it isn't, since exactly one of $\Re(n)$ or $\Im(n)$ is odd. In fact, what I wrote isn't true in general, I apologize. However, it doesn't break the argument in any way. – Ian Mateus Dec 17 '13 at 14:24
• @mathlove for the second question: drawing helps a lot. You say you understand $n$ is in the center of a square. Call two opposite vertices $A=\alpha (1+i)b$ and $C=\gamma(1+i)b$. Therefore, $a=\frac{A+C}{2}$. However, because they are opposite vertices, we have $$C-A=2\varepsilon b\implies C=A+2\varepsilon b\implies a=A+\varepsilon b\implies b\mid a.$$ This contradicts the fact that they are relatively prime. – Ian Mateus Dec 17 '13 at 14:49
• Thanks. I have two questions, again:). 1)I think $n=\frac{A+C}{2}$ instead of $a=\frac{A+C}{2}$ since $n$ is in the center. Am I mistaken? 2)Why do you get $C-A=2\epsilon b$? I get $2\epsilon$. Maybe am I drawing another figure? I'm thinking a figure made of the linear combinations of the numbers $mt,mit,−mt,−mit$. I'm afraid that you're thinking of a different figure. – mathlove Dec 17 '13 at 15:09