# Strategy of the proof of every prime number has a primitive root

I am going through number theory from the following book :

On page 96, the proof is given that every prime number $$p$$ has a primitive root modulo $$p$$.

The proof proceeds with establishing the equality of two summatory functions: in particular the sum of number of elements of order $$m$$ where $$m$$ is a number which divides $$p - 1$$ for some prime number $$p$$ and the sum of the number of elements coprime to $$m$$ where $$m|(p-1)$$.

On page 93 (theorem 58), the proof that "if a prime, $$p$$, is known to have a primitive root(s), then it will have $$\phi (p - 1)$$ " is given .

However, for the proof for existence of primitive roots for prime numbers, I am unable to understand the strategy behind the proof. How does equating these two summatory functions lead to existence of a primitive root ?

I went through the following question centered around the same point but it is focusing on a different part of the proof.

The proof, as in the book, is as follows :

Proof: Let $$p$$ be a prime and let $$m$$ be a positive integer such that: $$p−1=mk$$ for some integer k. Let $$F(m)$$ be the number of positive integers of order $$m$$ modulo $$p$$ that are less than $$p$$. The order modulo $$p$$ of an integer not divisible by $$p$$ divides $$p − 1$$, it follows that: $$p-1=\sum_{m|p-1}F(m)$$ By theorem 42 we know that: $$p-1=\sum_{m|p-1}\phi(m)$$ By Lemma 11, $$F(m)\leq \phi(m)$$ when $$m\mid(p−1)$$. Together with: $$\sum_{m|p-1}F(m)=\sum_{m|p-1}\phi(m)$$ we see that $$F(m)=\phi(m)$$ for each positive divisor $$m$$ of $$p−1$$. Thus we conclude that $$F(m)=\phi(m)$$. As a result, we see that there are $$p−1$$ incongruent integers of order $$p−1$$ modulo $$p$$. Thus $$p$$ has $$\phi(p−1)$$ primitive roots.

Are $$1$$ and $$p -1$$ also being considered in the list of $$m$$ ? How is this idea in the proof working ?

• Welcome to MSE. I suggest that you add proof-explanation to the tags of your question. – José Carlos Santos Sep 28 at 9:38
• @JoséCarlosSantos : Thanks a lot , Done – beerzil charlemagne Sep 28 at 10:31
• I'm quite ready to answer this question, as I'm familiar with this proof, but what exactly is your question? You ask if 1 and (p-1) are "in the list of $m$"? The answer is yes - do you know what "a|b" means? 1|(p-1) and (p-1)|(p-1) so they appear in the sum. – Isky Mathews Sep 29 at 20:44
• Is that your only question? – Isky Mathews Sep 29 at 20:44
• The main point to show $\Bbb{F}_p^\times$ is cyclic is to say that all its elements are roots of $x^{p-1}-1$ but since $x^d-1$ has at most $d$ roots they are not all roots of $x^d-1$ for any $d< p-1$, thus there is some $a$ which is a root of $x^{p-1}-1$ but not of any $x^d-1,d < p-1$ and $a$ is a primitive root. – reuns Sep 29 at 22:05

While I'm still not quite sure what you're asking, I shall go through each section of the proof in a lot of detail with the hope that this will help. Again, I'm sorry if I go over a lot of things you already know but I just don't know quite what part you're having difficulty with.

The order of an element $$a$$ modulo our prime $$p$$, as a reminder, is the smallest positive exponent $$i$$ s.t. $$a^i=1$$ modulo $$p$$. General proof strategy, then, is as follows:

We define a function $$F(m)$$ as the number of elements of order $$m$$ modulo $$p$$. So as an example, if we look modulo $$5$$, we see that $$4^2=1$$ (so 4 is an element of order 2) and every other element is either 1 (so has order 1) or has order greater than 2 (as $$2^2=3^2=4\neq 1$$). So, modulo 5, $$F(2)=1$$.

We then remember that the order of an element must divide the number of non-zero elements modulo $$p$$.

Why is this? (feel free to skip this if you know it already) Firstly, we know by Fermat's Little Theorem that $$a^{p-1}=1$$ modulo $$p$$ for every non-zero element $$a$$ modulo $$p$$. Then, if the order of an element $$a$$ is $$e$$, we can long divide $$p-1$$ by $$e$$ so that $$p-1=e\times n+b, 0\leq b Then we get that, modulo $$p$$, $$1=a^{p-1}=a^{e\times n+b}=a^{e\times n}a^b=(a^{e})^na^b=(1)^na^b=a^b$$ so $$a^b=1$$ but we know that $$b and $$e$$ is the smallest positive exponent for which $$a^e=1$$ so $$b$$ cannot be positive! But we also know that $$0\leq b$$ so $$b=0$$ and so $$p-1=e\times n$$ so $$e|p-1$$.

So the order of an element must divide $$p-1$$. But, obviously, every element has some order (given that orders are bounded above by $$p$$, i.e. we already know that $$a^p=1$$ modulo $$p$$ for every nonzero element $$a$$). So thus $$\sum_{k|(p-1)}F(k)=(p-1)$$This sum really doesn't say much - the number of elements that have some order is the number of nonzero elements.

Next, the proof whips out a famous identity which it says you've already seen the proof of. There are a number of other proofs online (some completely elementarily, some using the FTA, some using the multiplicative nature of the sum) but I won't give one here - you apparently have one in your textbook. The identity is the following:

$$n = \sum_{k|n}\phi(k)$$

for a natural number $$n$$ and we particularly care about this result when $$n=(p-1)$$. Now the proof says that you already know, from some previous section, that $$F(k) \leq \phi(k)$$ and since $$\sum_{k|n}\phi(k)=\sum_{k|(p-1)}F(k)$$ we deduce that $$F(k)=\phi(k)$$ for each divisor $$k$$. Why is this?

Suppose that any of these inequalities is strict, i.e. $$F(k)<\phi(k)$$ for some $$k$$ in the sum. Then, even if $$F(n)=\phi(n)$$ for every other divisor of $$(p-1)$$, we would have that $$\sum_{k|n}\phi(k)<\sum_{k|(p-1)}F(k)$$ which is a contradiction.

Then if $$F(k)=\phi(k)$$ for each divisor $$k$$ of $$(p-1)$$ and $$\phi(k)\geq 1$$ for each $$k$$, we know that $$F(p-1)=\phi(p-1) \geq 1$$, i.e. there is at least one element of order $$(p-1)$$ (a primitive root!) and we're done!

Just because I'm not personally such a fan of using $$F(m)\leq \phi(m)$$ without explaining it (given that it's arguably the most important part of the proof) and that I can't find anybody else on this forum explaining this fact, I'm going to give my own explanation here. You don't have to read this but I strongly suggest it, as I think this is very nice:

Consider the polynomial $$x^d-1$$ for a divisor $$d$$ of $$(p-1)$$ and suppose, hypothetically, it had some root $$u$$ modulo $$p$$. Then we can notice that $$u,u^2,u^3,...,u^d$$ are all roots also.

Why? $$(u^k)^d-1=(u^d)^k-1=1^k-1=0$$.

But notice that $$x^d-1$$ is a polynomial of degree $$d$$ and so, by Lagrange's Theorem, can have at most $$d$$ roots (the proof of L's theorem literally replicates polynomial division in modular arithmetic so we don't worry about it here - you may already know a proof!). But if it can have at most $$d$$ roots and $$u,...,u^d$$ are all roots, then $$u,...,u^d$$ are the only roots of this equation!

But every element of order $$d$$ must be a root of $$x^d-1$$ by definition so every element of order $$d$$ is a power of $$u$$. (NOTE: not every root of $$x^d-1$$ is an element of order $$d$$ - if $$u^k$$ had order $$d/2$$, it would still be a root of the equation)

But which powers of $$u$$ have order $$d$$ given that $$u^d-1=0$$? Well, all the powers of $$u$$ whose order is $$coprime$$ with $$d$$ (for the same EXACT reason as used in the proof that if there is 1 primitive root modulo $$p$$ then there are $$\phi(p-1)$$ many, a theorem whose proof you say you understand).

So if every element of order $$d$$ is a power of $$u$$ and there are exactly $$\phi(d)$$ many powers of $$u$$ of order $$d$$, then there are $$\phi(d)$$ many elements of order $$d$$.

So, if we call the number of elements of order $$d$$ "$$N_d$$", then we have just shown that $$N_d=0$$ OR $$N_d=\phi(d)$$, i.e. $$N_d \leq \phi(d)$$ as required.

===========================================================================

Phew! That took a long time to write, so I hope it's helpful. Don't be scared to ask for further clarification if necessary!

• Take a bow. I will never forget this generosity of yours . Thanks a ton – beerzil charlemagne Oct 9 at 19:23