Question about Euclid and Prime numbers.

[Iccanui]

Homework Statement

This is a question i just got in the coursera material.

Euclid's proof that there are infinitely many primes uses the fact that if p1…,pn are the first n primes, then the number N=(p1...pn)+1 is prime. True or False.

The answer was False
I answered true and i THINK i understand why i was wrong.Am i correct in assuming that because p is undefined that p1...pn, etc could be any number. Any number + 1 could be composite or prime and that's why its false. There is no PROOF.As always, thank you.

 

[awkward]

Euclid's proof shows that IF there are only finitely many prime numbers, then the product of all the primes plus 1 is a prime; it's an "indirect proof". Euclid starts by assuming the theorem is false and shows this leads to a contradiction. But if we drop the IF, we can't show that the product of the first n primes plus 1 is a prime by this method. And in fact, it's not true that the product of the first n primes plus 1 is a prime. There is a counterexample, which it would be fun for you to find.

 

[HallsofIvy]

Euclid's proof shows that IF there are only finitely many prime numbers, then the product of all the primes plus 1 is a prime

No, it doesn't. Pretty much by definition, IF there were only finitely many primes, the product of all of them, plus 1, can't be a prime!

; it's an "indirect proof". Euclid starts by assuming the theorem is false and shows this leads to a contradiction. But if we drop the IF, we can't show that the product of the first n primes plus 1 is a prime by this method. And in fact, it's not true that the product of the first n primes plus 1 is a prime. There is a counterexample, which it would be fun for you to find.

Euclid's proof shows that if there were a only a finite number of primes, then their product plus one, because it has remainder 1 when divided by any of those primes, either is a new prime or is divisible by a prime not on that list, either way giving a contradiction.

 

[awkward]

Well, assume there are only finitely many primes, and let's say x is the product of all the primes, plus 1. Since x is not divisible by any prime less than x, x must be prime.

But it's futile to argue what does or does not follow if there are only finitely many primes, because the assumption that there are only finitely many primes leads to a contradiction. In the presence of a contradiction, all statements are true.

 

[HallsofIvy]

Well, assume there are only finitely many primes, and let's say x is the product of all the primes, plus 1. Since x is not divisible by any prime less than x, x must be prime.

No, you don't know that "x is not divisible by any prime less than x". You only know that x is either prime or divisible by some prime larger than any of the primes you multiplied to get x. There may be a prime between the largest prime in the list and x.

But it's futile to argue what does or does not follow if there are only finitely many primes, because the assumption that there are only finitely many primes leads to a contradiction. In the presence of a contradiction, all statements are true.

it is NOT futile to argue about what the contradiction is since you need to be sure there is a contradiction!

 

[LCKurtz]

Well, assume there are only finitely many primes, and let's say x is the product of all the primes, plus 1. Since x is not divisible by any prime less than x, x must be prime.

No, you don't know that "x is not divisible by any prime less than x". You only know that x is either prime or divisible by some prime larger than any of the primes you multiplied to get x. There may be a prime between the largest prime in the list and x. it is NOT futile to argue about what the contradiction is since you need to be sure there is a contradiction!

It seems to me that awkward has a point. The hypothesis is that are finitely many primes and they are $p_1,p_2,...p_n$. Call their product $P$. Then $x= P+1$, as you note, is either divisible by some prime larger than any of the primes you multiplied to get $P$ (it can't be because you have listed all the primes) or it itself is prime. So it is prime, which is a contradiction to the fact that they were all listed. I don't see why the argument can't be phrased this way.

[Edit]:Never mind. I didn't read carefully enough what awkward said to which you were responding.