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

• Are you assuming that Erdős decided to find a new proof of the infinitude of primes (why?), and then came up with this? Seems unlikely to me, too. Could it be that he was considering those products $m_1^2m_2$ for some other reason and happened to notice that they gave a new proof of the infinitude of primes? This is called serendipity. – bof May 6 '14 at 10:19
• I've heard Erdős was known for loving elegant proofs, and he would often talk about The Book or something like that. While I agree that you might be right (and if so I'd love to know what was he studying), I can perfectly imagine a mathematician trying to find an alternate proof for the same result. (I've came across at least 6 different proofs of the infinitude of primes, though they all seemed too advanced for me to remember or even understand. Hell, there's a book with 367 different proofs for the Pythagorean Theorem.) – Deathkamp Drone May 6 '14 at 16:49
• resembles a talk, perhaps a popular one for a mixed audience. – Will Jagy May 6 '14 at 17:28
• That book with 367 proofs is The Pythagorean Proposition by Elisha S. Loomis. – bof May 6 '14 at 21:42
• Since this is Erdős, I think it's worth considering that the idea for the proof might have come to suddenly and without explanation, from his subconscious. – rlms Sep 26 '14 at 13:36

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

• "[...] having finitely many primes is simply not enough to generate all the numbers". Yes, that has given me an intuition. And now I get the motivation too, which wasn't to prove that there are infinitely many primes (this was already known), but rather to estimate how many primes there are up to a certain $n$. Perfect. – Deathkamp Drone Mar 28 '16 at 10:59