More fun in 2015, Part 24

We will use two basic results from number theory.

(a) The sum of all the $m$ th primitive roots of unity is $\mu(m)$ , the Mobius function (this result was known to Gauss). We discussed this issue here .

(b) $\phi(n)=\sum_{d|n}d\mu\left(\frac{n}{d}\right)$ . There are many ways to prove this formula. One approach is to point out that both sides are multiplicative functions; for prime powers $p^n$ both sides come out to be $p^n-p^{n-1}$ .

Now consider $\sum_{k=1}^{n}\gcd(n,k)e^{2k\pi i/n}$ . If $\gcd(n,k)=d$ , then $e^{2k\pi i/n}$ will be a primitive $\left(\frac{n}{d}\right)$ 'th root of unity. If we group together the terms with $\gcd(k,n)=d$ , we see that $\sum_{k=1}^{n}\gcd(n,k)e^{2k\pi i/n}=\sum_{d|n}d\mu\left(\frac{n}{d}\right)=\phi(n)$ . Taking real parts, we find that $\sum_{k=1}^{n}\gcd(n,k)\cos(2k\pi/n)=\phi(n)$ In the case of interest, $n=2015$ , this sum comes out to be $\phi(2015)=\boxed{1440}.$