Finding $\sum_{i = 1}^{n} \frac{n} { \gcd(i, n)}$ I am trying to solve this problem, the most important part of this problem is to find
?$$\sum_{i = 1}^{n} \frac{n}{\gcd(i, n)}$$
Where $n$ could be $10^{12}$
 A: Let $C(n)$ be your sum, consider a fixed divisor $d$ of $n$; it will appear in the denominator whenever $i$ is a multiple of $d$ and $i/d$ is coprime with $n/d$ that is exactly $\varphi(n/d)$ times so the sum can be written as
$$ C(n) = \sum_{d \vert n} \frac{n}d \varphi(n/d) = \sum_{d \vert n} d \varphi(d) $$
Where the sum is over the positive divisors of $n$ and $\varphi(n)$ stands for (The Euler totient function). 
It is easy to prove that the function $C(n)$ is multiplicative (as it is any function of the form $\sum_{d\vert n} f(n)$ when $f(n)$ is a multiplicative function), so you can write it as 
$$\begin{aligned}  C(n) &= \prod_{p^\alpha \vert\vert n} C(p^\alpha) \\
&=\prod_{p^\alpha \vert\vert n} \sum_{d \vert p^\alpha} d\varphi(d)\\
&=\prod_{p^\alpha \vert\vert n} \sum_{j=0}^\alpha p^j \varphi(p^j)\end{aligned} $$
where the product is over the maximal prime powers dividing $n$.
but $\varphi(p^j) = p^j(1-1/p) $ so
$$ C(n) = \prod_{p^\alpha \vert\vert n}\left( 1+\sum_{j=1}^\alpha (p^{2j}-p^{2j-1})\right) $$
the sum inside the product is just:
$$ 1 - p + p^2 - p^3 +- \dots + p^{2\alpha} = \frac{p^{2\alpha+1}+1}{p+1}  $$
And so 
$$ \sum_{i=1}^n \frac{n}{\gcd(i,n)} = \prod_{p^\alpha\vert\vert n} \frac{p^{2\alpha+1}+1}{p+1} $$
