How to find the GCD of $29-3i$ and $11+10i$ I'm trying to find the GCD of $29-3i$ and $11+10i$ in $Z[i]$
I know that one way I can do this, is to factorize each of the numbers and find the GCD through that. But the norms in these two numbers are fairly large so it seems like a tedious way to do it. I was wondering if there's a trick that I'm not seeing to get the GCD.
I tried subtracting the numbers and got $18 - 13i$, so we know our GCD divides that number. Here the norms are still too large, and this is definitely not a gaussian prime. Is there a way to reduce these numbers to something more manageable?
 A: Hint $\ $ The gcd divides the gcd of their norms $= (850,221) = 17 = (4-i)(4+i) = \frak p_1 \frak p_2$
$\quad {\rm mod}\,\ 17,\,\color{#c00}{i\!-\!4}\!:\ \ 29-3\color{#c00}i \equiv 29-3(\color{#c00}4)\equiv 0,\ \  11+10\color{#c00}i \equiv 11+10(\color{#c00}4)\equiv 0$
Thus the prime $\,{\frak p_1} = i - 4\,$ is a common divisor, necessarily greatest, since $17\nmid 11+10i$
A: $$\frac{29 - 3i}{11+10i} = \frac{289 - 313i}{221} = 1-i + \frac{68 - 92i}{221}   $$
confirm
$$ 68^2 + 92^2 = 13088 < 48841 = 221^2 $$
$$ \color{blue}{ (29 - 31) = (1-i)(11+10 i) + (8-2i)} $$
$$\frac{11+10i}{8-2i} = \frac{68 +102i}{68} = 1+i + \frac{34i}{68}   $$
confirm
$$ 34 < 68 $$
$$ \color{blue}{ (11+10i) = (1+i)(8-2i) + (1+4i)} $$
$$\frac{8-2i}{1+4i} = -2i   $$
confirm
$$ \color{blue}{ (8-2i) = -2i (1+4i) + 0} $$
$$  $$
$$ \color{red}{ \gcd(29 - 3i, 11+10i) = 1 + 4i} $$
$$  $$
$$\frac{29 - 3i}{1+4i} = \frac{17 - 119i}{17} = 1-7i    $$
$$  (1+4i)(1-7i) = 1 + 28 + 4i - 7i = 29 - 3i  $$
$$  $$
$$\frac{11 +10i}{1+4i} = \frac{51 - 34i}{17} = 3-2i    $$
$$  (1+4i)(3-2i) = 3 + 8 + 12i - 2i = 11 + 10i  $$
A: One more trick that you can use is the fact that $gcd(a,b)=gcd(a,b+ra)$ for any element $r$, which is helpful to reduce the number you work with. For example, in your case you can use
$$gcd(29-3i,11+10i)=gcd(29-3i+i(11+10i),11+10i)=gcd(19+8i,11+10i) \\
=gcd(19+8i-(11+10i),11+10i)=gcd(8-2i,11+10i)$$
You can stop here and use the prime decomposition $8-2i=2(4-i)=i(1-i)^2(4-i)$ and check which of these divide $11+10i$. You can also continue with this method until you get "smaller" numbers, or use the norms method as in Bill Dubuque's answer.
