A proof from Erdős
I have a friend from HCSSiM who reminded me of this proof, and a few others, that he put together for MIT Splash. Thanks Ben!
Let be the set of primes less than some number . Pick a number which is less than . We can break up into two parts:
- Let be the largest square dividing
- Let be .
Though I didn’t seem to mention factoring , we are using unique factorization here in a fundamental way. We know a few things. We know is only divisible by the primes , since all others are bigger than . We know is not divisible by any perfect squares, lest not be maximal.
How many posibilities are there for
, there are certainly no more than
, there can be no more than
, as there are
choices for the set of primes which divides
Each number less than
works like this, and so we get the inequality
, we get
We now have a lower bound on the number of primes less than
. This lower bound grows towards infinity as
gets big, and so therefore, the number of primes must do so as well.