Primes as the sum of two squares
Some thoughts on expressing prime numbers as the sum of two squares
In the Hans Woyda competition there have been several team rounds recently asking teams to find different ways of expressing integers as the sums of squares or the sums of cubes. The 2020 semi-final for example told teams about a theorem stated by Fermat and proved by Lagrange in 1770 that every positive integer n can be expressed as the sum of at most four squares (e.g. 21=1²+2²+4²). They team had 5 minutes to find solutions for 20<n<50, a rather simple task at that stage of the competition.
The Knock-Out stage 1 team round in 2020 was about expressing numbers as the sum of three cubes. This was inspired by the discovery only in September 2019 of a solution to 42=x³+y³+z³. Teams had to find a single solution, where possible, for every integer from 1 to 48, where x,y and z were limited to integers between -8 and 8. A sensible approach was to write down all the cubes from 0³ to 8³ and look for combinations of numbers from this set.
With more time, an approach could be to write a computer program to look for solutions. The solutions for 33 and for 42 were only discovered last year. Here is the solution for 42.
42 = (-80 538 738 812 075 974)³ + 80 435 758 145 817 515³ + 12 602 123 297 335 631³
It can be shown that some numbers have no solutions on theoretical grounds, but there is no formula for producing solutions or even for showing that a solution exists for a particular number.
Let’s look at the simpler problem of finding how many solutions there are to equations of the form
p = x² + y²
where p is a prime number.
The only even prime is p=2 and it has the solution 2 = 1²+1²
All odd numbers can be expressed in the form 4k+1 or 4k+3 and for some values of k these are prime.
Modulo arithmetic is a very rich area for exploration. It is sometimes called clock arithmetic and is explored a little in year 7 and then pretty much ignored until the sixth form. Arithmetic is nice and easy for answers are simply the remainder when the ‘normal’ answer is divided by the modulus. For example 3 x 9 = 6 (mod 11). The only numbers needed for any sum are 0,1,2,3,4,5,6,7,8,9,and 10.
Think about square numbers in modulo arithmetic.
If a number n is even then it can be written as n=2k so n²=(2k)²=4k² so n²=0 (mod4) which tells you that any even number squared is divisible by 4.
If a number n is odd then it can be written n= 2k+1 so n² = (2k+1)² = 4k²+4k+1 =1 (mod4).
Thinking about primes of the form p=4k+3
All such primes = 3 (mod4).
Apart from 2, all other primes are odd so if two squares add up to a prime (not 2) one must be odd and one must be even.
All odd squares = 1 (mod4)
All even squares = 0 (mod4)
So, any odd square + any even square = 0(mod4) + 1(mod4) = 1 (mod4)
But any primes of the form p=4k+3 = 3 (mod4) so we conclude that primes of the form p=4k+3 can never be expressed as the sum of two squares. There is no point looking for solutions for our logic shows that there cannot be any solutions.
Let’s turn primes of the form p = 4k+1. Solutions can exist, for 4k+1 = 1(mod4).
A quick look at a few examples for small primes shows that the first few primes of this type can be expressed as the sum of two squares: 5 = 1² + 2² , 13 = 2² + 3², 17 = 1² + 4², 29 = 2² + 5², etc.
You could keep looking at bigger and bigger primes and if necessary do an exhaustive search, perhaps using a simple program in Python, for any case and you would always find a solution – but this is not a proof. It is circumstantial evidence that suggests a theorem but can we provide a proof?
One good way to prove that there is always a solution uses the pigeon hole principle (a method for another article!). I want to show you that people are finding new methods and approaches all the time. The method I will illustrate was discovered by a Russian school teacher called Alexander Spivak as recently as 2007. He thought about solutions of the form 4xy+z² = p.
I will draw the diagrams for a particular value (p=29) but the approach can be generalised for any value of p. As part of a masterclass type lecture to secondary school students Spivak drew similar diagrams on the board. His approach had not been seen before that.
Taking p =29, then z can be 1,3 or 5. If there are solutions they can be represented with 4 squares at the corner of the square with sides x and y. This gives us a winged square. We only want different solutions so we can exclude congruent shapes by making the L shape at upper right with height >= width. Each solution of 4xy+z² leads to a unique winged square. Looking only at the outline shape, pairs of the ‘winged squares’ have the same ‘winged shape’. The winged shapes are polyominoes with 4-fold rotational symmetry. Notice that a square shape is impossible as 4xy+z² = p, a prime. For this case of p=29, z can be 1,3, or 5.
If z=1, you need to add four wings of area 7 so x=1, y = 7 or x =7, y=1
If z= 3, you need to add four wings of area 5 so x=1, y=5 or x=5, y=1
If z=5, you need to add four wings of area 1 so x=1, y=1 The five cases are shown in the following sketch.
In the sketches we started with the winged squares and found that every two winged squares give one winged shape apart from the basic cross shape that makes its own winged shape.
Let’s reverse the argument and start with any winged shape of rotational symmetry order four. The central section must be a square of odd size as the total area must be odd (All primes of the form 4k+1 are odd). Here is one with area =41.
All such winged shapes (except one) can be divided into winged squares in two ways; as shown in the two diagrams below with the additional red lines.
The only case that does not lead to 2 winged squares is the symmetrical cross shape like the top right hand example in the p=29 winged shape examples.
So if all the possible winged shapes are converted to winged squares there are an odd number of solutions; 2 x the number of possible winged shapes plus one for the simple cross. But these winged squares each correspond to a solution of 4xy + z² = p, and we have just determined that there are an odd number of solutions in total. If x≠y there are two paired winged solutions for every x,y pair so an even number of such solutions altogether, so if x=y there must be an odd number of solutions of that type since the total number of winged squares must be odd. The most important thing is that there must be at least one (the lowest odd number), but might there be 3 or even 5 or more?
There is guaranteed to be at least one solution with x=y, so there is at least one solution of the form
4x² + z² = p or (2x)² + z² = p
so there is always a solution of the form a² + b² = p if p is of the form 4k+1.
In the case of p = 29 that solution was (1,1,5) leading to 4+25 = 29 or 2² + 5² = 29 , the last of the winged square diagrams for 29.
At this point I went down a blind alley a few days ago. Two paragraphs ago I said the number of solutions with x=y must be odd – could it be 3 or 5 or ….? If so p = 4k+1 could be written as the sum of two squares in these cases in that number of ways. If I had got out a number theory book I would have discovered that there is a proof that the solution is unique. Spivak’s winged shapes and winged squares show there definitely is at least one solution and if there are more there are an odd number in total – the drawings don’t exclude the extra pairs of solutions.
I didn’t remember seeing any multiple solutions in the past so knew they would be rare. I used it as an excuse to learn Python3 programming. I downloaded a Python interpreter and Pycharm and a free university textbook for computer scientists (the publisher Springer has many of its text books free for download during the covid19 crisis). I spent a few hours learning the basics of loops, recursion, function definitions and wrote my first program which was to look for primes of the form 4k+1 that had three sets of solutions to a²+b²=p for values of 4k+1 up to 40,000,001. I enjoyed playing with Python but didn’t find any solutions having numerically tested all primes up to 40,000,001. This hints that there might not be any primes with more than one solution – can we prove it?
Hypothesis: There is a unique solution within the natural numbers for every equation, p = a² + b², where p is a prime of the form 4k+1.
A common method of proof in maths is to assume something is true and show that it leads to a contradiction and so the original assertion is proved to be false.
Let’s assume there are at least two solutions, (with the aim of showing that there are NOT!)
Assume p = a² + b² = m² + n² (1)
x (1) by n² n²a² + n²b² = m²n² + n⁴ x (1) by m² m²a² + m²b² = m⁴ + m²n²
subtract and rearrange a²n² - b²m² = m²n² + n⁴ - b²n² - m⁴ - m²n² + a²m² = m²(a² - m²) + n²(n²-b²)
but a²-m² = n²-b² from eqn (1)
so a²n² - b²m² = (m² + n²) (n² - b²) or a²n² - b²m² = p (n² - b²)
so a²n² - b²m² ≡ 0 (mod p) so (an)² - (bm)² ≡ 0 (mod p) (2)
This implies that an = bm (mod p) or an = -bm (mod p) (3)
Using difference of two squares: a²n² - b²m² = (an – bm) (an + bm)
All of a, b, m and n are less than √p, so all of the products an, bm, an and bn are less than p. These together with (2), (3) show that,
either an = bm (4) or, an+bm = p (5)
If (5) then p² = (a² + b²) (n² + m²) = (an +bm)² + (am –bn)² so p² = p² + (am – bn)² so am – bn = 0 so am = bn (6)
(4) and (6) show that either an = bm or am = bn
If (4), then an =bm
so a divides into bm. We write a │ bm
but the greatest common denominator of a and b is 1 since if b = ka, then a²+k²a² = p, so (1+k²)a² = p, but p is prime so no k possible,
so a │ bm implies a │ m
let m = ka
(4) then gives an = bm = b (ka)
so n = bk but p= m²+n² = k²(a²+b²) = k²p implies k=1 implies a = m and b = n.
The argument from (6) follows exactly the same lines as from (4): if am = bn …. (you can fill in the details as an exercise) …. implies a = n and b = m
In both alternatives p = a² + b² = n² + m² but with the n,m exactly the same pair of values as a,b, so there is not any alternative solution. There is always a solution of p= a² + b² when p is of the form 4k+1, AND it is a unique solution.
Overall conclusions about expressing primes numbers as the sum of two squares:
p = 2, 2 = 1² + 1² p = 4k +3 (e.g. 3, 7, 11, 19, 23, 32,……) No solutions of the form p = a²+b²
p = 4k+1 (e.g. 5, 13, 17, 29, 37, 41, …….) Each has a unique solution e.g 5 = 1² + 2² 13 = 2² + 3² 17 = 1² + 4² 29 = 2² + 3² 37 = 1² + 6²
I only saw Spivak’s idea for the first time a few days ago.
Preparing the above explanation of his idea and proof I can now see an extension, for the possible winged squares for any value of 4k+1 follow a pattern (in maths we always looks for patterns) and I can see how to create a simple diagram that will allow you to quickly determine which numbers of the form 4k+1 are prime and to state a sum of two squares for that number by inspection. It’s very exciting finding new things yourself (even if eventually it will turn out someone else has been there first). It also allows an estimate of the maximum possible number of primes below a certain number. The complete distribution of primes is known not to follow an exact pattern so estimates of the numbers of primes in a region is the best anyone can do. How will my formula compare with those published by others who have looked at this area? See next time. Looking at my diagrams I can see even more patterns emerging – perhaps I will just set the scene and let you play with the ideas with a few pointers for areas to try. It would make a good STEM project for Big Bang! What I can say is that the method uses nothing more than basic arithmetic and so is accessible to most students at school. As it is an algorithm it is also very suitable for writing as a piece of computer code so I will please Mrs Corkery and Mr Waterman and get my Python skills further developed by working on that side of the problem too.
Mr Ironside 5 May 2020