# Eigenvectors and eigenvalues of the gate $U_a:|s\rangle\mapsto|sa \bmod N\rangle$

I'm studying Shor algorithm. This is a demostration about the eigenvectors and eigenvalues of $$U_a$$ gate:

$U_{a}:&space;\left&space;|s&space;\right&space;\rangle&space;\rightarrow&space;\left&space;|sa&space;\mod&space;N&space;\right&space;\rangle&space;\\&space;\\&space;\\&space;U_{a}&space;\left|w_k\right&space;\rangle&space;=&space;\frac{1}{\sqrt{r}}&space;\sum_{s=0}^{r-1}&space;e^{-2\pi&space;i&space;\frac{k}{r}s}&space;U_{a}\left|a^{s}&space;\mod&space;N\right&space;\rangle&space;\\&space;=&space;\frac{1}{\sqrt{r}}&space;\sum_{s=0}^{r-1}&space;e^{-2\pi&space;i&space;\frac{k}{r}s}\left|a^{s+1}&space;\mod&space;N\right&space;\rangle&space;\\&space;=&space;e^{2\pi&space;i&space;\frac{k}{r}}&space;\frac{1}{\sqrt{r}}&space;\sum_{s=0}^{r-1}&space;e^{-2\pi&space;i&space;\frac{k}{r}(s+1)}\left|a^{s+1}&space;\mod&space;N\right&space;\rangle&space;\\&space;=&space;e^{2\pi&space;i&space;\frac{k}{r}}&space;\left&space;|w_{k}&space;\right&space;\rangle$

Can somebody explain me from the third step to the last?

You have the state $$\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}e^{-2\pi i\frac{k}{r}(s+1)}|a^{s+1}\text{ mod }N\rangle.$$ Perform a change of variable $$p=s+1$$ so this simply reads $$\frac{1}{\sqrt{r}}\sum_{p=1}^{r}e^{-2\pi i\frac{k}{r}p}|a^p\text{ mod }N\rangle.$$ Now consider for a moment that $$p=r$$ term, $$e^{-2\pi i\frac{k}{r}r}|a^r\text{ mod }N\rangle=|a^r\text{ mod }N\rangle.$$ By definition, $$a^r\equiv 1\text{ mod }N$$, which we could also write as $$a^0$$. Hence, this term is exactly the same as using $$p=0$$ instead. Thus, the state has become $$\frac{1}{\sqrt{r}}\sum_{p=0}^{r-1}e^{-2\pi i\frac{k}{r}p}|a^p\text{ mod }N\rangle,$$ which is $$|w_k\rangle$$.