$\sum_{i=1}^n \frac{n}{\text{gcd}(i,n)}.$

Question

Find the value of this series:

$$\sum_{i=1}^n \frac{n}{\text{gcd}(i,n)}.$$

Answer 1

For each divisor $d$ of $n$ there are exactly $\phi\left(\frac nd\right)$ terms in the sum whose value is $\frac nd$, so

$$\sum_{j=1}^n\frac n{(j,n)}=\sum_{d\mid n}\frac nd\phi\left(\frac nd\right)=\sum_{d\mid n}d\phi(d)=\sum_{d\mid n}\phi(d^2)$$