There are two extremely beautiful, fundamental theorems in mathematics — (1) the number of primes is infinite (2) the square root of 2 is irrational.
The oldest proof of the first theorem is due to Euclid. There is another proof of the first theorem due to Christian Goldbach (from a letter to Leonhard Euler, 1730). It is as follows: (Reference: Proofs from THE BOOK by Martin Aigner and Gunter M. Ziegler, fourth edition)
Let us look at Fermat Numbers for . We will show that any two Fermat numbers are relatively prime; hence, there must be infinitely many primes. To this end, we verify the recursion
from which our assertion follows immediately. Indeed, if m is a divisor of and (), then m divides 2, and, hence, . But, m=2 is impossible since all Fermat numbers are odd.
To prove the recursion, we use induction on n. For , we have and . With induction, we now conclude:
, which in turn, equals