Factorising a large number, part I: Sums of squares in different ways

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 squares1? 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 9202 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 square3.
  • $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.

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

  1. Proof by MathsJam $\blacksquare$ []
  2. whoosh 918.1 whoosh []
  3. Note that since the squares are 20 apart, the increase in the difference is $20\times (910+890)$, a pattern we can exploit. []

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter