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
an=1 but
ar 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.