1
$\begingroup$

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!

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.