# How do I prove that $\sum_{y=0}^{N-1}e^{2\pi i xy/N}=N\delta_{x,0}$?

I am trying to prove the following relation related to the Quantum Fourier Transform:

$$\sum_{y=0}^{N-1}e^{2\pi i\frac{x}{N}y} = \begin{cases}0 & \text{if } x\neq 0\mod N \\ N & \text{if } x=0\mod N\end{cases}.$$

I could not find the proof anywhere. What are the possible ways to proceed?

• Try to draw the terms in the sum in the complex plane, it will be clear that they sum to $0$. For a proof see this question on Math SE Sep 1, 2019 at 17:56

The case of $$x=0\text{ mod }N$$ is straightforward - each term in the sum is $$e^0=1$$ and there are $$N$$ terms in the sum.
For $$x\neq 0$$, there are a number of ways you could do this. I tend to use the sum of a geometric progression: $$\sum_{r=0}^{N-1}a^r=\frac{a^N-1}{a-1},$$ assuming $$a\neq 1$$. Hence, if we let $$a=e^{2\pi ix/N}$$, the sum is $$\frac{e^{2\pi ix}-1}{e^{2\pi ix/N}-1}=0.$$
Let $$f(y)=e^{2\pi i \frac{x}{N}y}, Y=\sum_{y=0}^{N-1}f(y)$$. Clearly $$f(0)=f(N)=1$$.
If $$x = 0\mod N$$, then $$f(y)=1$$, hence $$Y=N$$.
If $$x\not= 0 \mod N$$, then $$f(1)\not=1$$. Now $$f(1)Y=\sum_{y=1}^{N}f(x) = Y - f(0) + f(N) = Y$$, so $$Y(f(1)-1)=0$$. Since $$f(1)\not=1$$, then $$Y=0$$.