A basis for the DFT can be found in the following identity about $n$-th roots of unity $\zeta_k$, the sequence of which $(\zeta_k)$ builds for all $k\in\mathbb Z,$ an $n$-periodical complex sequence.

Lemma: Sum of Roots Of Unity in Complete Residue Systems 

For any positive integer $n > 0,$ the sum of $n$ consecutive $n$-th roots of unity equals $0.$

$$\sum_{k=0}^{n-1}\zeta_k=\sum_{k=0}^{n-1}\exp\left(2\pi i\frac {k}n\right)=0.$$

This result is only a special case for the complete residue system represented by the numbers $k=\{0,1,\ldots,n-1\}.$ By introducing a factor $(a-b)$ for arbitrary integers $a,b\in\mathbb Z,$ we have
$$\sum_{k=0}^{n-1}\exp\left(2\pi i\frac {(a-b)k}n\right)=\begin{cases}n&\text{ if }a(n)\equiv b(n)\\0&\text{else.}\end{cases}$$

| | | | | created: 2019-09-24 19:36:49 | modified: 2019-09-24 19:38:41 | by: bookofproofs | references: [8317]

1.Proof: (related to "Sum of Roots Of Unity in Complete Residue Systems")