Thread: 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.

If there was a finite number of primes, then there would exist some "biggest prime number". Call it .

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

So .


Then .

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

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

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

Therefore, there is an infinite number of prime numbers.