# Formula For the Primes?

1. Mar 8, 2009

### Pupil

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. Mar 8, 2009

### John Creighto

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.

3. Mar 8, 2009

### Office_Shredder

Staff Emeritus
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

4. Mar 8, 2009

### Pupil

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!

5. Mar 8, 2009

### John Creighto

Oh, okay. Thanks.

6. Mar 8, 2009

### HallsofIvy

Staff Emeritus
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.

7. Mar 8, 2009

### John Creighto

http://primes.utm.edu/notes/proofs/infinite/euclids.html

Why can't p divide:

P-p1p2...pr=1

8. Mar 8, 2009

### Count Iblis

Last edited by a moderator: Apr 24, 2017
9. Mar 8, 2009

### Office_Shredder

Staff Emeritus
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.