Euclid's proof 
Take any finite list of prime numbers p1, p2, ..., pn. It will be shown that at least one additional prime number not in this list exists. Let P be the product of all the prime numbers in the list: P = p1p2...pn. Let q = P + 1. Then, q is either prime or not:
- If q is prime then there is at least one more prime than is listed.
- If q is not prime then some prime factor p divides q. If this factor p were on our list, then it would divide P (since P is the product of every number on the list); but as we know, p divides P + 1 = q. If p divides P and q then p would have to divide the difference of the two numbers, which is (P + 1) − P or just 1. But no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list. This means at least one more prime number exists beyond those in the list.
This proves that for every finite list of prime numbers, there is a prime number not on the list. Therefore there must be infinitely many prime numbers.
It is often erroneously reported that Euclid proved this result by contradiction, beginning with the assumption that the set initially considered contains all prime numbers, or that it contains precisely the n smallest primes, rather than any arbitrary finite set of primes. Although the proof as a whole is not by contradiction, in that it does not begin by assuming that only finitely many primes exist, there is a proof by contradiction within it: that is the proof that none of the initially considered primes can divide the number called q above.
Euler's proof 
Another proof, by the Swiss mathematician Leonhard Euler, relies on the fundamental theorem of arithmetic: that every integer has a unique prime factorization. If P is the set of all prime numbers, Euler wrote that:
The first equality is given by the formula for a geometric series in each term of the product. To show the second equality, distribute the product over the sum:
in the result, every product of primes appears exactly once, so by the fundamental theorem of arithmetic, the sum is equal to the sum over all integers.
The sum on the right is the harmonic series, which diverges. So the product on the left must diverge also. Since each term of the product is finite, the number of terms must be infinite, so there is an infinite number of primes.
Furstenberg's proof 
Some recent proofs 
Juan Pablo Pinasco has written the following proof.
Let p1, ..., pN be the smallest N primes. Then by the inclusion–exclusion principle, the number of positive integers less than or equal to x that are divisible by one of those primes is
Dividing by x and letting x → ∞, we get
This can be written as
If no other primes than p1, ..., pN exist, then the expression in (1) is equal to and hence the expression in (2) is equal to 1. But clearly the expression in (3) is less than 1. Hence there must be more primes than p1, ..., pN.
But if only finitely many primes exist, then
so that is impossible.[dubious ]
Proof using the irrationality of π 
The following formula was discovered by Euler.
Each denominator is the multiple of four nearest to the numerator.
If there were finitely many primes, π would be rational. This contradicts the fact that π is irrational. However, to prove that π is irrational is considerably more onerous than to prove that infinitely many primes exist.
See also 
Notes and references 
- James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.
- Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.
- Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.
- Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.