A short and elementary proof of the infinitude of primes
Discrete Mathematics and its applications
Teaching Mathematics and Its Applications
Volume 27 Issue 4
This article briefly discusses Euclid’s proof of the infinitude of primes (a proof by contradiction that makes use of the Divisibility Lemma), then provides a similar but distinctly different proof. Euclid’s proof is one that I often demonstrate to students of all levels, both for its simplicity and as an example of what a formal mathematical proof looks like. For many students, their only exposure to proofs comes in a high school geometry course where the proofs are hardly indicative of what mathematicians actually do.
The proof presented in this paper is technically incomplete, because it fails to provide the requisite proof by induction at the end. However, the practice of omitting minor steps is common where the intended audience is be able to fill in the details with little or no work. While this proof is not as elegant as Euclid’s, and does in fact require a slightly more sophisticated reader, the techniques are straightforward. This proof would be an excellent example for students in a discrete mathematics or abstract algebra class, especially when compared to Euclid’s own proof.
I found this proof quite a nice read.
