On the infinitude of primes – Erdős’s proof

In the book “Proofs from THE BOOK”, there are 6 proofs on the infinitude of primes. All of them are very elegant and beautiful but I really liked the reasoning behind the following one, coined by Paul Erdos.

We shall prove that the series

$\sum\limits_{p \in \mathbb{P}}\frac{1}{p}$

diverges. That would imply that the set of prime numbers in infinite because otherwise their sum would converge.

Let $\{p_i\}_{i \in \mathbb{N}}$ be the sequence of primes numbers written in increasing order.

Assume that the series above converges. Then, there must exist some number $k$ such that

$\sum\limits_{i \geq k+1}\frac{1}{p_i} < \frac{1}{2}$

Call the primes $p_i$ for $1 \leq i \leq k$ the small primes and the rest the big primes.

For any natural number $N$ , it must then hold that

$\boxed{\sum\limits_{i \geq k+1}\frac{N}{p_i} < \frac{N}{2}}$

Now, let $N_b$ be the number of positive integers $n \leq N$ which are divisible by at least one big prime and let $N_s$ be the number of positive integers less than or equal to $N$ whose prime divisors are all small primes.

We will show that $N_b+N_s < N$ , thus arriving at a contradiction (it should be $N_b+N_s = N$ .

First, note that $\lfloor\frac{N}{p_i}\rfloor$ counts the number of positive integers less than or equal to $N$ that are multiples of $p_i$ .

We have that

$N_b \leq \sum\limits_{i \geq k+1}\lfloor\frac{N}{p_i}\rfloor < \frac{N}{2}$

and this equation allows us to estimate $N_b$ . For $N_s$ , let $n \leq N$ be a positive integer whose prime divisors are all small primes. Let $n = a_n b_n^2$ , where $a_n$ is not a square of an integer. Since $a_n$ cannot contain the same small prime number twice in its prime factor decomposition, it can take exactly $2^k$ values. And given that $b_n \leq \sqrt{N}$ , we have that