I'm trying to find $\gcd(135-14i, 155+34i)$ in $\mathbb{ℤ}[i]$ with the Euclidean algorithm, but at some point I get stuck. I think it is because I don't have a systematic way of finding suitable quotients $q_i$. This is how I'm doing it:
Let $a = 155+34i, b = 135 -14i$. Then
$a = 1 · (135 -14i) + (20+48i)$, so $q_0 = 1, r_0 = 20+48i$.
$b = (1-2i) · (20+48i) + (19-22i)$, so $q_1 = 1-2i, r_1 = 19-22i$.
$r_0 = q_2 · (19-22i) + r_2$
As $\frac{r_0}{r_1} \notin ℤ[i] $, $r_2 ≠ 0$, but every $q_2$ I've tried so far to reduce the 'size' of $r_1$ has resulted in failure.
Best Answer
Since it has already been resolved in the comments, here is a somewhat more general account of what has been said there:
When working in the Gaussian integers (or any other Euclidean domain), if we have $$ a=qb+r $$ then $q$ is an approximation of $\frac ab$, which may not exist in our domain. The magnitude of $r$ (as measured by the Euclidean function, in our case the complex norm) tells us how good the approximation is.
If $\frac ab$ makes sense in some extension of our domain (in this case in the field of complex numbers), and we want $r$ to be as small as possible, we can leverage our knowledge of this larger extension to choose $q$ to be as close to $\frac ab$ as possible.