*n*. Equivalenly,

*a*is a primitive complex root of unity if and only if

*a*but

^{n}=1*a*is not 1, for any smaller positive

^{r}*r*.

It's quite easy to show that they are exactly: *e ^{(2pik/n)}* with

*1<=r<=n*and such that

*r*and

*n*have no common factor.

Thus, there are *phi(n)* primitive roots of unity, where
*phi* is the Euler Phi function.