I was reading this proof of the roots of unity filter and I point can't understand is why:
$$ S = \sum_{j=0}^{n-1} w^{kj} =0$$
If $ \omega $ is the nth root of unity and $k$ is some positive integer not equal to zero and n doesn't divide k
I understand that the sum of nth roots of unity are zero as in:
$$ S = \sum_{j=0}^{n-1} w^j = 0$$
But I can't understand the powers of them should be as well. The reason I find it strange is that the nth roots of unity solves the following polynomial equation
$$ P(x) =(x-1)( \sum_{i=0}^{n-1} x^i)$$
So why should it be that any of their powers solve the above equation as well?
Best Answer
You can use the typical trick for geometric series. You have that if
$$S = \sum_{j=0}^{n-1} w^{kj}$$
then
$$w^k S = \sum_{j=1}^n w^{kj} \implies S = \frac{1-w^{nk}}{1-w^k} = 0 $$