Let $(n,k)=\gcd(n,k)$ and $(n,l,k) = \gcd(\gcd(n,l),k)$, $\sigma(n)=$ sum of divisors of $n$. My question is, how the "ugly" identity, which I can prove it is true, can be "simplified" in presentation?:
$$\sigma(n) = \sum_{k=1}^{n-1}\frac{\sigma((n,k))}{n-1}+\frac{n}{n-1}\sum_{l=1}^{n-1}\sum_{k=1}^{(n,l)}\frac{\sigma((n,l,k))}{(n,l)}$$
Note, that the interesting part for this identity is, that we compute $\sigma(n)$ using only numbers $x<n$ and $\sigma(x)$.
Thanks for your help.
Best Answer
Swapping your use of $k$ and $l$ in the second term gives
$$\sigma(n) = \sum_{k=1}^{n-1}\frac{\sigma((n,k))}{n-1}+\frac{n}{n-1}\sum_{k=1}^{n-1}\sum_{l=1}^{(n,k)}\frac{\sigma((n,k,l))}{(n,k)}$$
Multiplying by $n-1$,
$$(n-1)\sigma(n)=\sum_{k=1}^{n-1}\left(\sigma((n,k))+n\sum_{l=1}^{(n,k)}\frac{\sigma((n,k,l))}{(n,k)}\right)$$
By taking the sum up to $k=n$ rather than $k=n-1$ we get
$$n\sigma(n)+\sum_{l=1}^{n}\sigma((n,l))=\sum_{k=1}^{n}\left(\sigma((n,k))+n\sum_{l=1}^{(n,k)}\frac{\sigma((n,k,l))}{(n,k)}\right)$$
Then after getting rid of the redundant terms and dividing both sides by $n$ we have
$$\sigma(n)=\sum_{k=1}^{n}\sum_{l=1}^{(n,k)}\dfrac{\sigma((n,k,l))}{(n,k)}$$