4
$\begingroup$

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.

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

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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})$. $\endgroup$ – GiriB Sep 20 '16 at 13:46
  • $\begingroup$ Could anybody explain how does +1 come in the formula. Is this the cause, we have to discard value for d = 1? But why? $\endgroup$ – iamcrypticcoder Feb 25 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.