Euclidean prime number theorem

The set of prime numbers is infinite (Euclid's Elements, Book IX, Prop. 20). The Chebyshev theorems on prime numbers and the asymptotic law of the distribution of prime numbers provide more precise information on the set of prime numbers in the series of natural numbers.

Comments[edit]

The proof of the Euclidean theorem is simple. Suppose there exist only finitely many prime numbers $p_1,\dotsc,p_k$. Consider the number $N=p_1\dotsm p_k+1$. Since $N>1$ it must be divisible by a prime number $p$, which equals some $p_i$ due to the finiteness of the amount of prime numbers. Hence $p=p_i$ divides $N=p_1\dotsm p_i\dots p_k+1$, and thus $p_i$ divides 1. This contradiction shows that there must be infinitely many prime numbers.