Saturday, 5 November 2011

From Euclid to the infinitude of 6n+1 and 6n-1 primes.

I said I'd look at the logic of assuming that there is an infinite number of primes in each axis of the n-factor grid used in previous posts (eg primes in the form of 6n+1 and in the form 6n-1). I'm not sure how to prove this properly. Here's how far I got so far, if anyone can see how to fill in the last step I'd be pleased.
Euclid: Assume X is the highest prime number. Multiply all primes up to X together then add one to the resulting primorial. The result must be either a prime or the product of primes higher than X.

OK, so this number X#+1 is clearly of the form 6n+1 since the first two primes are 2*3. However we haven't yet proved that there is an infinite number of 6n+1 primes, since, if it is a product of primes higher than X, those primes could be 6n-1 numbers (since an even number of 6n-1 numbers multiplied will give us a 6n+1 number).

So let's do something slightly different to Euclid. Assume X is the highest prime number. Multiply all primes up to X together then subtract one from the resulting primorial. The result must be either a prime or the product of primes higher than X. If it is a prime it is a 6n-1 prime. If it is the product of primes higher than X, then at least one of them must be a 6n-1 number, since any number of 6n+1 numbers multiplied together will produce another 6n+1 number.

So that proves there is an infinite number of 6n-1 numbers, but still not that there is an infinite number of 6n+1 numbers.

Intuitively it seems there must be since each number in the Sieve of Eratosthenes will sieve out a fairly even selection of 6n+1 and 6n-1 numbers, but that's only a guess really.

Of course the proof above would also show that there is an infinite number of 6n+1 numbers (since you need a 6n+1 number and a 6n-1 number to multiply together to get a new 6n-1 number) - but only if we could assume that X#-1 wouldn't always be a new 6n-1 prime and would sometimes be a product of other primes instead. So it's not quite there.  (Edit - on returning to this post somewhat later on I realise that this paragraph is gobbledygook since a 6n-1 number could always be the product of an odd number of 6n-1 primes, but it doesn't really matter as either way the inifinitude of 6n+1 primes isn't proven using this approach)

I'm probably being stupid and there is probably a proof out there somewhere. (Edit: I think it is implied by Dirichlet's Theorem, so has been proved - I just want to see a proof I can get my head around a bit more easily).

Edit: For the infinitude of 6n+1 primes I'm tempted to suggest using the fraction Euler used (below) when he proved its inverse was equivalent to the sum of the harmonic series and thus diverged. He did this over all prime numbers, but it is clear that within the 6n+1 axis, the same maths is at work, since 4/5 of the numbers are not multiples of 5, 6/7 aren't multiples of 7, 10/11 aren't multiples of 11 and so on. I don't know how to express that idea more rigorously though.

1*2*4*6*….(p-1)  
2*3*5*7*……p

(Edit: What I was getting at here was something like this bit from Wikipedia: "Stronger forms of Dirichlet's theorem state that, for any arithmetic progression, the sum of the reciprocals the prime numbers in the progression diverges, and that different arithmetic progressions with the same modulus have approximately the same proportions of primes." - that seems intuitively correct to me and would answer the question posed above, I'll see if I can find any proofs that are easy enough for me to follow).

5 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. 1 * 2 * 4 * 6 * .... (P-1)
    2 * 3 * 5 * 7 * ...... p

    yukardaki bu formül her hangi bir n sayısını çarptığında n sayıda kaç tane asal sayı olacağını sana ortalama olarak verir yani n sayısındaki asal sayı(P)
    p=n*(1*2*4*6*10*12*...pmax-1)/(2*3*5*7*11*13*...pmax) olur.

    pmax<=karekökn

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. herhangi bir a sayısında toplam 6n+1 asallarının toplam miktarı
      toplam
      P(6n+1)=a*(1*2*6*12*...*(p(max6n+1)-1))/(2*3*7*13*....*p(max6n+1))

      herhangi bir a sayısında toplam 6n-1 asallarının toplam miktarı
      toplam
      P(6n-1)=a*(1*2*4*10*...*(p(max6n-1)-1))/(2*3*5*11*....*p(max6n-1))
      a=(Pmax(6n+1))^2+c
      1<=c<(Pmax(6n+1))*2+3

      Delete