Euclid's theorem

From Wikipedia, the free encyclopedia

Euclid's theorem is a fundamental statement in number theory which asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.

1 Euclid's proof
2 Euler's proof
3 See also
4 External links

[edit] Euclid's proof

Euclid offered the following proof published in his work Elements (Book IX, Proposition 20) and paraphrased here.

Take any finite list of prime numbers $p_1, p_2, \dots, p_n$ . This list will be shown not to contain all prime numbers, as follows:

Let P be the product of all the prime numbers: $P=p_1\cdot p_2\cdots p_n$ . Let q = P+1: more than this product. Then, q is either prime or not.

If q is prime then the list is not exhaustive: q is not on it.

If q is not prime then some prime factor p divides q. This factor p is not on our list: if it were, 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. 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 the list is not exhaustive.

This proves, for any finite list of prime numbers, there is a prime number not on the list. Therefore there must be infinitely many prime numbers.

[edit] Euler's proof

Another proof, by the Swiss mathematician Leonhard Euler, relies on the fundamental theorem of arithmetic: that every number has a unique prime factorization. If P is the set of all prime numbers, Euler wrote that:

$\prod_{p\in P} \frac{1}{1-1/p}=\prod_{p\in P} \sum_{k\geq 0} \frac{1}{p^k}=\sum_n\frac{1}{n}.$

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.