The question I'm trying to solve is

$\sum_{n \le N} \phi(n) \lfloor \frac {N}{n} \rfloor $ = $\frac {N(N+1)}{2}$

for all natural numbers N where $\phi$ is Euler's totient function.

This is how far I've gotten:

$\sum_{n \le N} \phi(n) \lfloor \frac {N}{n} \rfloor $ = $\sum_{n \le N} \phi(n)$$\sum_{k \le \frac {N}{n}} 1$ = $\sum_{N \le k} \sum_{n|N} \phi (n)$ = $\sum_{N \le k} N$

Any suggestions or answers are very appreciated!


You've made a good start writing

$$\biggl\lfloor \frac{N}{n}\biggr\rfloor = \sum_{k \leqslant N/n} 1,$$

but when you changed the order of summation you made a mistake. Just changing the order of summation would lead to

$$\sum_{n \leqslant N} \phi(n)\biggl\lfloor \frac{N}{n}\biggr\rfloor = \sum_{k \leqslant N} \sum_{n \leqslant N/k} \phi(n),$$

which doesn't make it obvious how to reach the goal either. The goal is reached by writing $m = n\cdot k$ and summing over $m$:

$$\sum_{n \leqslant N} \phi(n)\biggl\lfloor \frac{N}{n}\biggr\rfloor = \sum_{m \leqslant N} \sum_{n\cdot k = m} \phi(n)\cdot 1 = \sum_{m \leqslant N} \sum_{n \mid m} \phi(n) = \sum_{m \leqslant N} m = \frac{N(N+1)}{2}\,.$$

  • $\begingroup$ thanks for the correction. I still don't know how to get it from the double sum to the final result, could you help me with the last step as well? $\endgroup$ – vfantina Mar 26 '18 at 15:07
  • $\begingroup$ You have seen $\sum_{n \mid m} \phi(n)$ before. You just need to remember what it was. It may help to think about what $h(m)$ must be for $\sum_{m \leqslant N} h(m) = \frac{1}{2}N(N+1)$. $\endgroup$ – Daniel Fischer Mar 26 '18 at 15:10
  • $\begingroup$ What I think I have at this point is $\sum_{m \le N} m$ so I assume that has to equal $\frac{N(N+1)}{2}$ $\endgroup$ – vfantina Mar 26 '18 at 15:20
  • $\begingroup$ Indeed. That's a rather famous formula. Is it more familiar when written $$\sum_{m = 1}^N m = \frac{N(N+1)}{2}\,?$$ $\endgroup$ – Daniel Fischer Mar 26 '18 at 15:24

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.