# Can we simplify $\sum\limits_{k=1}^n 2^{\text{gcd}(k,n)}$?

The problem is contained in the headline: Is it possible to simplify the sum $\displaystyle \sum\limits_{k=1}^n 2^{\text{gcd}(k,n)}$?

-
$$\sum_{k=1}^n 2^{\gcd(k,n)} = \sum_{d \vert n}\phi(n/d) 2^d$$ I do not know if this can be simplified further. –  user17762 Jan 18 '13 at 0:31
The equation in Marvis's comment is a special instance of a polynomial identity: $\sum_{k=1}^n x^{\gcd(k,n)} = \sum_{d|n} \varphi(n/d)x^d$. At $x = 1$ it is the equation $n = \sum_{d|n} \varphi(d)$. At $x = 2$ it is the equation Marvis wrote down. –  KCd Jan 18 '13 at 4:17

As Marvis said, $$\sum_{k=1}^n2^{\text{gcd}(k,n)}=\sum_{d\mid n}\varphi(n/d)2^d.$$ Here's a cool article I found on OEIS detailing one way the expression occurs in combinatorics.