How to find this LCM sum function? $\text{lcm}(1,n) +\text{lcm}(2,n) +\cdots+\text{lcm}(n,n)$

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.

• You could perhaps try $lcm(a,b)=\frac{ab}{gcd(a,b)}$. – rah4927 Apr 20 '14 at 13:15
• I know that, but for this I have to iterate through all the integers 1...n . – Tamim Addari Apr 20 '14 at 13:18
• Well,it perhaps gives us a start,for there are $\phi(n)$ numbers with the denominator 1. – rah4927 Apr 20 '14 at 13:26
• ϕ(n) numbers with denominator 1, but to find the sum , I have to know all the a's , right? – Tamim Addari Apr 20 '14 at 13:33

Lemma 1: $\operatorname{lcm}(a, n) + \operatorname{lcm} (n-a, n) = \frac{ an } { \gcd(a, n)} + \frac{ (n-a)n} { \gcd(n-a, n)} = \frac{ n\times n} { \gcd(a,n) }$.

Lemma 2: $\sum \frac{n}{\gcd(a,n)} = \sum_{f \mid n} \frac{n}{f} \times \phi(\frac{n}{f} ) = \sum_{d\mid n} d\phi(d)$,

Proof: consider what happens if $\gcd(a,n) = f \mid n$. It appears $\phi(\frac{n}{f})$ times on the LHS, and each time it has value of $\frac{n}{f}$. Now substitute $d = \frac{n}{f}$, which is also a divisor of $n$.

Now, to your problem, pull out $\operatorname{lcm}(n,n) = n$.

We have $2 \sum_{a=1}^{n-1} \operatorname{lcm}(a,n) = \sum \left[\operatorname{lcm}(a,n) + \operatorname{lcm} (n-a, n) \right] = n \sum \frac{n}{\gcd(a,n)} = n \times \sum_{d\mid n} d\phi(d).$

Add back $\operatorname{lcm}(n,n)=n$, and you get the formula in OEIS.

• To understand why $\gcd(a,n) = f$ , (where $f \mid n$) occurs $\phi (\frac{n}{f})$ times on the LHS - consider $\gcd(\frac{a}{f},\frac{n}{f}) = 1$ : we know this happens $\phi (\frac{n}{d})$ (definition of the Totient function). If we multiply by $f$ throughout, we get $\gcd(a,n) = f$ , which has the same number of solutions as $\gcd(\frac{a}{f},\frac{n}{f}) = 1$ , and hence ,same as $\phi (\frac{n}{d})$. – GiriB Sep 20 '16 at 13:46
• Could anybody explain how does +1 come in the formula. Is this the cause, we have to discard value for d = 1? But why? – iamcrypticcoder Feb 25 at 11:21