# On sums involving Euler's totient function

I've been struggling with the following claim without being able to prove it, so your help would be highly appreciated:

Let $\varphi(n)$ be Euler's totient function. Show that there is a constant $0<K$ such that for any natural number $N$, $KN\leq\frac{\varphi(1)}{1}+\frac{\varphi(2)}{2}+...+\frac{\varphi(N)}{N}$.

-
$$\varphi(N)>\frac{N}{e^{\gamma} \cdot \ln (\ln N)+\frac{3}{ \ln (\ln N)}}$$ , for $N>2$ –  pedja Mar 22 '12 at 14:59
@pedja: What is $\gamma$, and how did you get this inequality? –  euler'stotient Mar 22 '12 at 15:29
That's the Euler-Mascheroni constant. –  anon Mar 22 '12 at 15:40
en.wikipedia.org/wiki/… –  pedja Mar 22 '12 at 15:44

We have that

$$\sum_{k=1}^{n} \frac{\varphi(k)}{k} \ge \sum_{k=1}^{n} \left(\left[\frac{n}{k}\right]\frac{k}{n}\right)\frac{\varphi(k)}{k}$$

$$= \frac{1}{n} \sum_{k=1}^{n} \left[\frac{n}{k}\right]\varphi(k) = \frac{n+1}{2}$$

Thus you can choose $K = \frac{1}{2}$.

The last step uses the identity:

$$\sum_{k=1}^{n} \left[\frac{n}{k}\right]\varphi(k) = \frac{n(n+1)}{2}$$

and the first inequality uses $\left[\frac{n}{k}\right] \le \frac{n}{k}$, where $[x]$ gives the integer part of $x$.

Multiple proofs of the last identity can be found here: Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$

-
Thanks, Aryabhata! –  euler'stotient Mar 22 '12 at 19:34
@euler'stotient: You are welcome! –  Aryabhata Mar 22 '12 at 20:09