Question about Euclid and Prime numbers.

  • Thread starter Iccanui
  • Start date
  • #1
11
0

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 thats why its false. There is no PROOF.


As always, thank you.
 

Answers and Replies

  • #2
329
0
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.
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,833
963
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.
 
  • #4
329
0
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.
 
Last edited:
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,833
963
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!
 
Last edited by a moderator:
  • #6
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,557
767
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.
 
Last edited:

Related Threads on Question about Euclid and Prime numbers.

  • Last Post
Replies
10
Views
3K
Replies
7
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
827
  • Last Post
Replies
2
Views
12K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
14
Views
2K
Replies
8
Views
2K
  • Last Post
Replies
2
Views
931
Replies
5
Views
1K
Top