How can I find $\gcd(16+7i,10-5i)$ by using the Euclidean algorithm?

Question

In Gaussian integers ring $\mathbb{Z}[i]$, I wanna get a greatest common divisor of $16+7i$ and $10-5i$ using the Euclidean algorithm.

I used an Euclidean norm $N$ as $N(a+bi) = a^2+b^2 $ for $a+bi \in \mathbb{Z}[i]$.

Specifically, the more i use an Euclidean algorithm, the more a norm of remainder does increase.

I do not know how to solve it.

Answer 1

$\frac {16+7i}{10-5i}= \frac {16+7i}{10-5i}\frac {10+5i}{10+5i}= \frac {125+150i}{125}\approx 1+i $

$16+7i =(10-5i)(1+i)+(1+2i) $

$\frac {10-5i}{1+2i} =\frac {10-5i}{1+2i}\frac {1-2i}{1-2i}=-25i/5=-5i $ exactly.

So gcd is $1+2i $.

$10-5i=-5i(1+2i)$

and $(16+7i)/(1+2i) =$

$(16+7i)(1-2i)/(1+2i)(1-2i)$

$=(30-25i)/5=6-5i $

Answer 2

We can use a version of the Euclidean algorithm as follows:

Since $N(16+7i) > N(10-5i)$ we may divide in $\mathbb{Q}(i)$ and round to the nearest Gaussian integer to obtain the minimum-norm remainder:

$$\frac{16+7i}{10-5i} = \frac{5 + 6i}{5} = (1+i) + \frac{1}{5}i$$ $$16+7i = (1+i)(10-5i) + (1 + 2i)$$ so $\gcd(16+7i,10-5i) = \gcd(10-5i,1+2i)$. Repeating this until you hit a remainder of $0$, you will find that a gcd is $1 + 2i$.

Answer 3

(The following was too long for a comment, yet it is not an answer proper since it doesn't use the Euclidian algorithm as asked.)

In this particular case, it may be easier to simply factor the 2 numbers in Gaussian primes and figure out the $\gcd$ from the prime factorization.

• $10-5i = 5\cdot(2 - i) = (2+i)(2-i) \cdot (2-i) = (2+i) \cdot (2-i)^2$. This factorization can be obtained pretty much by inspection, and $5=(2+i)(2-i)$ is one of the first taught and best known examples of factorization in Gaussian integers.

• $16+7i=(2-i)(5+6i)$. To find this factorization, first note that $||16+7i||=305=5 \cdot 61$ and any factors must divide the norm. We already know that $5=(2+i)(2-i)$. To guess the factors of $61$ it's enough to notice that $61=5^2 + 6^2$ (or, for more general methods, see this for example). Choosing one matching pair among the factors of $5$ and $61$, respectively, gives the respective factorization.

Comparing the factorizations above, it follows that $\gcd(16+7i, 10-5i)=2-i$. Of course, the $\gcd$ is only defined up to units, and $2-i=-i \cdot(1+2i)$ so the $1+2i$ posted in the other answers is equally correct.