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

Formula For the Primes?

  1. Mar 8, 2009 #1
    In What is Mathematics, the author gives Euclid's proof that there are infinitely many primes by assuming there aren't infinitely many, and taking all the primes, multiplying them together (P1*P2...*Pn), and then adding 1 - showing that this is larger than the largest prime, but not divisible by any of the primes (because of the remainder of 1) thus contradicting the assumption. Does this sexy reductio proof give us a method of find infinitely many primes? If we take all our known primes, multiply them together, and add one, do we always get a new prime and are thus able to find an infinitude of primes with a big enough calculator?
  2. jcsd
  3. Mar 8, 2009 #2
    False. If their are infinite many primes greater then zero and the primers are integers then there is no largest prime. That is their are no infinite subsets of the naturals with an upper bound.
  4. Mar 8, 2009 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Uhh... John, the proof's perfectly fine. I think you misread it

    Pupil, the problem is you need to know ALL the primes. For example, we start off with 2 as a prime.

    2+1=3. Great!

    2*3+1 = 7 Great! (wait... we missed 5....)

    2*3*7+1 = 43 Great! (wait... now we're missing a bunch of primes)

    2*3*7*43+1 = 1807 = 13*139

    You can see the problem here is that we missed some primes (most primes), and when we do the next step the result could be divisible by a prime we didn't include. Of course, we can try to extend this a bit, but if you start with any finite list of primes, after your first step it should intuitively be obvious you're going to start missing a lot of primes, and those could divide the new numbers you're generating
  5. Mar 8, 2009 #4
    Ah, I see. So basically, if we should know all the primes on a given interval from 0 to n we could at best find one prime larger than n with certainty by this method. Fascinating. Damn these primes for being so elusive!
  6. Mar 8, 2009 #5
    Oh, okay. Thanks.
  7. Mar 8, 2009 #6


    User Avatar
    Science Advisor

    No. Euclid's proof does not say or require that "P1*P2*...*Pn+ 1" must be prime. It says that, since it is not divisible by any of the primes P1, P2, ..., Pn, either it is prime or it is divisible by some prime larger than P1, P2, ..., Pn.
  8. Mar 8, 2009 #7
    I decided to Google it.

    Why can't p divide:

  9. Mar 8, 2009 #8
  10. Mar 8, 2009 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If p divides 1, then p<1.

    Maybe not even one step... for example, 2*3*5*7*11*13*17+1 is divisible by 19.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook