Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

1 Answer

  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.
share|improve this answer
    
I don't understand your 2. and 3. , can you elaborate a little bit please ? :D –  YoAsakura Mar 15 '12 at 22:01
    
I'll try. I need to go home and eat dinner first. –  deinst Mar 15 '12 at 22:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.