## Generators

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

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

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

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:

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

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