Greateat common divisor in Z[i]

Question

How do i use the euclidean algorithm to compute the greatest common divisor of two elements in Z[i]?

Answer 1

So, let's find $\gcd(11+17i,1+13i)$. We clearly see that $11+17i$ has the greater norm, so we can start by subtracting from that. What multiple should we subtract? We could figure that out by division (which, admittedly, is some work), but we see geometrically (which is much easier that division, and while not optimal, more than good enough) that since $11+17i$ is somewhere below the $45^\circ$ line, and $1+13i$ is close to the imaginary axis, $(1-i)$ shouldn't be too far off: $$ \gcd(11+17i,1+13i)=\gcd(11+17i-(1-i)(1+13i),1+13i)\\ =\gcd(-3+5i,1+13i)\\=\gcd(5+3i,1+13i) $$ where I've used that $\gcd(a,b)=\gcd(-ia,b)$. This time, $1+13i$ has the largest norm, so we find a multiple of $5+3i$ which is close to it. This time we want to turn $5+3i$ a bit more than $45^\circ$. Also, $1^2+13^2=170=5\cdot34=5\cdot(5^2+3^2)$ means that $1+2i$ is pretty good (since $1+2^2=5$): $$ \gcd(5+3i,1+13i)=\gcd(5+3i,1+13i-(1+2i)(5+3i))\\ =\gcd(5+3i,2) $$ Now we can finish directly: $$ =\gcd(5+3i-(2+2i)\cdot2,2)\\ =\gcd(1-i,2)\\ =\gcd(1-i,2-(1+i)(1-i))\\ =\gcd(1-i,0)=1-i $$