Erdős's proof of the divergence of the sum of the reciprocals of the primes

Proof

We argue by contradiction and count the integers up to $x$ in two ways.

1. By Euclid's theorem, there are infinitely many prime numbers. List them in increasing order as $p_1 < p_2 < p_3 < \cdots$.
2. For $j \ge 1$, put $s_j = \sum_{i=1}^{j} 1/p_i$. Every partial sum $\sum_{p \le x} 1/p$ equals some $s_j$ or $0$, and every $s_j$ is such a partial sum.
3. Suppose the partial sums are bounded. Then the set $\set{s_j : j \ge 1}$ is bounded above. By the completeness axiom, it has a supremum $L$.
4. By the approximation property of the supremum, there is an index $k$ with $s_k > L - 1/2$.
5. For every $j > k$, we get $\sum_{i=k+1}^{j} 1/p_i = s_j - s_k < L - (L - 1/2) = 1/2$, because $s_j \le L$.
6. Put $x = 2^{2k+2}$. Let $M$ be the set of integers $n$ with $1 \le n \le x$ such that no prime $p_i$ with $i > k$ divides $n$.
7. Upper estimate. Let $n \in M$. By the square times square-free decomposition, $n = m^2 r$ with positive integers $m$, $r$ and $r$ square-free.
8. Every prime that divides $r$ divides $n$, so it is one of $p_1, \dots, p_k$.
9. By the existence of prime factorization, $r$ is a product of primes. No prime occurs twice, since then its square would divide $r$.
10. So $r$ is the product of a subset of $\set{p_1, \dots, p_k}$. There are $2^k$ subsets, so $r$ takes at most $2^k$ values.
11. Also $m^2 \le n \le x$, so $m \le \sqrt{x} = 2^{k+1}$. So $m$ takes at most $2^{k+1}$ values.
12. The pair $(m, r)$ determines $n$. Hence $|M| \le 2^k \cdot 2^{k+1} = 2^{2k+1} = x/2$.
13. Lower estimate. Let $1 \le n \le x$ with $n \notin M$. Then some $p_i$ with $i > k$ divides $n$, and $p_i \le n \le x$.
14. Let $J$ be the largest index with $p_J \le x$. If $J \le k$, no such $n$ exists, and $|M| = x > x/2$.
15. If $J > k$, each such $n$ is a multiple of some $p_i$ with $k < i \le J$. The number of multiples of $p_i$ in $\set{1, \dots, x}$ is at most $x / p_i$.
16. So $x - |M| \le \sum_{i=k+1}^{J} x / p_i = x \sum_{i=k+1}^{J} 1/p_i < x/2$ by step 5. Hence $|M| > x/2$.
17. Steps 12, 14 and 16 give $x/2 < |M| \le x/2$, which is a contradiction.
18. So the partial sums $\sum_{p \le x} 1/p$ are not bounded, and the series $\sum_p 1/p$ diverges.