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

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.

• "By 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$." How? This is essentially the claim you are meant to prove (even a stronger one). – darij grinberg Sep 17 at 23:05
• @darijgrinberg yes, sorry, this part was proven in the text I am reading, which then asks you to show there are exactly $\phi(p-1)$ primitive roots. I should have made that clearer. – Moed Pol Bollo Sep 17 at 23:15
• Do you know the multiplicative group of nonzero elements of a finite field is cyclic? – Bernard Sep 17 at 23:23
• @Bernard yeah, I’ve seen the result proven much easier that way, but this was going for a purely elementary proof. – Moed Pol Bollo Sep 17 at 23:28

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$$.