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.

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|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
    
en.wikipedia.org/wiki/… –  pedja Mar 22 '12 at 15:44

1 Answer 1

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

 
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.