Given an integer $n$, How do we find $$S=\text{lcm}(1,n) + \text{lcm}(2,n) +\ldots+ \text{lcm}(n,n)$$ I know how find the $\gcd$ sum $$\gcd(1,n) + \gcd(2,n) +\cdots+\gcd(n,n)$$ Because there is $$\sum{\phi(\frac{n}{i}) * i}$$ where $i|n$. But how do I use it to calculate $\text {lcm}$ ?
I found a formula googling here . But there is no proof there, and the research paper journal is unreadable for me (i.e I can't understand the hard mathy notations). So it would be helpful if someone could explain how this formula came.