# 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 see every element.

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{11}$$ 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_n$$ 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). ∎

Ben Lynn blynn@cs.stanford.edu 💡