elementary number theory - Question about Paul Erdős’ proof on the infinitude of primes

I was reading Julian Havil’s book Gamma where he talks about a short proof by Paul Erdős on the infinitude of primes.

As I understand it, here are the steps:

(1) Let $N$ be any positive integer and $p_1, p_2, p_3, \dots, p_n$ be the complete set of primes less than or equal to $N$

(2) Each $1 \le x \le N$ can be written as $p_1^{e_1}p_2^{e_2}p_3^{e_3}\ldots p_n^{e_n} \times m^2$ where $e_i \in \left\{0,1\right\}$

(3) So, there are $2^n$ ways of choosing square-free numbers and $m^2 \le N$

(4) Since $m \le \sqrt{N}$, each $2 \le x \le N$ can be chosen in at most $2^n \times \sqrt{N}$ ways.

(5) Thus, $N \le 2^n \times \sqrt{N}$ and $2^n \ge \sqrt{N}$ so that $n \ge \dfrac{1}{2}\log_2 N$

I am confused by step #4. Why does it follow that $x$ can be chosen in at most $2^n \times \sqrt{N}$ ways. I would think that it would be chosen in $2^n \times m^2$ ways. Why is he allowed to replace $m^2$ with $m$ in this case?

---

Edit: I figured out my misunderstanding.

When I reread the proof in the book this morning, I noticed the following sentence in the paragraph before the proof:

"In 1938 the consummate practitioner Paul Erdos (1913-1996) gave the
one that follows, which uses a counting technique and a neat device

used by number theorists: that any integer can be written as the
product of a square and a square-free integer"

This device is easily proven. Let $u = p_1^{e_1}p_2^{e_2}\ldots p_n^{e_n}$ so that for any $x \le N$, $x = um^2$:

• Let $p^v | x$ where $p^{v+1} \nmid x$ and $v \ge 1$


• If $v \equiv 0 \pmod 2$, then $p \nmid u$ and $p^v | m^2$


• If $v \equiv 1 \pmod 2$, then $p | u$ and $p^{v-1} | m^2$

So that it follows that $m$ is an integer. Now, the full proof works for me.

Answer

The number of values $m^2$ can have is given by $m$. If you used $m^2$, it would look as if it could have any value from $1$ to $m^2$, which isn't true.

You "replace" $m^2$ by $m$ in the same sense you replaced $p_1^{e_1}\ldots p_n^{e_n}$ by $2^n$ (and not by $p_1\ldots p_n$).