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

Want to identify that a number is prime

  1. Jun 14, 2007 #1
    Well i read this somewhere that most prime numbers will give a whole number when equated with the formulae 6n+/-1(plus or minus)
    Is there any proof for this or is it just a coincidence.
  2. jcsd
  3. Jun 14, 2007 #2
    Well you are saying that most prime numbers are of the form 6n+1 or 6n+5 for some n.

    Well, note that all numbers can be written as 6n+m for some n, and some m between 0 and 5. So all we are claiming is that m cannot be any number other than 1 or 5. This can be seen simply by checking cases.

    p=6n+0 would imply p is a multiple of 6, so not prime
    p=6n+2=2(3n+1) implies p is even, so not prime unless p is 2
    p=6n+3=3(2n+1) implies p is a multiple of 3, and so prime only when p=3.
    p=6n+4=2(3n+2) implies p is even.
  4. Jun 15, 2007 #3

    Gib Z

    User Avatar
    Homework Helper

    On from DeadWolfe's post, that doesn't end up telling you that the number is actually prime though. It just rules out that 2 and 3 are not factors, which indeed rules out a lot of numbers, but isn't actually very effective. ie 35 = 6*(5) + 5. However 35 is not prime, 5*7.
  5. Jun 15, 2007 #4
    There can't be any known way for the simple reason that if there was one, Euclid's proof of the infinity of prime numbers wouldn't be the only one, as it is now.
    Last edited: Jun 15, 2007
  6. Jun 15, 2007 #5
    What are you saying? There is no way to tell whether a number is prime? Obviously there are methods (we can all think of at least one)

    Furthermore, I don't understand how this would relate to proofs of the infinitude of primes, but there are many known proofs of this fact.
  7. Jun 15, 2007 #6
    Are there? Admittedly I was venturing myself a bit so the argument probably doesn't hold. Though, I am skeptical whether that there is a general way to verify that a number is prime. If there was, it would be simple to construct prime numbers, something that I doubt is possible.
    Last edited: Jun 15, 2007
  8. Jun 15, 2007 #7
    Of course there is: to test p is prime, check all the numbers less than sqrt(p) and make sure none of them divide p. Of course, this does indeed yield a method for constructing primes, called the sieve Eratosthenes, and it has been known for thousands of years. Of course it isn't very effective...
  9. Jun 15, 2007 #8
    Sieve of Eratosthenes you say? I was unaware of that, I'll look into it.
  10. Jun 16, 2007 #9

    Gib Z

    User Avatar
    Homework Helper

    Not to mention I can think of a few proofs for the infintitude of the primes, my favorite being Euler's which shows [tex]\sum \frac{1}{p} [/tex] diverges, which of course it can't unless there are infinite p.
  11. Jun 16, 2007 #10
    Since that's from Euler, it's undoubtedly correct, but I don't follow the logic. If p = {1, 2, 3, ... 2^1000} rather than primes, that would also diverge but it has an explicit upper bound. How do you get from a diverging sum to proof of infinitude?
  12. Jun 16, 2007 #11
    If p belongs to any set of numbers let's call it P, it is fairly obvious that if P is finite then the sum of all 1/p converges because this is a finite sum of finite numbers. This statement is equivalent to( the contrapositive of) the statement that if the sum of all 1/p diverges then P is infinite.
    Last edited: Jun 16, 2007
  13. Jun 16, 2007 #12

    Gib Z

    User Avatar
    Homework Helper

    Umm if they example serious you gave where p = 1,2,3,4,5,.... then it diverges if that sequence has an infinite number of terms. However if it has a finite number implied by your 2^1000, then it actually converges.
  14. Jun 16, 2007 #13
    I guess I was thinking it diverges because

    [tex] \frac{1}{1} + \frac{1}{2} + \frac{1}{3} < \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}[/tex]

    and that adding each subsequent 1/n would produce a greater sum than the last, thus divergence. That's not what you mean by divergence though I suspect.
  15. Jun 16, 2007 #14
    OK. That makes sense. Thanks
  16. Jun 16, 2007 #15
    Remember that a series is said to converge if the limit of the sequence of it's partial sums converges. In the case:

    [tex]\sum_{a\in A}\frac{1}{a}[/tex]

    Where A is finite (i.e., |A| = some natural number n), the series of partial sums converges exactly to nth partial sum. Intuitively, what could the (n+1)th partial sum possibly be? If it was anything other than the nth partial sum, it would seem to indicate that |A|> n, which would violate our hypothesis. Since A is finite implies this series is convergent, then the contrapositive must also be true--if this series is divergent, then A is infinite.

    Of course this doesn't actually prove that this series is divergent when A is the set of prime numbers. Just that if it is divergent, then there must be infinite number of prime numbers.

    Edit: Looks like I was beaten to the punch.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook