Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
$$\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… – pedja Mar 22 '12 at 15:44
up vote 7 down vote accepted

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

share|cite|improve this answer
Thanks, Aryabhata! – euler'stotient Mar 22 '12 at 19:34
@euler'stotient: You are welcome! – Aryabhata Mar 22 '12 at 20:09

Your Answer


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.