<s>[INST] Find the GCD of the following values in $Z[i]$ I'm trying to find the GCD of $4+22i$ and $17+i$ in $Z[i]$. I started by using Euclid's and did the following steps:
$4 + 22i = (17 + i) \cdot i + (5 + 5i)$
$17 + i = (5 + 5i) \cdot (1 - i) + (7 + i)$
Now when I try to divide $5 + 5i$ by $7 + i$ I get
$\frac{5 + 5i}{7 + i} = \frac{5 + 5i}{7 + i} \cdot \frac{7 - i}{7 - i} = \frac{40}{50} + \frac{30i}{50}$
I'm not sure where to go from here (or if I've made a mistake along the way) because this would seem to give a quotient of $0$ which will cause the algorithm to loop.
 [/INST] Write $z=4+22i$ and $w=17+i$. Now,
$$\frac{z}{w}=\frac{4+22i}{17+i}\cdot \frac{17-i}{17-i}=\frac{9}{29}+\frac{37}{29}i.$$ The closest integers to $\frac{9}{29}$ and $\frac{37}{29}$ are $0$ and $1$, respectively. Write $q_1=0+1i=i.$ 
Then
$$r_1=(4+22i)-(17+i)(i)=5+5i.$$
Now,
$$\frac{17+i}{r_1}=\frac{17+i}{5+5i}\cdot \frac{5-5i}{5-5i}=\frac{9}{5}+\frac{-8}{5}i.$$ The closest integers to $\frac{9}{5}$ and $\frac{-8}{5}$ are $2$ and $-2$, respectively. Write $q_2=2-2i$. Then
$$r_2=(17+i)-r_1q_2=(17+i)-(5+5i)(2-2i)=-3+i.$$ 
Now,
$$\frac{r_1}{r_2}=\frac{5+5i}{-3+i}\cdot\frac{-3-i}{-3-i}=-1-2i=q_3\in\Bbb{Z}[i].$$
We have shown that
$$\begin{align}
z&=wq_1+r_1\\
w&=r_1q_2+r_2\\
r_1&=r_2q_3+0.
\end{align}$$
The last nonzero remainder is $r_2$ and hence (using the euclidean algorithm) the required $\gcd$ is $r_2=-3+i$.
</s>