# Sum of GCD(k,n)

I want to find this

$$\sum_{k=1}^n \gcd(k,n)$$

but I don't know how to solve. Does anybody can help me to finding this problem.

Thanks.

• Do you know how many integers $k$ in the range $1 \leq k \leq n$ are relatively prime to $n$ so that $\gcd(k,n) = 1$? (Hint: Read about Euler's totient function.) – Dilip Sarwate Apr 22 '12 at 16:03
• n $\leq$ 200000. Ok I will read Euler's totient function. – Elmi Ahmadov Apr 22 '12 at 16:32

## 1 Answer

This is Pillai's arithmetical function as in OEIS A018804

Formulae given there include $$\sum_{d|n} d \,\phi(n/d)$$ and $$\sum_{d|n} d \, \tau(d) \, \mu(n/d)$$ where $\phi(n)$ is Euler's totient function, $\tau(n)$ is the number of divisors and $\mu(n)$ is the Möbius function.