There is a theorem that states: if a number can be written as the sum of two squares in two different ways, it is composite.

Because of Twitter, I became interested in factorising $n=842,909$. Can this be written as the sum of two squares ((Proof by MathsJam $\blacksquare$))? How - without cheating and using a computer - could we check?

One option is to say “there are only 920 or so square numbers smaller than $n$ - we could simply check them all!” That would… succeed, I suppose, but seems like an awful lot of work. How can we narrow down the search?

Using modulo arithmetic, of course!

Modulo 20, there are only a few possible values for squares: 0, 1, 4, 9, 16 and 5 - and only a few pairs of those add up to 9: we could have 0+9 or 5+4. In each case, one of the squares is a multiple of 5.

This makes things much easier: now we only need to consider squares that end 00 or 25, and their partners - which must end 09 or 84. Now we only need to look at 200 or so possibilities! But surely we could do better than that?

How about modulo 16? There, squares must be 0, 1, 4 or 9; our number is congruent to 13, and the only way we can make that is with 4 and 9.

Let’s switch to thinking about the square root numbers for a while. If $a^2$ ends with 00, $a$ is a multiple of 10; further, if $a^2 \equiv 4 \pmod{16}$, then $a$ can be written as $4k+2$. Putting these together, $a$ must be a multiple of 10, but not 20. There are fewer than 50 of these candidates.

For the other pair, our number ending 25 must be congruent to 9 (modulo 16), which is only possible if the square root is three away from a multiple of 8 - again, reducing our work by half to fewer than 50 candidates.

So let’s do this!

We’ll start at the high end with our multiples of 10 and gradually decrease until we hit a match. Since the square root of 842,909 is somewhere about 920 ((whoosh 918.1 whoosh)) so we’ll start with 910.

  • $910^2 = 828,100$, which is $14,809$ away - not square.
  • $890^2 = 792,100$, which is $50,809$ away - not square ((Note that since the squares are 20 apart, the increase in the difference is $20\times (910+890)$, a pattern we can exploit.)).
  • $870^2 = 756,900$, which is $86,009$ away - not square.
  • $850^2 = 722,500$, which is $120,409$ away, or $347^2$.

Boom! We have one of our squares.

The fives are a bit trickier, since we need to keep track of the remainders modulo 16, but we can do that:

  • 915 is 3 (mod 8), so we want it: $915^2 = 837,225$, 5684 away - not square.
  • We don’t want 905 or 895 (1 and 7, mod 8, respectively)
  • $885^2 = 783,225$, which 59,684 away - not square
  • $875^2 = 765,625$, which is 77,284 away - or $278^2$.

So, $842,909 = 850^2 + 347^2 = 875^2 + 278^2$, which means it can be factorised - which we’ll do in the next thrilling installment.

I can’t help but think the search for squares can be done more efficiently (we got lucky in finding the squares so quickly), but I think this is a very nice paper-and-pencil exercise.