Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Frequency of prime numbers?

  1. Nov 1, 2010 #1
    Is there a rule governing the frequency of prime numbers?

    Also, I've heard that all primes greater than 3 are of the form 6k+1 or 6k-1. I'm assuming that this is because 6 is the lcm of 2 and 3 (the two primes lesser than 3), and the +1,-1 is because if the number was in a range greater than 1 around the 6k number, it should be a multiple of 2 (even number).

    Can you extend this for any primes greater than any given prime (say 5 instead of 3 for example) ?
     
  2. jcsd
  3. Nov 1, 2010 #2

    HallsofIvy

    User Avatar
    Science Advisor

    Any prime larger than 3 cannot be divisible by 3 and 2. 6k+ 2= 2(3k+1) is divisible by 2. 6k+ 3= 3(2k+1) is divisible by 3. 6k+ 4= 2(3k+ 2) is divisible by 2. 6k+ 5= 6k+ 6- 1= 6(k+1)- 1. Those are the only possiblities.

    No, you cannot do that with, say, 5. 2(3)(5)= 30 but 30k+ 7 may be a prime for example (if k= 1, 30k+7= 37 is prime).
     
  4. Nov 1, 2010 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yes, the Prime Number Theorem.
     
  5. Nov 2, 2010 #4
    But why cant you extend this property? If I understand this correctly this is analogous to Eratosthenes sieve where in you remove multiples of primes. In this case, you're removing multiples of 2,3 and you're searching for a prime near the target number. Shouldn't there be an lcm of the first n primes for which this property is true? Also, is there a formal reason why the 2.3.5 example doesnt work?
     
  6. Nov 2, 2010 #5
    For 2*3*5, you would have primes greater than 5 in the form 30k±1, 30k±7, 30k±11, 30k±13
     
  7. Nov 2, 2010 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Because the prime 5 divides 2 * 3 * 5, and 5 > 3.

    You can always find a fixed group of valid residues mod a number N, but you won't generally be able to express the residues as kN +- 1. (This gives just two residues, and 3 - 1 = 2.)
     
  8. Nov 7, 2010 #7
    I think I see the connection. For the 6k±1 analogy, the only 'prime' less than 2 is one (I know 1 is not prime, but idk what else to call it atm), but to extend it to a higher degree (2*3*5) you would have to add and subtract all primes less than the lcm.

    Going by that logic, if you take just 3,5 the primes should be of the form 15k±2, 15k±7, 15k±11, 15k±13 (you can't take 3,5 because they're included in 15).

    I dont quite follow you. What do you mean by residues?
     
  9. Mar 13, 2011 #8
    You kids are so smart, and WAY above me. But I find the prime number question so fascinating. I believe that when we see more about this set we will also then understand something more profound about the nature of the universe, and will think....."duh"...."it was so obvious, why didn't we see it". Any thoughts, especially how the set relates to chaos theory ? Behave.
     
  10. Mar 13, 2011 #9
    As I see it, 'coprimes' is the magic word. The (positive) integers less than 6 than are coprime to 6 are precisely 1 and 5, giving rise to your two possible forms of a prime: 6k+1 and 6k+5. In the case of 2*3*5 = 30, its coprimes are 1,7,11,13, and 17,19,23,29.

    (Note that they always come in two 'symmetrical' halves: if a is coprime to n then n-a is also coprime to n.)

    Of course, there is no guarantee that numbers of the form 6k+1 or 6k+5 will be primes: for example, 25 is 6*4+1 and it's not prime. But what you know is that numbers in any of the other forms don't stand a chance of being primes. For example, 6k+4 can't be a prime because the common factor 2 can be taken out, rewriting it as 2(3k+2), so it is composite. That's why you look for numbers with no common factors, namely coprimes.

    P.S. Edit: "don't stand a chance"... I was being dramatic. :) Obviously 6k+2 and 6k+3 can be primes when k=0. The rule needs a kickstart: you begin after 2 and 3, the primes you used to build the 6.
     
    Last edited: Mar 13, 2011
  11. Mar 13, 2011 #10
    there is a very simple way to see why primes larger than 2 and 3 are of the form 6k+1 and 6k-1. Draw a hexagon and start numbering from 1 to N ( whatever N is ) along the edges in concentric circles. You will then see that all the primes ( p> 2, 3 ) fall along the 6k+/-1.

    there are many interesting properties that this diagram will show if you spend some time studying it.
     
  12. Mar 13, 2011 #11
    Think of residues as the remainder 0 <= R < N after repeated subtraction of a fixed number (N, in your case 15). Another way to say it is if B = A mod N, where B and A are both positive integers, then the residue of B will be the same as the residue of A after repeated subtraction by N. The residues do not have to be prime, e.g. 15n + 8 can be prime not because 8 is prime but because 8 is coprime to 15 (does not divide 15).
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook