Compute the gcd of the following numbers.

Question

How to find the $\gcd(3+2i,1+i)$?

Working modulo the gcd we have: $$3=-2i,1=-i$$ $$\implies 3=(3-1)(-i)=(-2i+i)(-i)=1$$ $$\implies 2=0$$ $$\implies 3=0$$ $$\implies 1=3-2=0$$ So $\gcd(3+2i,1+i)=1.$

Is this correct?

Answer 1

According to Bezout lemma since $$(3+2i)+(-2)(1+i)=1$$we have that $\gcd(3+2i,1+i)=1$

Answer 2

Use that $\gcd(a,b)=\gcd(a,a-kb)$ then

$$\gcd(3+2i,1+i)=\gcd(3+2i-2-2i,1+i)=\gcd(1,1+i)=1$$

Answer 3

Yet another method. The norms of your two Gaussian integers are $13$ and $2$, which are rational primes. Hence each is a prime. Since they are different primes, they are relatively prime.

Granted this is not as elementary as using the Euclidean algorithm or one of the tricks in the other answers.