I am studying the discrete Fourier transform. For sequence $x_{0}, \dots, x_{N-1}$ it is defined as
$$X_{k} = \sum_{n=0}^{N-1} x_{n}e^{-2\pi ikn/N} \quad 0 \leq k \leq N-1$$
according to Wikipedia. The article states that the definition can be given as
$$X_{k} = \sum_{n=0}^{N-1} x_{n}w^{kn} \quad 0 \leq k \leq N-1$$
where $w = e^{-2\pi i/N}$ is the $N$th primitive root of unity. How can I show that $w$ actually is an $N$th primitive root of unity? I believe this is connected to Euler's formula, and maybe De Moivre's, but after several attempts I could still not solve it.
EDIT:
I think I partly figured it out:
1) Because $w^{N} = (e^{-2\pi i/N})^{N} = e^{-2\pi i} = \cos(-2\pi) + i\sin(-2\pi) = 1$, $w$ is a root of unity by definition.
2) Let $m < N$ be a positive integer. Now $w^{m} = e^{-2\pi i m/N} = \cos(-2\pi m/N) + i\sin(-2\pi m/N) \neq 1$ for all $m$ (how to proof this?). Therefore, $w$ is primitive root of unity.
There is a good reason why one writes of "a primitive $N$th root of unity" rather than of "the $N$th primitive root of unity". The word "the" in this context could reasonably be taken to mean that only one primitive $N$th root of unity exists, but that is false.
$$ \underbrace{e^{2\pi i/N}\cdots e^{2\pi i/N}}_{N\text{ factors}} = e^{2\pi i/N+\,\cdots\,+2\pi i/N} = e^{2\pi i } = \cos(2\pi) + i\sin(2\pi). $$ This shows that $e^{2\pi i/N}$ is a root of unity. It remains to show that it is primitive. $$ \underbrace{e^{2\pi i/N}\cdots e^{2\pi i/N}}_{n\text{ factors}; \quad 0<n<N} = e^{2\pi i n/N} = \cos\left(\frac{2\pi in}N\right)+i\sin\left(\frac{2\pi in}N\right) $$ Observe that $0<\dfrac{2\pi n}N<2\pi$, and the sine and cosines functions, or the function $x\mapsto e^{ix}$, has no period smaller than $2\pi$. Although $\sin x$ returns to $0$ at one point before $x$ gets all the way from $0$ to $2\pi$, the other function $\cos x$, does not return to $1$ until $x$ traverses the whole period.
It is conventional to denote this number be $\omega$ rather than $w$.