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 and ? Since , there are certainly no more than . For , 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

.

Solving for , 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.

About these ads