1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about Euclid and Prime numbers.

  1. Sep 20, 2012 #1
    1. The problem statement, all variables and given/known data

    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.
     
  2. jcsd
  3. Sep 20, 2012 #2
    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.
     
  4. Sep 20, 2012 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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!

    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.
     
  5. Sep 21, 2012 #4
    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: Sep 21, 2012
  6. Sep 22, 2012 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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!
     
    Last edited: Sep 22, 2012
  7. Sep 22, 2012 #6

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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: Sep 22, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Question about Euclid and Prime numbers.
Loading...