A primitive root in is an integer such that for each such that there exists an integer such that (It follows that

When is a prime, always has primitive roots. Indeed is a cyclic group of order generated by any primitive root; hence the number of primitive roots is This answers your question for

If is not prime, things are a little complicated. For though, you can easily see that for which are the integers coprime with Hence has no primitive roots since there is are no integers such that even though