Primes of form 4k+1 part 2
Can we express numbers of this type as sums of two squares and say whether or not they are prime? YES and YES.
In my last post there was quite a lot of fairly technical maths, proving results about the nature of primes. Even working on that post was new material for me and it took quite a lot of time to get into the topic. As a teacher you usually look at little bits of maths that can be finished or solved completely with an upper time limit of about an hour - this topic has been more like a project for me.
I could see lots of things to follow up from the last post and this week I have spent many hours looking at extensions and trying to prove my ideas - not all completely finished yet. The detail will probably only interest a small number of students so instead I am going to write up the detail for an article to submit to a maths journal.
However, more of you may be interested in the general process of working on a new area of study in maths. Experiment, draw diagrams, look for patterns, start with the simplest examples and add complexity one feature at a time, turn patterns into formulae, make conjectures and test them and, finally, prove them.
It all started with trying to reverse the process that Spivak undertook when proving that every prime of the form p=4k+1 can be expressed as the sum of two squares. I also showed last time that such a solution, if it existed, is unique.
I thought about the possible winged shapes with an area = 4k+1. If a winged square can be drawn from any of the winged shapes then the area can be expressed as the sum of two squares. If there is more than one solution then the value 4k+1 cannot be prime. For example 65 = 4 x 16 +1 can be expressed as,
65 = 1² + 8² = 7² + 4²
There is more than pair of squares summing to 65, so 65 is not a prime. 65 = 5 x 13.
A very interesting example is 725 = 4 x 181 +1 = 7² + 26² = 23² + 14² = 25² + 10²
725 can be expressed as the sum of two squares in three different ways, so cannot be a prime number. Last week I described writing a computer program to search for primes which could be expressed as the sum of two squares in three ways. I didn’t find any up to 40,000,000 and of course the program didn’t find 725 because it checked whether the number was prime as well. 725 is of the 4k+1 type but fails the prime test.
The diagram below shows winged shapes for 105 and 153 that shows that these winged shape can be cut up and rearranged into a rectangular pattern and so neither 105 nor 153 is prime.
All numbers ending in a 5 are divisible by 5 and so (apart from 5 itself) are not prime, but it is not so obvious in other cases,
e.g. 377 = 4 x 94 +1 = 7² + 18² = 17² + 4² so NOT Prime. 377 = 13 x 29
We know from our work on winged squares last week that the squares had to be of one odd number and one even number to give an odd total.
I next drew a table with one column for each odd integer. Starting with the smallest value 5 = 4 x 1 +1 and then 9 = 4 x 2 +1, then 13 = 4 x 3 + 1,.. I was looking for value = (odd number)² + a number that was 4 times a square. I could see quickly that the squares were appearing in very regular patterns as this structure was built up. Look at the position of all the 0, 1, 2s etc in the diagram below. They follow very regular and easy to describe shapes.
The next step was to try and explain that pattern with algebra. That process took a long time to master. Having spotted the patterns visually (and Spivak’s diagrams were helpful again here) it was much easier to see the patterns when arranged in the table and think about why they were there and so describe the patterns with an algebraic formula. At first the algebra looked too difficult, but perseverance is a great quality in problem solving in any subject and thinking about the solutions in different ways eventually opened up a general method of explaining the patterns algebraically. The diagram below is a ‘final’ version of the table that takes out any unnecessary detail and so makes the patterns more obvious. It didn’t look so neat and tidy in my first attempts, but I was playing with the numbers, not sure what would emerge and as patterns became clearer I redrew the diagram taking out numbers that were not now needed. The entries with O,E and p values are all the primes (from 9 onwards)
The diagram allows you to express any value of the form 4k+1 up to 437 as the sum of squares (in multiple ways if that is possible) and say immediately if the number is a prime. The table can easily be extended to larger values (see tasks at the end).
Here is how to use the diagram: Choose your value of k. For that value of k, look in the row of the main table. Is there a number in that row in the main table? If not, the number 4k+1 is not prime and it cannot be expressed as a sum of two squares; If row contains a 0, the number 4k+1 is a square and hence not prime. If there are more values in the row it can be expressed as the sum of 2 squares in as many ways as there are numbers; If the row contains multiple entries then the number 4k+1 can be expressed as two squares in more than one way and so is not prime; If there is a single entry (not equal to 0) and the entry and column number do not have a common factor, then the value 4k+1 is prime and can be expressed uniquely as the sum of two squares; If there is a single entry but the entry and column number have a common factor then the value of the 4k+1 is not prime; (I have shown these entries with square boxes around them in the table)
The odd number E is the number at the heading of the column for that entry in the row. The even number O is twice that entry. So p=4k+1 = O² + E²
Examples: k=8: no entry in the main table, 4x8+1 = 33 NOT prime (3x11) and 33 cannot be expressed as the sum of two squares.
K=20: 0 in the table, 4 x 20 +1 = 81 = 9² NOT prime (3x3x3x3)
K=56, 0 and 6 in the table 4 x 56 + 1 = 225 = 15² = 9² + 12² NOT prime (3x3x5x5)
K=36, 6 and 4 in table 4 x 36 + 1 = 145 = 1² + 12² = 9² + 8² NOT prime (5 x 29)
K=29, 3 in table but, 3 is a factor of 9, the column heading so 4 x 29+1 = 117 NOT prime as 117 = 9² + 6² = 3²(3² + 2²) = 9 x 13
K=48, 6 in table in column headed 7, so 4 x 48 + 1 = 193 = 7² + 12² and is prime. (7 is the column number and 12 is 2 x 6, the entry in column 7.)
Are the primes in any pattern? I expected the answer to this question to be NO – as there is no general formula for the nth prime or quick ways of determining whether a given number is prime.
However, by analysing the patterns I have described above and converting them into algebra I think I have found a set of formulae which locate every single NON-prime of the form 4k+1 and hence the numbers left over are all primes and can be counted with a formula (although not easily for large primes as the number of terms grows with the size of the number being investigated.
The non-primes fall into sequences which are infinite. For example (and missing out a lot of detail)
In one sequence i = 1, 2, 3, 4, 5, …… (each term differs by 1) m= 7, 15, 23, 31, 39, …… (each term differs by 8) with r =((m+1)(m+8)/4i) + i, so r = 31, 48, 65, 82, 99, ….. and k= r²+12 and p = 4k+1 We have a sequence of values of p = 3893, 9265, 16949, 26945, 39253,…. all of which are NOT prime and this sequence carries on for ever, so there are an infinite number of numbers in this sequence which are not primes.
There are other sequences of m such as i = 1, 2, 3, 4 , 5, …. m= 2, 10, 18, 26,…. with r =((m+1)(m+6)/4i) + i, so r= 7, 24, 41, 58, ….. and k = r² + 6, p= 4k + 1
Giving the sequence p = 221, 2329, 6749, 13481, …..
There are an infinite number of these sequences and each sequence has an infinite number of terms of the form 4k+1 which are NOT primes and yet there are still an infinite number of terms of the form 4k+1 which are primes.
This shows how messy talking about counting in infinite sets becomes. We have an infinite number of values of the form 4k+1 where k=1,2,3,4,…. .
We take away an infinite number of sequences each containing an infinite number of terms and we still have an infinite number left!
∞ - (∞ x ∞ ) = ∞
Things for you to explore.
Carry on the table onto the next sheet (and even further if you have the patience). As the method follows an algorithm the table could be constructed easily to every large numbers.
Colour the diagram to mark the values of k which lead to primes, squares, non-primes with no sums of squares, non-primes with 1,2,3,… different sums of two squares.
Make graphs of numbers of the cumulative number of these different types below the current value.
How many primes are there of the type p = 4k + 1 less than say 100, 200, 300, ……. ?
Mr Ironside 18 May 2020