How to find the GCD of $29-3i$ and $11+10i$

Question

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?

Answer 1

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$

Answer 2

$$\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 $$

Answer 3

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.