Why is this term $=1$

Question

Can you tell me why

$$\frac{1}{r} \sum_{k=0}^{r-1} R_N(x^k) \sum_{s=0}^{r-1} e^{\frac{-2 \pi i s k}{r}}=1?$$

Here $R_N(x^k)$ is the remainder of $x^k$ Modulo $N$.

When I entered the last sum in Wolfram Alpha, it gave me $0$, so I am a Little bit confused here.

Thank you very much for your help.

(By the way: This Comes from the Shor-algorithm)

Answer 1

$\sum_{s=0}^{r-1} e^{\frac{-2 \pi i s k}{r}}$ equals $0$ unless $k=0$, in which case it equals $r$. So your expression is equal to $$\frac{1}{r} R_N(x^0) r = R_N(1) = 1$$

Answer 2

You face a geometric series. Thus $$S_k=\sum_{s=0}^{r-1} e^{\frac{-2 \pi i s k}{r}}=\frac{\left(1-e^{2 i \pi k}\right) e^{\frac{2 i \pi k}{r}-2 i \pi k}}{1-e^{\frac{2 i \pi k}{r}}}=e^{-\frac{i \pi k (r-1)}{r}} \sin (\pi k) \csc \left(\frac{\pi k}{r}\right)$$ which is $0$ for all $k \neq 0$ and then the results already given in answers and comments.