Finding $\sum_{i = 1}^{n} \frac{n} { \gcd(i, n)}$

Question

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}$

Answer 1

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} $$