Given $n$, calculate the sum $LCM(1,n) + LCM(2,n) + ... + LCM(n,n)$, where $LCM(i,n)$ denotes the Least Common Multiple of the integers $i$ and $n$.
In order to solve this problem, you need to know about Euler Phi Function, finding Divisor using Sieve and some properties of LCM and GCD.
Let us define a variable SUM which we need to find.
$SUM = LCM(1,n) + LCM(2,n) + ... + LCM(n,n)$ (take $LCM(n,n)$ to the other side for now )
$SUM - LCM(n,n) = LCM(1,n) + LCM(2,n) + ... + LCM(n-1,n)$
We know that $LCM(n,n) = n$.
$SUM - n = LCM(1,n) + LCM(2,n) + ... + LCM(n-1,n)$ ($eq 1$)
Reverse and Add
$SUM - n = LCM(1,n) + LCM(2,n) + ... + LCM(n-1,n)$ (Reverse $eq 1$ to get $eq 2$)
$SUM - n = LCM(n-1,n) + LCM(n-2,n) + ... + LCM(1,n)$ ( $eq 2$ )
No what will we get if we add $eq 1$ with $eq 2$? Well, we need to do more work to find that.
Sum of $LCM(a,n) + LCM(n-a,n)$
$x = LCM(a,n) + LCM(n-a,n)$
$x = \frac{an}{gcd(a,n)} + \frac{(n-a)n}{gcd(n-a,n)}$ ($eq 3$)
Arghh. Now we need to prove that $gcd(a,n)$ is equal to $gcd(n-a,n)$.
If $c$ divides $a$ and $b$, then, $c$ will divide $a+b$ and $a-b$. This is common property of division. So, if $g = gcd(a,n)$ divides $a$ and $n$, then it will also divide $n-a$. Hence, $gcd(a,n)=gcd(n-a,n)$.
So $eq 3$ becomes:
$x = \frac{an}{gcd(a,n)} + \frac{(n-a)n}{gcd(a,n)}$
$x = \frac{an + n^2 -an}{gcd(a,n)}$.
$x = \frac{n^2}{gcd(a,n)}$.
Now, we can continue adding $eq 1$ with $eq 2$.
Reverse and Add Continued
$SUM - n = LCM(1,n) + LCM(2,n) + ... + LCM(n-1,n)$ ($eq 1$)
$SUM - n = LCM(n-1,n) + LCM(n-2,n) + ... + LCM(1,n)$ ( $eq 2$ Add them )
$2(SUM-n)= \frac{n^2}{gcd(1,n)} + \frac{n^2}{gcd(2,n)} + ... \frac{n^2}{gcd(n-1,n)}$
$2(SUM-n ) = \sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)}$
$2(SUM-n ) = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$ ( take $n$ common )
Group Similar GCD
What are the possible values of $g = gcd(i,n)$? Since $g$ must divide $n$, $g$ needs to be a divisor of $n$. So we can list the possible values of $gcd(i,n)$ by finding the divisors of $n$.
Let $Z = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$. Now, every time $gcd(i,n) = d$, where $d$ is a divisior of $n$, $n \times \frac{n}{d}$ is added to $Z$. Therefore, we just need to find, for each divisor $d$, how many times $n \times \frac{n}{d}$ is added to $Z$.
How many values $i$ can we put such that $gcd(i,n) = d$? There are $\phi(\frac{n}{d})$ possible values of $i$ for which we get $gcd(i,n)=d$. Therefore:
$2(SUM-n ) = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$
$2(SUM-n ) = n\sum_{d\:|\:n, d \neq n } \phi(\frac{n}{d}) \times \frac{n}{d}$ (but, $\frac{n}{d}$ is also a divisor of $n$ )
$2(SUM-n ) = n\sum_{d\:|\:n, d \neq 1 } \phi(d) \times d$ ( when $d = 1$, we get $\phi(1)\times 1$ )
$2(SUM-n ) = n( \sum_{d\:|\:n } ( \phi(d) \times d ) -1 )$
$2(SUM-n ) = n \sum_{d\:|\:n } (\phi(d) \times d ) - n$
$2SUM - 2n + n = n\sum_{d\:|\:n } \phi(d) \times d $
$2SUM - n = n\sum_{d\:|\:n } \phi(d) \times d $
$$2SUM = n( \sum_{d\:|\:n } \phi(d) \times d )+ n \\2SUM = n ( \sum_{d\:|\:n } ( \phi(d) \times d ) + 1 )\\ \therefore SUM = \frac{n}{2} ( \sum_{d\:|\:n } ( \phi(d) \times d ) + 1 )$$
Using this formula we can solve the problem.
Code