How to calculate GCD of Gaussian integers? [closed]

Question

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]$?

Answer 1

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.

Answer 2

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