Find $\sum_{i=1}^{2000}\gcd(i,2000)\cos\left(\frac{2\pi\ i}{2000}\right)$ What is the value of the following sum?  

$$\sum_{i=1}^{2000}\gcd(i,2000)\cos\left(\frac{2\pi\ i}{2000}\right)$$  
where 
  
  
*
  
*$\gcd$ is the greatest common divisor.
  

 A: Answer : the sum evaluates to $\varphi(2000)=800$ .
why? because :
Claim : 

For any positive integer $n$ we have:$$\varphi(n)=\sum_{i=1}^{n}\gcd(i,n)\cos\left(\frac{2\pi\ i}{n}\right) \tag 1$$ where $\varphi(n)$ is Euler's totient function

Proof
Let $\zeta_n := e^{\frac{2\pi i}{n}}$, define the function $s$ for every positive integer $n$ by :
$$ \displaystyle s(n) := \sum_{\substack{1\leq k\leq n\\ \gcd(k,n)=1}}\zeta_n^k \tag 2$$
this is, of course, the sum of all primitive $n$-th roots of unity. Since every $n$-th root of unity is a primitive $d$-th root of unity for some divisor $d$ of $n$, we have, for all positive integers $n$:
$$\displaystyle \sum_{d|n} s(d) = \sum_{k=1}^n \zeta_n^k = \begin{cases} 1 &,\quad n=1\\ 0 &,\quad n\geq 2\end{cases}\tag 3$$
This last identity is the characterization of the the Mobius function $\mu$ (this can be proven using the Dirichlet convolution, as we know the Dirichlet inverse of the constant function $1$ is the Möbius function $\mu$), hence $s(n)=\mu(n)$. So up to here we have :
$$\mu(n)=\sum_{\substack{1\leq k\leq n\\ \gcd(k,n)=1}}\zeta_n^k \tag 4$$
This last identity is related to Ramanujan's sum.
Using the Dirichlet convolution again, the Möbius inversion gives
$$ \varphi(n) = \sum_{d\mid n} d \cdot \mu\left(\frac{n}{d} \right) = n\sum_{d\mid n} \frac{\mu (d)}{d}\tag 5$$
This identity can be derived also using the expansion of :$ \prod_{p\mid n} \left(1 - \frac{1}{p}\right)$and get  $\sum_{d\mid n} \frac{\mu (d)}{d}$. Now we can use this to prove our claim:
$$\begin{align}\sum_{k=1}^n \gcd(k,n) \zeta_n^k &=\sum_{d|n}d\sum_{\substack{1\leq k\leq n\\ \gcd(k,n)=d}} \zeta_n^k &\text{ take } d:=\gcd(k,n) \text{ and sum over }d &\\ \\
&=\sum_{d|n}d\sum_{\substack{1\leq k'\leq \frac{n}{d}\\ \gcd(k',\frac{n}{d})=1}} \zeta_{\frac{n}{d}}^k & \text{rewrite the inner sum; } k'=\frac{k}{d}\\ \\
&=\sum_{d|n}d\mu\left(\frac{n}{d}\right)& \text{ using the identity } (4)\\ \\ 
&=\varphi(n) &\text{ using the identity } (5)\end{align}$$
\
This gives us the final identity:
$$\varphi(n)=\sum_{k=1}^n \gcd(k,n) \zeta_n^k \tag 6 $$
now you would obtain $(1)$ by taking the real part of both sides of this identity.
