# Three step proof of the divergence of $\sum_{p\in \mathbf{P}} \frac{1}{p}$

In my Number Theory skript it says:

1. By showing that there are at most $(1+\frac{\log n}{\log 2})^{\pi(x)}$ numbers with $m\le n$ which are divisible only by prime numbers $p\le x$.

2. By showing that there are at most $\sum_{x<p\le n} \frac{n}{p}$ numbers $m\le n$ which are divisible by at least one prime with $p\le x$.

3. With 1. and 2. we can conclude that $\sum_{p\in \mathbf{P}} \frac{1}{p}$ is divergent by otherwise choosing x with $\sum_{p>x} \frac{1}{p} < \epsilon \le \frac{1}{2}$ and then $n\le (1+\frac{\log n}{\log 2})^{\pi (x)} + \epsilon n$ follows for all n.

How can we show 1. and 2. ? And how does my professor conclude in 3?

-
I think the second inequality in 2. is backwards. It should read "By showing that there are at most $\sum{x<p\le n}\frac{n}{p}$ numbers $m\le n$ which are divisible by at least one prime with $p \ge x$." – deinst Mar 15 '12 at 20:17

1. A number less than $n$ has fewer than $(1+\frac{\log n}{\log2})$ prime factors (each prime factor is at least 2) and there are at most $\pi(x)$ choices for each prime factor.
2. There are $\lfloor\frac{n}{p}\rfloor$ numbers divisible by $p$, so there are at most $\sum_{x<p\le n}\frac{n}{p}$ with a prime factor greater than or equal to $x$ as $\lfloor\frac{n}{p}\rfloor\le\frac{n}{p}$.
3. The numbers less than $n$ can be divided into two groups, Those having a prime factor greater than $x$ and those having all prime factors less than $x$. For the first group, by 2. we get that there are at most
$$\sum_{x<p\le n}\frac{n}{p}=n\sum_{x<p\le n}\frac{1}{p}<\epsilon n$$ numbers having a prime factor greater than $x$. For the second group, by 1. we know that there are at most $(1+\frac{\log n}{\log 2})^{\pi(x)}$ numbers having no prime factor greater than $x$. So as there are $n$ positive integers at most $n$, we have that $n<(1+\frac{\log n}{\log 2})^{\pi(x)}+\epsilon n$. To see that this proves that the sum of $\frac{1}{p}$ diverges note that for a fixed $x$, $(1+\frac{\log n}{\log 2})^{\pi(x)}$ is $o(n)$, so for large enough $n$ $n>(1+\frac{\log n}{\log 2})^{\pi(x)}+\epsilon n$ if $\epsilon \le\frac{1}{2}$, so we cannot find an $x$ such that $\sum_{p>x}\frac{1}{p}<\frac{1}{2}$. In other words $\sum_{p\in P}\frac{1}{p}$ diverges.