4
$\begingroup$

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 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?

  • 1
    I think the second inequality in 2. is backwards. It should read "By showing that there are at most \sum{x numbers $m\le n$ which are divisible by at least one prime with $p \ge x$."2012-03-15

1 Answers 1

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