Infinitude of Primes via Coprime Pairs
For any integer \(n \gt 1\), \(n\) and \(n+1\) are coprime - mutually prime, having no common prime factors. So start with any \(n \gt 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.
(I am grateful to Jens Bossaert for pointing out the source of the proof. The proof is due to Filip Saidak, a mathematician at the University of North Carolina. Much later I found in Victor Moll's book a generalization that I placed on a separate page.)
- V. H. Moll, Numbers and Functions: From a Classical-Experimental Mathematician's Point of View, AMS, 2012, 26-27
- F. Saidak, A New Proof of Euclid's Theorem, The American Mathematical Monthly, Vol. 113, No. 10 (Dec., 2006), 937-938
Copyright © 1996-2018 Alexander Bogomolny