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}$.

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

  • $\begingroup$ @euler'stotient: You are welcome! $\endgroup$ – Aryabhata Mar 22 '12 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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