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.
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.
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.