soft question - Intuition behind Erdős proof of the infinitude of prime numbers

Suppose by contradiction that there are finitely many primes, namely $p_1, p_2,...,p_k$, where $k$ is a natural number. Now consider another natural number $n$, and all natural numbers $m \leq n$. We can write every $m$ as a product $m_1^2m_2$, where $m_1 \in \mathbb{N}$ and $m_2 \in \mathbb{N}$ is a square-free integer. Now, using some simple combinatorics arguments and the FTA it's easy to see that there are at most $2^k\left \lfloor \sqrt{n} \right \rfloor$ ways to write the product $m_1^2m_2$, and so we can conclude that

$$n \leq 2^k\sqrt{n}$$
which is absurd, since the inequality does not hold for large $n$.

This is a version proof of the proof given by P. Erdős of the infinitude of the prime numbers. (as I remember it.)

I have no problems understanding the proof itself. What bothers me is that while both this and Euclid's proof (I believe we all know that one) are very beautiful, this one seems a little bit mysterious to me, while the Euclid's one, albeit very ingenious, was quite natural.

I know some of the beauty of it is because of the very fact that it is unexpected and elusive. But if one is trying to prove the infinitude of the prime numbers, why would they think of the product $m_1^2m_2$? Why would this even help? Was Erdős just trying a bunch of different ideas randomly until he got one that worked (which I find very unlikely), or there is a motivation for considering the factorization $m_1^2m_2$?

I'm sorry if I didn't make myself clear, or if this question is not suitable for this website.

Answer

The intuition that I see is to show that having finitely many primes is simply not enough to generate all the numbers. More precisely, this gives a lower bound on the number of primes below a certain size (a lower bound on $\pi(n)$ as a function of $n$), which is more informative than simply saying $\pi(n) \to \infty$ as $n \to \infty$. Getting this lower bound is a good motivation for going beyond Euclid's proof.

Suppose we have finitely many primes $p_1, p_2, \dots, p_k$, then every number can be expressed as $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ for some exponent vector $(e_1, \dots, e_k)$ with all components nonnegative integers. Unfortunately there are infinitely many possibilities for each $e_i$ so this doesn't let us control anything.

On the other hand, if each $e_i$ were either $0$ or $1$ (i.e. we only looked at products of distinct primes), then there are only $2^k$ possible products. Numbers that are products of distinct primes (there is never an $i$ with $e_i \ge 2$) are called square-free integers. For any number we can pull out the squares in it and leave a square-free part. This is well-known in elementary number theory, and was not introduced by Erdős; there's even an MathWorld entry about squarefree part.

For any integer $n$ and any integer $m \le n$, if we write $m$ as a squarefree part $r$ times a square $s^2$ (i.e. $m = s^2 r$) then as $s^2 \le N,$ we have $s \le \sqrt{N}$. At the same time, as there are only $2^k$ possible exponent vectors $(e_1, \dots, e_k)$, there are only $2^k$ possible values for $r$. This gives

$$n \le 2^k \sqrt{n}.$$

In the question you have used this to conclude that $k$ cannot be finite (thus proving that there are infinitely many primes), but the more useful consequence is that the number of available primes $k$ should satisfy $2^k\sqrt{n} \ge n$, i.e.

$$\pi(n) \ge \lg\sqrt{n}.$$

(The real bound is much better; the prime-number theorem says $\pi(n)$ grows as $n/\log n$.)

I don't know if I have given you any intuition or just restated the proof. :-)