The infinity of primes

  1. Euclid's proof:

    1) Assume there is a finite number of primes.
    2) Let Pn be the largest prime.
    3) Let X be the P1 * P2 ... * Pn + 1

    At this point the statement is that "X cannot be divided by P1 through Pn", but why is that? This is not self-obvious to me. How can I know this?

    k
     
  2. jcsd
  3. HallsofIvy

    HallsofIvy 40,241
    Staff Emeritus
    Science Advisor

    Because dividing by any of those primes gives a remainder of 1, not 0:

    [tex]\frac{P_1P_2...P_{i-1}P_iP_{i+1}...Pn+ 1}{Pi}= P_1P_2...P_{i-1}P_{i+1}...Pn+ \frac{1}{P_i}[/tex]
    The first term is an integer but the second is not.
     
  4. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Minor aside: "the infinity of primes" is bad grammar. The noun form is wrong here -- you want the adjective "infinite", such as in "the infinite set of primes".
     
  5. Hurkyl

    Hurkyl 16,090
    Staff Emeritus
    Science Advisor
    Gold Member

    Try dividing.
     
  6. That made perfect sense, thank you!

    k
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook