You know how things escalate on Twitter sometimes? Somebody makes an off-hand comment wondering whether a number is prime and suddenly you’re neck deep in number theory?

This is the story of how you might factorise 842,909 on paper.

In fact, it’s the second part of the story; we join it after having discovered that 842,909 can be written as $850^2 + 347^2$ and as $875^2 + 278^2$.

The Gaussian integers

If those +s were -s, we’d be laughing: we could simply apply the difference of two squares to either and boom! A factorisation. However, we don’t have that - at least, not in the positive integers.

However, in the Gaussian integers, we do. Gaussian integers are the extension of the integers into complex numbers: they’re complex numbers of the form $a+b\i$ where both $a$ and $b$ are integers.

Gaussian integers have many neat properties, but among the neatest is that they are - like the integers - a unique factorisation domain. Any Gaussian integer can, essentially ((By which I mean, up to a power of $\i$)), be decomposed into one set of prime factors. Primes, though, are funny things: numbers of the form $4n+3$ or $(4n+3)\i$ are primes if $4n+3$ is prime; otherwise, Gaussian primes take the form $a + bi$ with $a^2 + b^2$ being a prime not of the form $4n+3$, with neither $a$ nor $b$ being zero. For example, $5 + 2\i$ is a Gaussian prime, because $a^2 + b^2 = 29$, a prime that’s one more than a multiple of 4. Also, $-1-\i$ is a Gaussian prime, because $a^2 + b^2 = 2$, a prime that’s not in the form $4n+3$. Clear enough?

In particular, our number - one more than a multiple of 4, but with $b=0$ - is not a Gaussian prime. In fact, having written our number as the sum of two squares in two different ways, we know it has factors in the Gaussian integers of $(850\pm347\i)$ and $(875 \pm 278\i)$.

How does this help?

The key thing is that the Gaussians are a unique factorisation domain - we have two distinct factorisations of our number, which means that these factors are not prime.

Suppose $850+347\i = g_1 g_2$, where $g_1$ and $g_2$ are Gaussian integers and $g_1$ also divides $875+278\i$. We know such numbers exist. Because $850-347\i$ is its complex conjugate, this must be $\bar{g_1} \bar{g_2}$.

We can also state that $875 + 278\i = g_1 g_3$ and $875 - 278\i = \bar{g_1}\bar{g_3}$ for some further Gaussian integer $g_3$.

Now the clever bit: if we work out $(850+347\i)(875-278\i)$, we get $g_1 \bar{g_1} g_2 \bar{g_3}$ - and $g_1 \bar{g_1} = |g_1|^2$, an integer that’s a factor of our original number!

This works out to be $840,216 - 67,325\i$ - and if we apply the Euclidean algorithm to the two components, we’ll find $|g_1|^2$!

The Euclidean algorithm

The Euclidean algorithm finds the greatest common factor of two numbers by repeatedly taking multiples of one away from the other, as follows:

  • $840,216 = 12 \times 67,325 + 32,316$
  • $67,325 = 2\times 32,316 + 2,693$
  • $32,316 = 12 \times 2,693$ exactly

This gives 2,693 as a factor of our original number - in fact, it’s $2,693 \times 313$.

Aharr!

“You could just put it into Wolfram Alpha, though, couldn’t you, me hearty?”

But where’s the fun in that?

* Many thanks to Hilarie Orman and Richard Schroeppel for piquing my interest about factorising! * Corrected a mistaken number 2018-10-15. Thanks to @teakaybee for pointing it out! Also added a link.