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.