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 \{p_1,\dots,p_n\} be the set of primes less than some number N. Pick a number x which is less than N. We can break up x into two parts:

  • Let a^2 be the largest square dividing x
  • Let b be x/a^2.
Though I didn’t seem to mention factoring x, we are using unique factorization here in a fundamental way. We know a few things. We know x is only divisible by the primes p_1,\dots,p_n, since all others are bigger than N. We know b is not divisible by any perfect squares, lest a^2 not be maximal.
How many posibilities are there for a and b? Since a^2\le x\le N, there are certainly no more than \sqrt N. For b, there can be no more than 2^n, as there are 2^n choices for the set of primes which divides b.
Each number less than N works like this, and so we get the inequality
N\le 2^n\sqrt N.
Solving for n, we get
n\ge\frac12\log_2N.
We now have a lower bound on the number of primes less than N. This lower bound grows towards infinity as N gets big, and so therefore, the number of primes must do so as well.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s