# 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.