One of my favourite factorising tricks ((I learned about it from Hillarie Orman and Richard Schroeppel, who probably learned it from Euler; my take on it is necessarily less sophisticated than theirs because they are several leagues cleverer than me.)) is the sum-of-two-squares-in-two-ways one.

For example, $221 = 10^2 + 11^2 = 5^2 + 14^2$. (Now, if you’re sharp, you might spot that $221 = 15^2 - 2^2$, so it’s $13 \times 17$. But we’re doing this another way, ok?)

Instead, we’re going to go to the Gaussian integers – complex numbers with integer coefficients – and factorise $10^2 + 11^2$ as $(10+11i)(10-11i)$ and $5^2 + 14^2$ as $(5 + 14i)(5-14i)$.

If we’re just after a factorisation, we can say that, for example, $(10+11i)(5+14i)$ must be a factor of $221^2$. That expands to $-104+195i$, or $13(-8 + 15i)$ – so 13 is a factor of $221^2$. Thirteen is prime, so it must be a factor of 221 itself.

But I wondered: can I find the highest common factor of $10+11i$ and $5+14i$? How would I do that?

Euler, Gauss and Euclid in the same post, oh my.

With the traditional, integer-based Euclidean algorithm, you start with two numbers (let’s say $a$ and $b$, with $a>b$) and write $a$ as a multiple of $b$ and a remainder – there’s a unique way to write $a = qb + r$ with $q$ an integer and $0 \le r \lt b$.

You then repeat the process using $b$ and $r$ as your numbers, until you hit a remainder of zero – in which case, your current “$b$” is the highest common factor. For example, you might not have spotted that 104 and 195 were both multiples of 13. Euclid would say:

  • $195 = 1 \times 104 + 91$
  • $104 = 1 \times 91 + 13$
  • $91 = 7 \times 13$ with no remainder, so 13 is the HCF of 195 and 104.

There is a problem in applying this to Gaussian integers, though: they’re not ordered. Is $10+11i$ larger or smaller than $5+14i$? The answer to that is “no”! If we want to Euclid up this whole Gaussian thing, we need to come up with another rule.

Now we start with two Gaussian integers $g$ and $h$, and write $g$ as a multiple of $h$ and a remainder, and write $g = qh + r$ such that $r$ is as small as possible in magnitude. There is not necessarily a unique pair $(q,r)$ in the Gaussians that satisfy this, but when there’s a tie, any of them will do.

So let’s try it with $10+ 11i$ and $5+14i$!

  • $10+11i = 1\times (5+14i) + (5-3i)$
  • $5+14i$… we have a choice here. I’ve gone for $5+14i = 2i \times (5-3i) + (-1 + 4i)$. Try a different one! See if it works!
  • $5-3i = -(1+i)\times (-1+4i)$ with no remainder – so $-1 + 4i$ is a common factor.

By a symmetry argument, you can also find that $-1 -4i$ is a common factor of $10-11i$ and $5-14i$. That means that $(-1-4i)(-1+4i)$, which is 17, is a factor of 221.

This is all a bit sledgehammer-and-nut – in particular, in finding the nearest Gaussian integer, I found myself saying “gosh, there are a lot of multiples of 17 flying around” – but I thought it was an interesting extention to a classical algortihm.