$$\sum_{i=1}^n \frac{n}{gcd(i,n)} = \sum_{d|n} d\times\phi(d) $$
Where $\phi(d)$ is the Euler totient function of d. I want to prove it using Mobius Inversion formula. Please give a formal step by step proof. And I want to mention that I came across this formula in this programming question SimpleSum
If $i\in[1,n]$ the value of $\gcd(i,n)$ can only be a divisor of $n$. If we fix some $d\mid n$, how many $i\in[1,n]$ are such that $\gcd(i,n)=d$? As many as the numbers $\leq \frac{n}{d}$ and coprime with $\frac{n}{d}$. It follows that
$$ F(n)=\sum_{i=1}^{n}\frac{n}{\gcd(i,n)} = \sum_{d\mid n}\frac{n}{d}\cdot\varphi\left(\frac{n}{d}\right) = \sum_{d\mid n} d\cdot\varphi(d) $$ where the last equality follows by switching to complementary divisors $d\leftrightarrow\frac{n}{d}$.
The RHS is a multiplicative function: for any prime power we have $$ F(p^m) = 1+\sum_{k=1}^{m} p^{2k-1} (p-1) $$ hence $$ F(n) = \prod_{p\mid n}\frac{p^{2\nu_p(n)+1}+1}{p+1}. $$