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 and .

We know that 13 divides 39 and .

Similarily

thus .

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