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, which explains the term “generator”.

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(mod5)$ 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 $\varphi (p-1)$ generators. In general, for every divisor $d\mid p-1$, ${\mathbb{Z}}_p^{*}$ contains $\varphi (d)$ elements of order $d$.

Proof: by Fermat's Theorem we know the equation $$x^{p-1}-1=0(modp)$$ 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(modp)$$ where $g(x)$ is some degree $p-1-q^k$ polynomial. From before 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(modp).$$ 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=\varphi (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, [[order.xhtml][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 $\varphi (q_i^{k_i})$ choices for each $a_i$ thus we have exactly $\varphi (q_1^{k_1})...\varphi (q_n^{k_n})=\varphi (p-1)$ different generators.

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

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(modp).$$ 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 $\varphi (d)$ elements of order $d$.

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

What about powers of primes, or composite numbers in general?