In order to make up a quiz question I was recently looking at numbers that can be expressed as the sum of two squares in more than one way. For example, 50 can be expressed as both seven squared plus one squared and also five squared plus five squared. This is the lowest such number (and the answer to my quiz question). However, I looked at some other such numbers. A list follows:
50 (1,7; 5,5)
65 (1,8; 4,7)
65 (1,8; 4,7)
85 (2,9; 6,7)
125 (2,11; 5,10)
130 (3,11; 7,9)
145 (1,12; 8,9)
170 (1,13; 7,11)
185 (4,13; 8,11)
200 (2,14; 10,10)
and so on. I hope that the notation is clear.

I was surprised to notice that all these numbers have 5 as a factor. I continued looking and soon came across 221 (5,14; 10,11). However, of the first 24 such numbers, 20 have 5 as a factor. Does anyone have a simple reason for this?

Of course, if n is such a number, so n (a,b; c,d), then 4n is (2a,2b; 2c,2d) and so there is an infinite number of these. In fact, unsurprisingly, they occur with increasing frequency but it would be interesting to know how the number grows.

Also, if n is such a number and a ¹ b and c ¹ d then 2n is such and is (b-a, b+a; d-c, d+c). The proof of this is very straightforward but has a simple elegance to it.

Incidentally, generating these numbers is very simple. Take any 3 distinct numbers, either all even or all odd (eg 1, 3 and 5).

Note that (1x3)x5 = 1x(3x5) ie 3x5 = 1x15
Now make both sides equal to the difference between 2 squares, finding which squares by adding the factors and dividing by 2 and then subtracting the factors and dividing by 2. In this case this gives;

4² - 1² = 8² - 7²

This gives 4² + 7² = 1² + 8² = 65.

If the three numbers chosen are a, b and c then it can be seen that the number thus generated is (a² + b² )(1 + c² )/4 (including, of course, any cyclic permutation of a, b and c, if none of these is unity).

Also, just as 5 appears to be a preferred factor of these numbers other factors appear to be unpopular. For example, 3 hardly ever appears. I think that the first is 450 (3,21; 15,15) but this is merely a square multiple of another number on the list (ie 3 squared times 50 (1,7; 5,5)) and similarly for 585 (3,24; 12,21). I haven't gone very far (up to 26² ) but I cannot find a single example of such a number which has 3 as a factor but which is not 9 times another such number. Any explanations?

Yours

Daniel Goldberg

I have been thinking about this problem and I think that I have a partial solution.

As you may recall I was interested in numbers which could be expressed as the sum of two squares in more than one way (let us call these numbers versatile ). The lowest versatile number is 50 (1,7; 5,5).

In my last message I showed that any such number can be written in the form (a² + c² )(1 + b² )/4 where a, b and c are three distinct numbers, either all odd or all even. In fact, not such strict conditions apply. Suppose we want to consider; (ab)c = a(bc). Then we need b¹ 1 and a and c are either both even or both odd.

It is easy to see that 1 + b² is not a multiple of 3 for any b (3n, 3n+1 or 3n+2).

Similarly, if both a and c are multiples of 3 then a² +b² will be a multiple of 9. If either a or b or both are not multiples of 3 then neither is a² + b² since (3n)² is zero (mod 3) and (3n+1)² and (3n+2)² are both 1 (mod 3). This explains why no versatile number can have only 1 factor of 3 (or be a proper example in my previous terminolgy) but must be derivable from multiplying another versatile number by 9 (and hence its generators by 3).

Also, 1+b² is a multiple of 5 whenever b ends in a 2, 3, 7 or 8 (ie 4 out of the 10 possibilities rather than 2 out of 10).

Furthermore, if a and c are both even then a² + b² is a multiple of 5 whenever a and c end in the following pairs; (0,0), (2,4), (2,6), (4,2), (4,8), (6,2), (6,8), (8,4) and (8,6) (ie 9 out of 25)

Similarly, if a and c are both odd then we have (1,3), (1,7), (3,1), (3,9), (5,5), (7,1), (7,9), (9,3) and (9,7) (ie 9 out of 25).

Clearly, numbers of factors of 5 have been greatly increased, although not to almost 100%. Besides, I would hope for a slightly more profound explanation.

Also, as with 3, factors of 7 do not occur except as 49 times another versatile number since (7n+i)² (i=1..6) can only by 1, 2 or 4 and so the same argument as above applies.

I would still like to know why 5 predominates.

Daniel Goldberg

Okay; this will probably end up being a rather long post, and will cover quite a lot of what has been talked about above but in a different way.

Let's ignore the thing about the number being written as the sum of two squares in two different ways . SO to start with I'll just look for numbers that can be written as x² +y² .

Let me also suppose that x and y don't share a common factor (so they are 'proper').

Now in this letter I will mainly quote some results (not because they are too hard but because this will just become unreadable), if you actually want to see how these are proved please write back and I'll respond.

Detour on modular arithmetic

I will be using something called modular arithmetic in what follows... now this is just a complicated name for something quite simple. We write x = y (mod a) to mean that x and y leave the same remainder when divided by a. Another way of putting this is that (x-y) is divisible by a. By a square modulo a I mean a number n for which the equation x^2 = n (mod a) has a solution. For example if we work modulo 4 then the squares are 0,1 and the non-squares are 2,3... Try it, you will find that no integer can square to leave a remainder of 2 or 3 when divided by 4.

Notice (or prove) that the product of two squares is also a square. The product of two non-squares is a square. The product of a square and a non-square is a non-square.

Primes as the sum of two squares

There is a theorem which says that ax² +bxy+cy² can take the value p (which is a prime) only if the number b² -4ac is a square modulo p. In our case this says -4 is a square modulo p (and as 4 is a square this is the same as -1 is a square modulo p). Now you might think this doesn't tell us much about p. Actually it is true that -1 is a square modulo p if and only if p is 2 or p = 1 (mod 4). This is the main reason that you found you couldn't get primes like 3 or 7...

So now we know the primes that can be written as the sum of two squares... what about non-prime numbers?

Composite numbers as the sum of two squares

Suppose that x² +y² = n and a² +b² = m. By using complex numbers I can write this as follows:

(x+iy)(x-iy) = n and (a+ib)(a-ib) = m.

So (x+iy)(a+ib)(x-iy)(a-ib) = mn
So [(ax-by) + i(ay+bx)][(ax-by) - i(ay+bx)] = mn
So (ax-by)² + (ay+bx)² = mn.

So if we can get m and n as the sum of two squares then we can get mn. Notice that this is exactly how you got 2n as a sum of two squares!

Because we know what primes we can get we now know that we can get all numbers which are products of these primes as sums of two squares.

Suppose now that x² +y² = a and let p be a prime divisor of a.

So x² +y² = 0 (mod p).
So x² = -y² (mod p)
So y² and -y² are squares modulo p
So (if x,y are not 0 mod p then -1 is a square modulo p
So p must either divide x and y or p must be 2 or p = 1 (mod 4).

So we now know all numbers that x^2+y^2 can be... they are numbers n shuch that the primes that are p = 3 (mod 4) must occur an even number of times in n.

Back to two squares in two different ways

This is the bit that you really want to see. I'll show that any number which is the product of two different numbers that can be written as sums of two squares can be written so in two different ways. This will show that 5 only predominates because it is the smallest prime = 1 (mod 4).

Suppose x² + y² = a² + b² (with x,y and a,b being proper).

Then (x-a)(x+a) = (b-y)(b+y)

Now I can clearly pick these so that x-a and y-b are both even.

Let h be the highest common factor of x-a and b-y.

So x-a = hX and b-y = hY with hcf of X,Y being 1.

So hX(x+a) = hY(y+b)

Hence X divides (y+b) and Y divides (x+a).

So y+b = sX and x+a = sY (check that it must be the same s!).

So 2y = sX-hY and 2x=hX+sY.

Now because x-a and b-y were even we see that h and s are both even, so we can absorb the 2 into them. So write H and S for h/2 and s/2.

Hence x² + y² = (S² + H² )(X² + Y² )

So a number which is the sum of two squares in two different ways is a product of two numbers which are sums of 2 squares. Similarly we can clearly reverse everything to get:

x = HX+SY , y = SX-HY , a = SY-HX , b = SX+HY.

So a number which is a product of two sums of squares can be written as the sum of 2 squares in two different ways... Well almost. We have to check that x,y and a,b are actually different. We only have a problem when X=+/-Y or H=+/-S. And this only happens if we use 1² + 1² = 2. This explains why the smallest example is 50=2×5×5 and not 10=2×5 (the factor 2 is special because it is the sum of two identical squares).

So the first few numbers that are versatile and proper are (I think!):

2×5×5, 5×13, 5×17, 2×5×13,...

Now for a number to be versatile proper and not divisible by 5 it must have two prime factors that are = 1 (mod 4) and not 5 and the smallest this can be is 13.17 = 221 = 10² +11² = 14² +5² . So you can see that for small numbers these are very rare. However in the long run 1 in 13 of the numbers we look at are divisible by 13 and so 1 in 13 versatile numbers are divisible by 13 and in the long run 1 in 5 versatile numbers are divisible by 5. So 5 really isn't that common! It is just a trick of looking only at relatively low numbers.

Well... I think I've rambled on for far too long.

Please let me know what you think of this and if you want me to expand on things I've left out.

AlexB.

To AlexB and anyone else who is reading.

I did do some further thinking about this problem and came up with more stuff. It looks to be along similar lines to AlexB. I'll post it (in colour below) as I wrote it (it wasn't posted at the time in order to promote more discussion!). I think there's just one more point which needs solving from the original thought plus a couple more questions at the end.

Firstly, consider the idea of "useful" and "non-useful" primes (incidentally, I have no idea whether there is a correct terminology for this) as follows; a "useful" prime is one which can be made to equal the sum of the squares of two numbers smaller than itself (where addition is modulo that prime).

For example, 2 is useful since 2 = 1² + 1² . Similarly, 5 is useful since 5 = 1² + 2² . However, 3 is not since 1² = 1 and 2² = 1 (mod 3). Similarly, the squares of the integers less than 7 are 1, 4, 2, 2, 4 and 1 and so 7 is non-useful. 11 is also non-useful but 13 is very much useful because 13 = 2² + 3² . Similarly, 17 = 1² + 4² and 29 = 7² + 3² . However, both 19 and 23 are non-useful.

Therefore, the list of useful primes begins 2, 5, 13, 17, 29 and this almost provides us with the answer to my original question.

Bearing in mind from before that any versatile number must be of the form
(a² + c² )(1 + b² )/4
where a and c are distinct and either both even or both odd and b is not unity, and ignoring 2 for now, it is clear therefore that only useful primes can appear as single (or odd numbers of) factors of versatile numbers (because if a non-u prime p is a factor of the versatile number then either it is a factor (1+b² ), not possible because p is non-u, or of (a² +c² ) in which case it must be a factor of both a and c (again, because p is non-u) in which case p² is also a factor).

If you consider the prime factors of the versatile numbers then it appears that pretty much all combinations of useful primes appear. For example (again ignoring 2 for a while);

5x13 = 65 (1,8; 4,7), 5x17 = 85 (2,9; 6,7), 13x17 = 221 (5,14; 10,11), 13x37 = 481 (9,20; 15,16) and so on

(incidentally, 37 is clearly u since 37 = 1² + 6² ).

Of course, given the size gap between 5 and the next useful prime (13) and given that versatile numbers can be generated from lower versatile numbers by multiplying by 2 (usually), 4, 9 and so on, it is now clear that the lower valued versatile numbers are all going to have factors of 2 and/or 5. It is now only necessary to consider why 2 is relatively under-represented.


I guess generalising to 3 and so on would be simple so rather than coining "useful" above I should have called it "2-useful" or "doubly useful".

Does this relate to anything important, elegant, useful or previously done?


Daniel Goldberg

Daniel,

Again, 2 isn't really under-represented! If you look back at my bit about sums of two squares in two different ways you'll see:

If n = (S² + H² )(X² + Y² )

then if we let:

x = HX+SY , y = SX-HY , a = SY-HX , b = SX+HY.

Then n = x² +y² = a² +b² .

So n will be the sum of two squares in two different ways provided that (x,y) and (a,b) are different. The problem when we multiply by 2 is that 2 = 1² + 1² . So:

(1² + 1² )(l² + m² ) gives:

x=l+m ; y=l-m ; a=l-m ; b=l+m.

Which are the same. So to actually get two different ways we must have that the second number in the product is already a sum of two squares in two different ways. So factors of two in versatile numbers MUST occur with two other odd prime factors. I'm pretty sure that if you remove all power of 2 multiples of the primes then 2 will still be a factor in half the versatile numbers.

Sums of more than two square

Actually generalising it is surprisingly hard! Off the top of my head I'll tell you what I think is true (but be warned it might not all be correct). There is a very good section in a book by Martin Gardner about this sort of thing, unfortunately I don't know its name off hand (my guess is Knotted Doughnuts... )

Cayley proved that every number can be written as the sum of 3 triangular numbers, 4 square numbers, 5 pentagonal numbers etc... Unfortunately I have no idea of the proof!

I think that there are only a finite number of numbers which require more than 3 squares. This is a problem called Waring's problem . The question is in a few different levels of difficulty:

(Easy) Choose a power (square, cube, fourth...) and show that with a fixed number of these you can get all positive integers. [done by Hilbert]

(Hard) Find the smallest number of squares, cubes, ... that you need to get all positive integers. [solved completely, see below]

(Really Hard) Find the smallest number of squares, cubes,... that you need to get all apart from a finite number of the positive integers. [Not even known for cubes!]

You can do all these problems too when you allow yourself to subtract as well as add - called the Generalised Waring problem .

Just in case you're interested, here is the answer to the hard question:


Suppose we're taking n^th powers, let g(n) be the number of n^th powers you need to get every integer, then:

Let 3ⁿ = q 7#215; 2ⁿ + r with 0 < r < 2ⁿ . (In other words, q is the quotient of 3ⁿ / 2ⁿ , and r is the remainder.)

If r+q < = 2ⁿ then
g(n) = 2ⁿ + [(3/2)ⁿ ] - 2.

If r+q > 2ⁿ then
g(n) = 2ⁿ + [(3/2)ⁿ ] + [(4/3)ⁿ ] - 2 if Q = 2ⁿ
g(n) = 2ⁿ + [(3/2)ⁿ ] + [(4/3)ⁿ ] - 3 if Q < 2ⁿ

Where Q = q + (q+1)(4/3)ⁿ .


Write back if you want more information.

AlexB.