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

Question

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!

Answer 1

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$$

Answer 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$.