Finding the GCD of two Gaussian integers

Question

How do you calculate the GCD of $6-17i$ and $18+i$ in $\Bbb Z [i]$?

Answer 1

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.

Answer 2

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.