Prove that there are exactly $\phi(p-1)$ primitive roots modulo a prime $p$

Question

Note, in the proof below, I assume as proven the theorem that, if $d$ is any factor of $p-1$, then the equation $$\tag{1} x^d -1\equiv 0\pmod{p}$$ has exactly $d$ solutions, and I skip the details of showing there are at least $\phi(p-1)$ primitive roots.

Proof:

Let $$p-1={q_1}^{a_1}\cdots {q_k}^{a_k},$$ for distinct primes $q_i$.

Consider some specific $q^a$ in the above factorisation. By $(1)$, and Lagrange’s Theorem on the number of solutions to an algebraic equation in the field $\Bbb{Z}/p\Bbb{Z}$, it can be shown that there are exactly $q^a -q^{a-1}$ elements $x\in\Bbb{Z}/p\Bbb{Z}$, such that the order of $x$ is $q^a$.

By the multiplication principle, it thus follows that there are at least $\phi(p-1)$ primitive roots modulo $p$. We will show that these are in fact the only primitive roots.

To see this, consider any primitive root $g$ in $\Bbb{Z}/p\Bbb{Z}$.

If $$n_i=\frac{p-1}{{q_i}^{a_i}},$$ then $g^{n_i}$ has order ${q_i}^{a_i}$. By Bézout’s lemma, there exist integers $l_i$ such that $$\sum l_in_i=1.$$

We wish to prove that the order of $g^{l_in_i}$ is still ${q_i}^{a_i}$. For this, it suffices to show that $gcd(l_i,n_i)=1$.

Assume, for contradiction, that for some $j$ they are not coprime; that is, $$l_j={q_j}^{b_j}m$$ for some integer $m$. Now, consider the sum $\sum l_in_i$. Explicitly, this is $$\tag{2} (p-1)\left[\sum{\frac{l_i}{{q_i}^{a_i}}}\right]=1$$

Converting the left side of $(2)$ into a single fraction gives:

$$(p-1)\left[\frac{l_1A_1+\cdots +l_kA_k}{\prod{{q_i}^{a_i}}}\right]=1$$ $$\implies \tag{3}l_1A_1+\cdots+l_kA_k=1,$$

where $$A_r=\frac{\prod{{q_i}^{a_i}}}{{q_r}^{a_r}}.$$

By our assumption, every term on the left side of $(3)$ contains $q_j$ as a factor, but this implies $$q_jA=1,$$ where $A$ is an integer, which is a contradiction.

Thus, $$g\equiv g^{\sum l_in_i}\equiv \prod g^{l_in_i}\pmod{p},$$ so that $g$ is a product of $k$ numbers with distinct coprime orders ${q_i}^{a_i}$ that multiply to $p-1$.

$\square$

Question: I am wondering if I need to explicitly consider the sign of the integers $l_i$, since, as $g$ is primitive, the congruence $$\left(g^m\right)^{-1}\equiv x\pmod{p}$$ is soluble for any positive integer $m$, and so the numbers $g^m$ and $x$ will have the same order modulo $p$, which means to work out the order of $g^{l_in_i}$ we can, if we like, take $l_i$ positive.

Answer 1

Your first fact implies the multiplicative group of $\Bbb Z_p$ is cyclic. For if it isn't cyclic, then it has a subgroup isomorphic to $\Bbb Z_q\times \Bbb Z_q$, which gives $q^2$ roots to $x^q-1$.

And $\mid\Bbb Z_p^*\mid=p-1$.

Take a primitive element $g$ of $\Bbb Z_p^*$. That is $\langle g\rangle =\Bbb Z_p^*$. Then for every $k$ with $k$ and $p-1$ relatively prime, $g^k$ is a primitive root $\bmod p$.

But there are $\phi(p-1)$ such $k$.