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$ – darij grinberg Sep 17 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$ – Moed Pol Bollo Sep 17 at 23:15
  • $\begingroup$ Do you know the multiplicative group of nonzero elements of a finite field is cyclic? $\endgroup$ – Bernard Sep 17 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$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.