Sunday 22 January 2012

Composite numbers seen as the difference between two squares.

I've been looking at a different way of thinking about the distribution of primes and twin primes. I want to make some notes about it here to help clarify the patterns I am looking at.

The general plan of what I want to do over the next few posts is this:

1. Explain how composite numbers are related to the difference between two square numbers. Show a way of sieving for composites/primes using this. (This is the basis of Fermat factorisation, but I am going to approach this from basics as I want to understand the nuts and bolts).
2. Look at the pattern of composite numbers that are adjacent to (eg 1 more than or 1 less than)  multiples of 12.
3. Extend this analysis to composite numbers that are adjacent to 24, 48, 96 etc, doubling each time (3*2^n as n increases).
4. Make some observations on the elements of (fractal-like) self-similarity in these patterns.
5. Conjecture as to how these patterns help to explain or suggest (not prove) the infinitude of twin primes.

OK, so firstly, why does the difference of two squares always produce a composite number? This is easy to explain - N^2 - M^2 = (N+M)(N-M) so if N and M are two different positive integers, the result is a positive composite number, unless N - M = 1, in which case the number may be prime (for instance 7^2 - 6^2 = 1x13 = 13 whereas 18^2 - 17^2 = 35, but this can also be expressed as 6^2 - 1^2).

Here is a chart showing composite numbers generated by subtracting the square of M (the vertical axis) from the square of N (the horizontal axis). Note that the first row is N^2 - 0^2 = N^2. Obviously this is also always a composite number.


When looking for primes > 3 we are considering odd numbers of the form 6X+1 or 6X-1 where X is a positive integer.

The chart doesn't consider cases where N - M < 5 because these cases don't generate any composite 6N+/-1 numbers (see below for the reason why).

Where N and M are both even or both odd, the difference between the two squares will be even, so we will only be looking at cases where one is odd and the other is even. It is also clear that you only get a number of the form 6X+/-1 where (N+M) and (N-M) are also both of the form 6X +/-1. (I hope this is obvious enough not to need a lengthy explanation)

Examples of this include.
5^2 - 0^2=  5 x 5 = 25
6^2 - 1^ 2 = 5 x 7 = 35
7^2 - 0^2 = 7 x 7 = 49
8^2 - 3^2 = 5 x 11 = 55
9^2 - 2^2 = 7 x 11 = 77
9^2 - 4^2 = 65
10^2 - 3^2 = 91
11^2 - 6^2 = 85
12^2 - 1 ^2 = 143
12 ^2 - 5^2 = 119
12^2 - 7^2 = 95

The final thing I will note in this post is that the numbers that are pink above are all 11 or 1 (mod 12) while the numbers coloured orange are 5 or 7 (mod 12). The pink numbers are thus adjacent to (one more or one less than) multiples of 12.

It's pretty clear that we only get a composite odd number of the form 6N+/-1 adjacent to a multiple of 12 when one of N and M is a multiple of 6 and the other is 1 or 5 (mod 6).

(Briefly, the reason for this is that squares of 6N+/-1 numbers (eg 1 or 5 mod 6) are always 1 (mod 24) and squares of multiples of 6 are always 0 (mod 12) so the difference between them will always be 1 or 11 (mod 12). Whereas squares of numbers that are 3 (mod 6) are always 9 (mod 12) while squares of numbers that are 2 or 4 (mod 6) are always 4 (mod 12) - meaning the difference between them will always be 5 or 7 (mod 12). )

This all means that we can take out 3 out of every six vertical columns in the chart (the ones containing orange numbers) if we only want to sieve for composite numbers adjacent to 12.

In subsequent posts I will look at how the number of composites in the pattern halves as we double up to look for composite numbers adjacent to 24, 48 and so on.

Part Two

No comments:

Post a Comment