Monday 25 March 2019

Prime Questions


For some reason I was thinking about prime numbers.  Prime numbers are numbers that have exactly two positive divisors, themselves and one.  If you can divide a number by any smaller whole number that is greater than one, it’s not a prime.  (Note that this makes one itself not a prime, since it has only one divisor, which is also itself.)

Prime numbers have some interesting characteristics:

  •        All primes greater than or equal to 5, when squared are equal to a multiple of 24 plus 1.
  •        Primes are getting hard to find, the most recently found ones are very, very big (at time of writing, it is 282,589,933 – 1).
  •        Primes are can be used for cryptography.  The bigger the prime, the more useful it is (well … potentially).
  •        If you find a new prime, you can get paid for it.  If you find a really massive one, one billion digits long (I’m guessing that’s binary digits), you’ll win a cool $250k.
Anyway, I was thinking about whether you could use the primes that we already have to identify new primes.  The current method, as far as I know, is to throw out all obvious non primes (anything divisible by 2,3,5, etc) and then just grind away on it.  This is being crowd funded using the GIMPS program, although that effort is only looking at Mersenne primes (2P-1).  I’ve just joined the program and am doing number crunching in the background.


The first idea I came up with was what I found to be the weak Goldbach conjecture, namely that all odd numbers (above a lower limit) can be constructed from three primes.  Initially I was a bit unsure as to whether one is counted as prime.  Back in Goldbach’s day one was considered prime, but since then the definition has been tightened up to remove 1 from consideration, placing it in a special category where it is neither prime nor composite.  Even earlier there was a line of thought that two is not prime, due to it being even, while all the rest are odd.   Whether one is prime or not does not affect what follows over than where the lower limit is.  The lowest of the lower limits however does exclude 2, and the highest of the lower limits excludes all primes below 11.

So, on to my question … I am wondering whether there is a name for the following two conjectures, either independently or combined:

1) For every prime P, at or above a lower limit as high as 11 or as low as 3, there are two primes A and B such that 2*A+B=P, and

2) For every prime P, there exists a prime X such that, if Y=2P+X, then Y is prime.

I checked the first conjecture against the first 300 or so up to 2099 and the second conjecture against the first 165 or so all up to 1019 and it seems to work.  I suspect that it would work for all primes and there might be a good equation to show why that is the case, but figuring that out will need to wait until another day.

The reason why I have the caveat against the first conjecture is that if 1 is considered to a prime (in so much as not being composite), then 3 = 1*2+1 and that counts, and if 2 is eliminated as a prime for some reason (not being an odd number), then the lower limit is 3*2+5=11.  If you only eliminate 1, then the lower limit is 2*2+3=7.  I think this is the "right" lower limit, but someone is certain to strenuously disagree with me on that.

If the conjecture holds up to scrutiny, and it’s not trivial, and naming rights have not already been claimed, then I’m priming myself to claim them!  I wonder what the prize is for that.

---

I've had a look at the figures and its seemed pretty trivial to prove the first conjecture.  I really should have done that before crunching through all the primes (although it was a pleasant way to spend an otherwise boringly quite morning at work).

Then I tried to put it down on paper in order to explain my proof and ... it became less trivial, and with less "proof-ness".  Back to the drawing board.

In the process of failure I did remember that I was using another conjecture or theorem that I don't know the name of, namely that all primes greater or equal to 5 take the form 3(2n)±1, where n is an integer.  All this is saying is that a prime can be neither a multiple of 3 nor even, so they are going to sit either above or below an even multiple of 3 (since the number on either side of an odd multiple of 3 is even, and the number beyond that is one away from an even multiple of 3).  I guess I could say 6n±1, but that doesn't highlight that I'm basing the claim on how multiples of 3 are arranged.

Interestingly, composite (ie non-prime) odd numbers above 5 seem to only take the form 3(2n)±1 if and only they are the product of primes where each prime P>3 - for example 25 (5x5), 35 (5x7), 49 (7x7), 55 (5x11), 125 (5x5x5), 175 (5x5x7), etc.  Another way to state this is that, if you are given an odd number greater than or equal to 5, then you can add and subtract 1 and if either result is a multiple of 6, then that number is either a prime, or the product of two or more primes (where each prime P>3).

I’m not sure whether this is a conjecture or a proved theorem - I have a recollection that it is something that is used in cryptography, but I might be wrong.  If anyone knows, please let me know and I’ll put a link in.