Results 1 to 2 of 2

Math Help - Confused About Euclid's Proof of Infinite Prime Numbers

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    1

    Confused About Euclid's Proof of Infinite Prime Numbers

    I've read several variations on Euclid's proof, mainly:

    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.

    from Euclid's Proof of the Infinitude of Primes (c. 300 BC)

    What I don't understand is why "p can not be any of p1, p2, ..., pr, otherwise p would divide the difference P-p1p2...pr=1, which is impossible." Why can't it, for instance, be divisible by p1*p1*p1*p2? In other words I don't understand why "p would divide the difference P-p1p2...pr=1".

    ----

    After thinking about it, I found a satisfactory answer but since I wrote all of the above, I figured I would post this with the answer.

    As a reminder from above: P = p1*p2*p3...pr+1 and p is a prime of P. Define A such that:

    A = P/p
    = (p1*p2*p3...pr+1)/p
    = (p1*p2*p3...pr)/p + 1/p

    Since p is a prime of P, A must be a whole number (e.g. 2 is a prime of 6 so 6/2 = 3 which is a whole number). Assume that p is any of p1,p2,p3...pr.

    From the above, we can see that if p is equal to any of p1, p2, p3, then the first term of A ((p1*p2*p3...pr)/p) is a whole number, but the second term of A (1/p) is a fraction. A fraction subtracted from a whole number is a fraction. Therefore there is a contradiction since when p is any of p1,p2,p3...pr, A is a fraction. Therefore, p cannot be any of p1,p2,p3...pr.

    Sorry if it's a bit verbose. If anyone has a better explanation, please post it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,319
    Thanks
    1238
    If there was a finite number of primes, then there would exist some "biggest prime number". Call it P.

    Therefore, you could create a number that was the product of all the prime numbers. Call it N.

    So N = 2\cdot 3\cdot 5 \cdot 7 \cdot 11 \cdot \dots \cdot P.


    Then N + 1 = 2\cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot \dots \cdot P + 1.

    If you were to divide N + 1 by ANY of the prime numbers, then you would ALWAYS have a remainder of 1.

    That means that either there is a prime number larger than P which divides N + 1, or else N + 1 is itself a prime number.

    Either way, this contradicts our original statement that P is the largest prime.

    Therefore, there is an infinite number of prime numbers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof involving prime numbers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 7th 2011, 02:38 PM
  2. proof with perfect and prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2010, 07:46 PM
  3. Proof relating to prime numbers
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: January 13th 2010, 11:31 AM
  4. Proof relating to prime numbers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 13th 2010, 10:02 AM
  5. Proof with prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 25th 2009, 08:58 PM

Search Tags


/mathhelpforum @mathhelpforum