GCD computations in $\mathbb{Z}[i]$ Problem statement:

Find a generator of the ideal $(85, 1+13i)$ in $\mathbb{Z}[i]$, i.e., a GCD for $85$ and $1 + 13i$ by the Euclidean Algorithm. Do the same for the ideal $(47-13i, 53+56i).$

Can you please outline the steps, then I can practice with others.

Source: Abstract Algebra by Dummit & Foote, $\S$8.1 #7
 A: The Euclidean algorithm gives:
$$
85/(1+13i)=1/2-13i/2\approx -6i, \ 85=(-6i)(1+13i)+(7+6i),
$$
$$
(1+13i)/(7+6i)=1+i, \ 1+13i=(1+i)(7+6i),
$$
Hence the gcd is $7+6i$.
When going through the Euclidean algorithm, you divide and take a nearest (Gaussian) integer, as you would over the (rational) integers.
A: A good way to understand the Euclidean algorithm for $\mathbb{Z}[i]$ is to prove that $R:=\mathbb{Z}[i]$ is a Euclidean domain with respect to the function $\varphi(a+bi)=a^2+b^2$.
This can be done in the following way:
1) for $x\in\mathbb{Q}$ there are $y\in \mathbb{Z}$ and $z\in\mathbb{Q}$, $|z|\leq \frac 1 2$, such that $x = y+z$ (use the Gauss floor function).
2) if $a,b \in R$, then $\frac a b \in \mathbb{Q}(i)$. Write $\frac a b = y_1+z_1 + (y_2+z_2)i$, according to (1), with $y_j \in \mathbb{Z}$ and $z_j \in \mathbb{Q}, ~ |z_j|\leq \frac 1 2$.
3) Now we can write $a=qb+r$, $q:=y_1+y_2i$, $r:=b(z_1+z_2i)$. $q,r \in R$.
4) The important part is: $\varphi(r)<\varphi(b)$ (use the fact that $\varphi$ is multiplicative).
$\varphi$ works just like the absolute value in $\mathbb{Z}$. It will become smaller in every step, so the algorithm will terminate.
From this proof we gather the following algorithm: Compute the fraction $\frac{a}{b}=x+yi$ in $\mathbb{C}$. For $x,y$ choose the closest integers $\tilde x, \tilde y$. Then $a=b(\tilde x + \tilde y i) - r$ with a suitable $r$. In this way you can do a division with remainder in $\mathbb{Z}[i]$.
A: Compute $\rm\ gcd(53+56\ i,\ 47-13\ i)\ $ by using a (Euclidean) remainder sequence, e.g.
$\rm(1)\quad\quad\quad\quad 56\ i +53$
$\rm(2)\quad\quad\ -13\ i + 47$
$\rm(3)\quad\quad\quad\quad\ \ 9\ i + 40\quad\quad$ by $\rm\ \ \ \ \ \ (1) - \:i\ (2)$
$\rm(4)\quad\quad\quad\quad\ \ 7\ i + 22\quad\quad$ by $\rm\ \ \ \ i \ (2) - \:i\ (3)$
$\rm(5)\quad\quad\quad\quad\quad 5\ i + 4\ \quad\quad$ by $\rm\ - (3) + 2\ (4)\:,\ $
Note  $\rm\ p\: =\: \ 5\ i + 4\ $ is prime, since it has prime norm $= 41\:.\:$ Hence the gcd will be either $\rm\:p\:$ or $1\:,\:$ depending on if $\rm\:p\:$ divides $\rm\:q = 7\ i + 22\:;\ $ it does:  $\rm\:p\:p' = 41\:$ divides $\rm\ q\:p' = 123 - 82\ i\:.$
The first problem is much simpler, involving only two divisions - see yoyo's answer.
