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$.
 A: 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)$.
