A

complex root of unity is called

primitive
if it has

order *n*. Equivalenly,

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

*a*^{n}=1 but

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

*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.