Suppose I wanted to find the GCD between a complex integer z and an integer. How would I go about doing this?

For instance, suppose $\displaystyle z = 6 + 4i$ and $\displaystyle I = 39$.

We know that 13 divides 39 and $\displaystyle 13 = (3 + 2i) \cdot (3 - 2i)$.

Similarily $\displaystyle 6 + 4i = 2 \cdot (3 + 2i)$

thus $\displaystyle gcd(z,I) = 3 + 2i$.

How the heck would I figure this out though without having to first factor z and I separately into they're irreducible/prime factors?