I start this page with an apology: the short and elegant proof of the infinitude of primes that I am going to describe below is not mine, but I misplaced the source and cannot provide the reference. I'll be grateful for any suggestion.

For any integer n > 1, n and n+1 are coprime - mutually prime, having no common prime factors. So start with any n > 1 and write down one of its prime factors, say p. The prime factors of its successor, n + 1, are different from p. So there is at least some other prime, say q.

Now consider the successor of the product n(n + 1). The prime factors of the latter are different from those of n and n + 1, p and q, in particular. Let r be one of those.

Appply the same argument to the successor of n(n + 1)[n(n + 1) + 1] to obtain yet another prime, say s. Obviously the process can be extended indefinitely.

Copyright © 1996-2008 Alexander Bogomolny