Calculating the gcd of $6-7i$ and $2-9i$

Question

I need help in calculating the gcd of complex numbers $6-7i$ and $2-9i$. The problem is I don't know the algorithm for complex numbers and I've read a few posts related to this but it seem like it doesn't work on my case, or I don't totally understand the solutions. Can someone help me?

Answer 1

$\begin{align}\gcd(6-7i,2-9i)&=\gcd(6-7i,4+2i) & \text{subtract} \\&=\gcd(6-7i,2+i) & \text{divide by 2} \\&=\gcd(4-8i,2+i) & \text{subtract} \\&=\gcd(1-2i,2+i) & \text{divide by 4} \\&=(2+i)\times\gcd(-i,1) & \text{factor} \\&=2+i\end{align}$

---

Some justifications:

We subtract so as to reduce the norm in $\mathbb Z[i]$ i.e. $N(a+ib)=a^2+b^2$ of the new number in the gcd, since the norm is positive, we ensure the convergence of the algorithm as it cannot decrease eternally. This is exactly the step we would use in Euclidean division algorithm.

There is a shortcut though regarding division by $2=(1+i)(1-i)$.

Note that $(x+iy)=(1\pm i)(a+ib)=(a\mp b)+i(b\pm a)$, therefore we need $\frac{x\pm y}2$ to be integer, to have $x+iy$ divisible by one of the factors of $2$, i.e. $x,y$ should have the same parity.

Here $6-7i$ and $2+i$ have coordinates of different parity so they do not have factors in common with $2$ and we can divide as mentionned in the step by step process.