How to calculate GCD of Gaussian integers? [closed]

Let $\mathbb Z [i] =\{a+bi: a,b \in \mathbb Z\}$.

What is the gcd of $11+7i$ and $18-i$ in $\mathbb Z [i]$?

An excellent general approach is to use a Gaussian version of the Euclidean Algorithm. We give a calculation using that towards the end of this post.
But with "small" Gaussian integers, other approaches may work quickly.

For example, we can look for common factors using the norms. Observe that $\|11+7i\|=170$ and $\|18-i\|=325$.

Any common divisor of our numbers must divide the ordinary greatest common divisor of their norms, so must divide $5$. We know that in the Gaussian integers, $5$ has the prime factorization $5=(2+i)(2-i)$. Let's see whether $2+i$ divides both of our numbers.

Calculate: $$\frac{11+7i}{2+i}=\frac{(11+7i)(2-i)}{(2+i)(2-i)}=\frac{29+3i}{5}.$$ We conclude that $2+i$ does not divide $11+7i$. (It follows that $2-i$ must divide $11+7i$, but we won't need that.)

Now let's check whether this prime divisor $2-i$ of $11+7i$ divides $18-i$: $$\frac{18-i}{2-i}=\frac{(18+i)(2+i)}{(2-i)(2+i)}=\frac{37+16i}{5}.$$ So $2-i$ does not divide $18-i$. Thus nothing other than a unit divides both of our numbers.

We conclude that $1$ is a greatest common divisor of $11+7i$ and $18-i$. (So are its associates $-1$ and $\pm i$.)

Comment: We could have saved some time. For example, any common divisor of $11+7i$ and $18-i$ must divide any linear combination of them, such as $1\cdot(11+7i)+7\cdot (18-i)$. This is $137$. So any common divisor must divide the norm of $11+7i$, which is $170$, and must also divide $137$. These numbers are relatively prime in the ordinary sense, so they are also relatively prime in the Gaussian sense. We could have dispensed with the divisions by $2+i$ and $2-i$ entirely!

The Euclidean Algorithm: We just look at our particular problem, which is too small to give a full illustration of the process. The idea is to imitate the ordinary process of division with remainder. Divide $18-i$, the number with larger norm, by $11+7i$. After a little calculation this simplifies to $\dfrac{191-137i}{170}$. Now pick the nearest Gaussian integer to this. It is $1-i$ and is our candidate for "quotient."

Calculate $(18-i)-(11+7i)(1-i)$: we get $3i$. Thus $$18-i=(11+7i)(1-i) +3i.$$ Note that as in the ordinary integer case, the gcd of $18-i$ and $11+7i$ is the same as the gcd of $11+7i$ and the "remainder" $3i$. It is obvious that this gcd is $1$. But if we decide not to notice, we can apply the division procedure mechanically again. We have $\dfrac{11+7i}{3i}=(7-11i)/3$. The nearest Gaussian integer is $2-4i$. So $$11+7i=(3i)(2-4i) -1 +i.$$ Thus our gcd is the same as the gcd of $3i$ and $-1+i$. Let's continue. Calculate $3i/(-1+i)$, find the nearest Gaussian integer. There are several, including $1-i$. We get $3i=(-1+i)(1-i)+i$. The next remainder will be $0$ since $i$ is a unit. Our computation has given $i$ as a gcd. No thinking whatsoever.

One nice thing about the Euclidean Algorithm approach is that we don't have to do any factoring (for large integers, that's hard). The calculations don't look like much fun, and they aren't, but it's the sort of thing computers love.

• I appreciate your efforts so far, so hopefully my grateful request for a demonstration of the Euclidian Algorithm will not be offensive... (+1) – The Chaz 2.0 Nov 15 '11 at 16:18
• @The Chaz: You reminded me that I really should have mentioned something of the Euclidean Algorithm beside the name. – André Nicolas Nov 15 '11 at 17:47
• Indeed, many people know (supposedly) that the EA should be used, but fail to demonstrate its use clearly. Your work is helpful and encouraging to me, since I kept doubting my work at the r = -3i step. – The Chaz 2.0 Nov 15 '11 at 18:36
• The norm of the gcd has to be $5$ or $1$. Why can't the gcd be $\pm 3\pm 4i$ or $\pm 4\pm 3i$? – fierydemon Oct 11 '13 at 9:15
• The norm of these is $25$. Recall that norm in number theory is different from complex variables norm. – André Nicolas Oct 11 '13 at 14:03

HINT $\$ Modulo the gcd: $\ 11\: =\: {-}7\ i\$ and $\ 18\: =\: i\:,\$ therefore

$$11\ =\ (11-18)\ i\ =\ (-7\ i\:-\:i)\ i\ =\ 8\ \ \Rightarrow\ \ 3\: =\: 0\ \ \Rightarrow\ \ i\: =\: 6\cdot 3\: =\: 0\ \ \Rightarrow\ \ 1\: =\: 0$$

• I got lost somewhere between "Modulo.." and "1=0"... – The Chaz 2.0 Nov 16 '11 at 20:08
• @The precisely where did you get lost? – Gone Nov 16 '11 at 20:18
• Well apparently (and I'm sure I should know this!), $11+7i=0$ modulo the GCD. So after some manipulations, we find that $3=1=0$. How does that give us the GCD? Could you do an example where the GCD isn't a unit? – The Chaz 2.0 Nov 16 '11 at 20:22
• @The $\rm\ d\ |\ a-b\ \iff\ a\equiv b\pmod{d}\:.\$ Thus $\rm\ 1\equiv 0\pmod d\ \Rightarrow\ d\ |\ 1\:.$ – Gone Nov 16 '11 at 20:26