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