#### Andy Soffer

UCLA Mathematics Ph.D Student

# A proof from Erdős

May 16, 2012

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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 29, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9547980427742004, "perplexity_flag": "head"}