14
$\begingroup$

There is a second part of the problem posted in Proving $ \frac{\sigma(n)}{n} < \frac{n}{\varphi(n)} < \frac{\pi^{2}}{6} \frac{\sigma(n)}{n}$, from Apostol's book, but I can't figure it out. It asks the reader to prove that if $x \geq 2$ then $\sum\limits_{n\leq x} \frac{n}{\phi(n)} = O(x)$, where the right hand side of the equation uses the Big-O notation. I've tried using the prior result, but I always end up with $O(x^2)$ . Any insights?

  • 0
    You can improve on your $\mathcal{O}(x^2)$ bound to $\mathcal{O}(x^{1.5})$ by making use of the fact that $\phi(n) \geq \sqrt{n}$ for $n > 6$2011-11-22

3 Answers 3