Find $\sum_{k=1}^n P(z_k)$ where P is a polynomial and $z_k$ the $k$th root of $z^{13}=1$ Question: Given a complex number z such that $z^{13}=1$, find the sum of all possible values of $z+z^3+z^4+z^9+z^{10}+z^{12}$.
I know we have to use roots of unity and try to manipulate the polynomial we want to evaluate, but can't find a pattern.
 A: As stated in comments, for a fixed $z=e^{i\theta}$ the given expression is equal to $2(\cos\theta+\cos3\theta+\cos4\theta)$. As $z$ runs through its $13$ possible values, so does each term ($1,3,4$ are all coprime to $13$) and the sum over all possibilities is
$$6\sum_{k=0}^{12}\cos\frac{2\pi k}{13}$$
but the summation is well-known to evaluate to zero, so the final answer is $0$.
A: Since $13$ is prime, the map $z\mapsto z^k$ is a permutation of the roots of $z^{13}-1$, for $k=1,2,3,\dots,12$.  Thus, the answer is $6$ times the sum of the roots , and this is $0$ by Vieta.
A: If $z^{13} = 1$ and $z \not= 1$, then $z = e^{2\pi i \frac{k}{13}}$ where $(k, 13) = 1$.
Since $z^{12} = z^{-1}$, $z^{10} = z^{-3}$ and $z^{9} = z^{-4}$ we have
$z+z^3 + z^4 + z^9 + z^{10}+z^{12} = 2(\cos(2 \pi \frac{k}{13}) + \cos(2 \pi \frac{3k}{13}) + \cos(2 \pi\frac{4k}{13}))$ where $z = e^{2\pi i \frac{k}{13}}$.
The total is $2\sum_{k=1}^{12} \cos(2 \pi \frac{k}{13}) + \cos(2 \pi \frac{3k}{13}) + \cos(2 \pi\frac{4k}{13}) = -6$.
If $z = 1$ is included, the total is $0$.
