Summation question with Euler's totient function

Question

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!

Answer 1

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