Understanding formula for $\sum_{i = 1}^{n}LCM(n,i)\ $

Question

Let $A_n = \sum_{i = 1}^{n}LCM(n,i)\ $ where $LCM\ $ is the Least Common Multiple. http://oeis.org/A051193 here is a formula for calculating $A_n$.

$$A_n = \frac{n}{2}(1+\sum_{d|n}{d\varphi(d))} $$

Where $\varphi(d)$ Euler's totient function. I need hint to understand how this formula works.

Answer 1

Let $(n,i)=d,i=dk,(k,\frac{n}d)=1,\dfrac{i}{(n,i)}=k,$

$$A_n=\sum_{i = 1}^{n}LCM(n,i)=\sum_{i=1}^{n}\dfrac{ni}{(n,i)} \\=n\sum_{i=1}^{n}\dfrac{i}{(n,i)}=n\sum_{d\mid n}\sum_{(k,\frac{n}d)=1,k\leq \frac{n}d}k \\=\frac{n}2(1+\sum_{d\mid n}\sum_{(k,\frac{n}d)=1,k\leq \frac{n}d}k+(\frac{n}d-k)) \\=\frac{n}2(1+\sum_{d\mid n}\sum_{(k,\frac{n}d)=1,k\leq \frac{n}d}\frac{n}d) \\=\frac{n}2(1+\sum_{d\mid n}\frac{n}d\phi(\frac{n}d)) \\=\frac{n}2(1+\sum_{d\mid n}d\phi(d))$$