How can we use Euclid's proof to find infinitely many primes?

[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?

 

[John Creighto]

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,

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.

 

[Office_Shredder]

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.

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

 

[Pupil]

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

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!

 

[John Creighto]

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

Oh, okay. Thanks.

 

[HallsofIvy]

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?

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.

 

[John Creighto]

I decided to Google it.

Suppose that p1=2 < p2 = 3 < ... < pr are all of the primes. Let P = p1p2...pr+1 and let p be a prime dividing P; then p can not be any of p1, p2, ..., pr, otherwise p would divide the difference P-p1p2...pr=1, which is impossible. So this prime p is still another prime, and p1, p2, ..., pr would not be all of the primes.

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

Why can't p divide:

P-p1p2...pr=1

 

[Count Iblis]

http://en.wikipedia.org/wiki/Formula_for_primes#Formula_based_on_a_system_of_Diophantine_equations"

 

[Office_Shredder]

I decided to Google it.

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

Why can't p divide:

P-p1p2...pr=1

If p divides 1, then p<1.

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!

Maybe not even one step... for example, 2*3*5*7*11*13*17+1 is divisible by 19.