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