# Another proof due to Erdős

In fact, we can do better than just “there are infinitely many primes.” Sometimes there are infinitely many numbers, but the sum of there reciprocals is convergent because they get big fast. For instance, there are infinitely many factorials $0!, 1!, 2!, 3!\dots$, but the sum of the reciprocals is still convergent:

$\sum\frac{1}{k!}=e=2.71828\dots$.

But certainly if the sum was divergent, there would have to be infinitely many terms in the sum. Let $S$ denote

$S=\sum\frac1p$

the sum of the reciprocals of the primes. We’re going to show that $S=\infty$. If it were convergent, we could get rid of the first some number of terms, and end with a sum less than, say, $1/2$.

$S_N=\sum_{p\ge N}\frac1p<\frac12$.

Call a prime big if it appears in the sum $S_N$. Call it small if it doesn’t.

Now pick your favorite number $M$, and partition $\{1,2,\dots,M\}$ into two sets. The first set, $A$ will be all the numbers less than or equal to $M$ divisible by small primes only. The second set, $B$ will be those numbers divisible by some big prime.

Let’s deal with the big primes first. For any prime $p$, there are no more than $M/p$ numbers in $\{1,2,\dots,M\}$ divisible by $p$. Ignoring the gratuitous amounts of double counting we’ll be doing, we can very safely bound the size of $B$ by

$\left|B\right|\le\displaystyle\sum_{p\ge N}\frac Np<\frac N2$.

For the set $A$, we use a bound similar to what we used last time. For each $a\in A$, write $a=b^2c$ where $c$ is square-free. (i.e., not divisible by any perfect squares other than $1$). Clearly $c$ is the product of small primes, of which there are some fixed number $k$. This gives us $2^k$ choices for $c$. For $b$, it certainly can’t be any bigger than $\sqrt M$, so

$\left|A\right|\le 2^k\sqrt M$.

But our choice of $M$ was totally independent of our choice for $N$ and $k$. So let’s just pick $M$ to be super big. By super big, I mean big enough so that $2^k\sqrt M. Something like $M> 2^{2^{2^k}}\cdot(k!)!^{k!^2}$ should probably do the trick. But now we have a problem:

$M=\left|A\right|+\left|B\right|.

This is a contradiction, so the sum of the reciprocals of the primes diverges, and therefore, there are infinitely many of them.