Finding the GCD of two Gaussian integers How do you calculate the GCD of $6-17i$ and $18+i$ in $\Bbb Z [i]$?
 A: Look at the norms:
$$N(6+17i)=36+289=325,\; N(18+i)=324+1=325$$
So the primes dividing each have to divide the rational primes $5, 13$ since $325=5^2\cdot 13$.
These are:
$$(2+i),\, (2-i),\, (3+2i),\, (3-2i)$$
From there we see that $5, 13$ do not divide any of the real or imaginary parts, so that none of these factors appear with their conjugates, so since $25$ divides both norms, you know that they have a factor of either $(2+i)^2=3+4i$ or $(2-i)^2=3-4i$ and exactly one of $(3+2i)$ or $(3-2i)$.
Then from there you can try dividing the original numbers by each possible irreducible factor to get the proper factorization, then the gcd is easy from there.
Ex. 1

$${6+17i\over 2-i}={(6+17i)(2+i)\over 5}=-1+8i$$

Hence $(2-i)^2\lVert (6+7i)$ where $\lVert$ means "exactly divides."
If you don't believe me you can check directly.
Ex. 1'

$${6+17i\over (2-i)^2}={6+17i\over 3-4i}=-2+3i$$

as claimed.
Similarly we have
Ex. 2

$${6+17i\over 3+2i}={(6+17i)(3-2i)\over 13}={1\over 13}(-16+63i)$$

which is also a Gaußian integer, so we conclude that $(3+2i)\lVert (6+17i)$ since one of them has to.
If you're a bit skeptical that I can conclude that so easily, you can check for yourself with
Ex. 2'

$${6+17i\over 3+2i}=4+3i$$

verifying the claim.
Repeat the same procedure for $18+i$, testing just with $(2-i)$ and $(3+2i)$. If the first one works out nicely, you get $(2-i)^2\lVert(18+i)$, if not $(2+i)^2\lvert (18+i)$, either way you get an answer. Same for the second one. Then just compare common factors.
A: You can use the Euclidean algorithm in $\Bbb Z[i]$: divide one number by the other to obtain a quotient and remainder, then repeat with the previous divisor and remainder, and so on.  The quotient must of course be an element of $\Bbb Z[i]$, and the remainder must have norm less than that of the divisor: to ensure this we'll take the quotient to be the exact quotient, with real and imaginary parts rounded to the nearest integer.  In this case we have
$$\frac{18+i}{6-17i}=\frac{91+312i}{325}$$
and so we take the first quotient to be $i$.  Thus
$$\eqalign{
  18+i&=(i)(6-17i)+(1-5i)\cr
  6-17i&=(\cdots)(1-5i)+(\cdots)\cr
  1-5i&=(\cdots)(\cdots)+(\cdots)\cr}$$
and so on.  See if you can finish this.
