# 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) Nov 15, 2011 at 16:18
• @The Chaz: You reminded me that I really should have mentioned something of the Euclidean Algorithm beside the name. Nov 15, 2011 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. Nov 15, 2011 at 18:36
• The norm of these is $25$. Recall that norm in number theory is different from complex variables norm. Oct 11, 2013 at 14:03
• Let me ask you one question: Why do you pick the nearest gaussian integer? I know that the nearest is $1-i.$ But why do you pick the nearest? I can get this point :(
– ZFR
Jun 1, 2018 at 19:54

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"... Nov 16, 2011 at 20:08
• @The precisely where did you get lost? Nov 16, 2011 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? Nov 16, 2011 at 20:22
• @The $\rm\ d\ |\ a-b\ \iff\ a\equiv b\pmod{d}\:.\$ Thus $\rm\ 1\equiv 0\pmod d\ \Rightarrow\ d\ |\ 1\:.$ Nov 16, 2011 at 20:26