A unit $g \in \mathbb{Z}_n^*$ is called a generator or primitive root of $\mathbb{Z}_n^*$ if for every $a \in \mathbb{Z}_n^*$ we have $g^k = a$ for some integer $k$. In other words, if we start with $g$, and keep multiplying by $g$ eventually we will see every element. Generators are aptly named.

Example: $3$ is a generator of $\mathbb{Z}_4^*$ since $3^1 = 3, 3^2 = 1$ are the units of $\mathbb{Z}_4^*$.

Example: $3$ is a generator of $\mathbb{Z}_7^*$. From before the powers of $3$ are $3, 2, 6, 4, 5, 1$ which are the units of $\mathbb{Z}_7^*$.

Example: $3$ is not a generator of $\mathbb{Z}_{11}^*$ since the powers of $3 \pmod{5}$ are $3, 9, 5, 4, 1$ which is only half of $\mathbb{Z}_{11}^*$.

Theorem: Let $p$ be a prime. Then $\mathbb{Z}_p^*$ contains exactly $\phi(p-1)$ generators. In general, for every divisor $d | p - 1$, $\mathbb{Z}_p^*$ contains $\phi(d)$ elements of order $d$.

Proof: by Fermat’s Theorem we know the equation

\[ x^{p-1} - 1 = 0 \pmod {p} \]

has $p-1$ distinct solutions, namely every element of $\mathbb{Z}_p^*$. Let $q^k$ be a prime power dividing $p-1$. Then we can factorize the above

\[ x^{p-1} - 1 = (x^{q^k} - 1)g(x) = 0 \pmod {p} \]

where $g(x)$ is some degree $p-1-q^k$ polynomial. From our notes on polynomials we know that $(x^{q^k} - 1)$ has at most $q^k$ roots and $g(x)$ has at most $p-1-q^k$ roots, and since their product has $p-1$ different roots, we see that there are exactly $q^k$ distinct solutions to

\[ x^{q^k} - 1 = 0 \pmod {p}. \]

Any solution $a$ must have order dividing $q^k$. Suppose such an $a$ has order less than $q^k$. Then its order must divide $q^{k-1}$, and $a$ is a solution of $x^{q^{k-1}} - 1 = 0$.

By a similar argument $x^{q^{k-1}} - 1$ (which is a factor of $x^{q^k} - 1$) has exactly $q^{k-1}$ distinct roots, so there must be exactly $q^k - q^{k-1}$ roots of $x^{q^k} - 1$ that are not roots of $x^{q^{k-1}}$ and hence are of order $q^k$. Recall $q^k - q^k-1 = \phi(q^k)$.

Factorize $p-1$ into primes:

\[ p-1 = q_1^{k_1}...q_n^{k_n} \]

For each $q_i^{k_i}$ we find an element $a_i$ with order $q_i^{k_i}$. Since the orders of each $a_i$ are coprime, the order of their product is equal to the product of their orders, that is $a_1...a_i$ has order $q_1^{k_1}...q_n^{k_n} = p-1$ and thus is a generator.

We have $\phi(q_i^{k_i})$ choices for each $a_i$ thus we have exactly $\phi(q_1^{k_1})...\phi(q_n^{k_n}) = \phi(p-1)$ different generators.

A similar argument proves the theorem for the divisors of $p-1$.∎

Alternative Proof: We can use a counting argument and basic facts about cyclic groups instead.

Any element $a \in\mathbb{Z}_p^*$ must have order dividing $p-1$ (by Fermat). Then if $a$ has order $d$, the solutions of

\[ x^d - 1 = 0 \pmod {p}. \]

are precisely $a, a^2,...,a^d = 1$ and there are no other elements of order $d$ since $x^d - 1$ has at most $d$ roots.

It is easy to show that $a^k$ has order $d$ if and only if $\gcd(k, d) = 1$, thus either there are no elements of order $d$ or there are exactly $\phi(d)$ elements of order $d$.

Now $\sum_{d|p-1} \phi(d) = p-1$ (which we can prove using multiplicative functions or cyclic groups) and if any of the $\phi(d)$ were replaced with $0$ on the left-hand side, the equality would fail. Hence there must be exactly $\phi(d)$ elements of order $d$ for each $d | p-1$ (since each one of the $p-1$ elements of $\mathbb{Z}_p^*$ must have some order). ∎