# GCD of Gaussian Integers $\text{gcd}(4, 36+18i)$

I have to compute $$\text{gcd}(4, 36+18i)$$. I computed the norms: $$16$$ and $$1620$$.

I am sure $$2$$ is the gcd. Is there any method to prove $$2$$ is the gcd, other than using the Euclidean Algorithm (which I don't know how to use)?

Or if it couldn't be proved directly, can you please explain me how to compute it using Euclidean Algorithm? I've searched here but I really don't understand the steps.

Thank you!

The $$\gcd$$ of two numbers is the same if you subtract a multiple of one from the other.

In other words, $$\gcd(a,b) = \gcd(a,b-ak)$$ for any $$k$$.

So here, notice that we can immediately simplify the expression by subtracting $$36$$ from the second term -- $$\gcd(4,36+18i)=\gcd(4,18i).$$

Next, we subtract $$16i$$ from the latter term, remembering that this is a multiple of $$4$$ in the Gaussian integers.

$$\gcd(4,18i)=\gcd(4,2i).$$

Finally, we subtract $$4$$ from the LHS, as $$4=2i\times(-2i)$$ is a multiple of $$2i$$:

$$\gcd(4,2i)=\gcd(0,2i)$$

Since the $$\gcd$$ of $$0$$ and anything is the latter, the answer is $$2i$$. Note that this only differs from $$2$$ by a unit, and it's conventional to give the $$\gcd$$ in simplest form, so $$2$$ is the simplified answer.

Another way to approach the question is to full factorise both sides, noting that $$\mathbb Z[i]$$ is a UFD -- in other words,

$$4=(1+i)^2(1-i)^2, 36+18i=(1+i)(1-i)3^2(2+i)$$ and then just picking the common factors (remembering that multiples of units is fine!), $$(1+i)(1-i)=2$$

$$4=2×2; 36+18i=2×9(2+i)$$.

So, $$\text{gcd}(4, 36+19i)=2\text{gcd}(2, 2+i) =2$$.

$$|2+i|^2=5$$, which is a prime. Hence, $$2+i$$, can't be factorised. Also, $$|2|<|2+i| \rightarrow 2+i \nmid 2$$

$$\text{gcd}(2, 2+i)=1 \rightarrow \text{gcd}(4, 36+18i)=2$$.