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.


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


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.

  • $\begingroup$ "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). $\endgroup$ Sep 17, 2019 at 23:05
  • $\begingroup$ @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. $\endgroup$
    – Mo Pol Bol
    Sep 17, 2019 at 23:15
  • $\begingroup$ Do you know the multiplicative group of nonzero elements of a finite field is cyclic? $\endgroup$
    – Bernard
    Sep 17, 2019 at 23:23
  • $\begingroup$ @Bernard yeah, I’ve seen the result proven much easier that way, but this was going for a purely elementary proof. $\endgroup$
    – Mo Pol Bol
    Sep 17, 2019 at 23:28

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

  • $\begingroup$ Thanks, I’ve actually seen this proof elsewhere, but I am trying to prove the result using only elementary number theoretic tools. $\endgroup$
    – Mo Pol Bol
    Sep 18, 2019 at 0:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .