In today's blog, I will present a very well known proof. What makes this proof especially appealing is that it is not too complex. Even so, it is very powerful. This theorem was first presented in Euclid's Elements (Book IX, Proposition 20).
Theorem: There are an infinite number of primes.
Proof:
(1) Assume that there is only a finite number of primes.
(2) Then, there exists a prime pn that is the largest prime.
(3) Let p1, p2, ..., pn be the list of all primes that exist.
(4) Let x = p1*p2*...*pn + 1.
(5) By the fundamental theorem of arithmetic (see Theorem 3, here), we know there is at least one prime that divides x. Let us call this prime p*.
(6) But none of the primes p1 ... pn divide x since x ≡ 1 (mod pi) for any of the primes p1 ... pn
(7) Therefore, we have a contradiction. We have a prime p* that is not in the complete list of primes.
(8) So, we reject our assumption in step#1 and conclude that there are an infinite number of primes that exist.
QED
