How do I simplify $\sum_{k=1}^n \gcd(k,n)$? For a given positive integer $n$, how do I simplify $$\sum_{k=1}^n \gcd(k,n)?$$
By simplification I mean is there any formula which makes it easier to compute it (rather than just compute each term and sum up)?
 A: Just as a complement to other answers, we may notice that the arithmetic function
$$ S(n)=\sum_{d\mid n}d\cdot\varphi\left(\frac{n}{d}\right) = (\text{Id}*\varphi)(n) $$
is a multiplicative function, since it is the Dirichlet's convolution between two multiplicative functions. So in order to compute $S(n)$ for any $n\geq 1$, it is enough to compute $S(p^k)$ when $p$ is a prime number:
$$ S(p^k) = \sum_{j=0}^{k} p^{k-j} \varphi(p^{j}) = p^k+(p-1)\sum_{j=1}^{k}p^{k-j}p^{j-1}=p^k+k(p-1)p^{k-1}$$
and:
$$ S(n) = n\prod_{p\mid n}\left[1+\nu_p(n)\left(1-\frac{1}{p}\right)\right].$$
A: $\renewcommand{\phi}{\varphi}$Use the following two facts


*

*if $G$ is a multiplicative group of order $n$, generated by $g$, and $k$ is an integer, then the order of $g^{k}$ is 
$$
\frac{n}{\gcd(n, k)}
$$

*in a cyclic group $G$ of order $n$, there are $\phi(d)$ elements of order $d$, for each divisor $d$ of $n$


Let $D$ be the set of positive divisors of $n$. Let $d \in D$, so that also $n/d \in D$. In the summation 
$$\sum_{k=1}^n \gcd(k,n)$$
we get a term $n/d$ every time that $g^{k}$ has order $d$ in a cyclic group $\langle g \rangle$ of order $n$, so $\phi(d)$ times.
Your summation becomes
$$
\sum_{d \in D} \phi(d) \frac{n}{d}.
$$
But perhaps this is not that much better than the original. Although, as suggested in a comment below by Henning Makholm, one can obtain from this a formula in terms of the prime factorization of $n$, as requested by OP in a comment to the post.
A: This function is called Pillai's arithmetical function and is A018804 in the OEIS. Values of the function starting from $n=1$ are as follows:
$$1, 3, 5, 8, 9, 15, 13, 20, 21, 27, 21, 40,\dots$$
Vladeta Jovovic in the comments there gives this formula which ranges only over the divisors of $n$:
$$\sum_{d\mid n}d\cdot\varphi(n/d)$$
which is the same sum as obtained by Andreas Caranti (above).
