Intuition behind Erdős proof of the infinitude of prime numbers

Solution 1:

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. :-)