### Theorem 10.4.1. Primitive Roots Exist for Primes.

Every prime has a primitive root. In other words, the order \(p-1\) group \(U_p\) is always cyclic.

We use many of the same techniques and ideas in by proving that every prime number \(p\) has a primitive root. Let’s check that this claim is true for at least *some* primes.

So at least we get a primitive root for the first 25 primes.

Every prime has a primitive root. In other words, the order \(p-1\) group \(U_p\) is always cyclic.

Below, we will actually prove the stronger Claim 10.4.4, which states that the number of elements of order \(d\) (a positive divisor of \(n\)) is \(\phi(d)\text{.}\) Naturally this will be non-zero for \(d=p-1\text{,}\) which proves the theorem.

Before we examine the claim, we need some discussion.

First, it is useful to see what these sets look like for two examples – one where we know we have a primitive root, and one where we know we don’t.

Assuming you are online, evaluate the next cell to get the list of sets of different order elements for \(n=41\text{:}\)

But here is the list of sets for \(n=32\text{;}\) there aren’t any for the highest possible order, and all the other sets have orders exact multiples of \(\phi(d)\text{.}\)

As always, doing an entire example manually is very instructive too.

For another set of ideas, recall that if \(g\) is a primitive root of \(p\text{,}\) by definition \(g^{p-1}\equiv 1\) but no previous positive power is. Assuming \(p\) is an odd prime, then \(p-1\) is even, and we could try to separate out the odd and even powers

\begin{equation*}
g,g^3,g^5,\ldots\text{ and }g^2,g^4,g^6,\ldots
\end{equation*}

and compare them or their products.

Let \(g\) be a primitive root of \(p\text{.}\)

- Can you see why the inverse of an even power of a primitive root is also an even power?
- Do you think an odd power (greater than one) of a primitive root \(g\) could be a
*different*primitive root \(g'\text{?}\) Why or why not? What about even powers of a given primitive root – could they be primitive roots, at least in principle?

Finally, for those with more experience with groups, a good exercise would be to see whether Claim 10.4.4 converts into a statement about the number of elements of each order of *any* cyclic group.

Now let’s prove our claim.

If \(p\) is prime, the number of elements of \(U_p\) of order \(d\) is \(\phi(d)\) (where of necessity \(d\) is a positive divisor of \(\phi(p)=p-1\)).

Assume that \(p\) is prime. For any of the divisors \(d\) of \(p-1\) (not just \(p-1\) itself), consider the possible number of elements of \(U_p\) with that order,

\begin{equation*}
\left|\{a\in U_p \mid a\text{ has order }d\}\right|\text{.}
\end{equation*}

By Lemma 10.3.5, this quantity is clearly between zero and \(\phi(d)\text{.}\) On the other hand, by Lemma 10.3.4, once we find one \(a\) with order \(d\text{,}\) then all the powers of \(a\) coprime to \(d\) also have that order (and are distinct), so there are at least \(\phi(d)\) of them.

In particular, the cardinality of the set of elements of \(U_p\) of order \(d\) is always either zero or \(\phi(d)>0\text{,}\) so the entire proof boils down to finding at least one element \(a\) with order \(d\) for each potential order \(d\text{.}\) (The reason we just need to consider \(d\mid p-1\) is Theorem 8.3.12 that the order of any element of a group divides the order of the group, so the only possible orders of elements in \(U_p\) are positive divisors of \(p-1\text{.}\))

Suppose that at least one of the sets for some divisor \(d'\) (such as the set of *primitive* roots, if \(d'=p-1\)) is empty. Then on the one hand, *every* element of \(U_p\) has *some* order, so

\begin{equation*}
p-1=\sum_{d\mid p-1} \left|\{a\in U_p \mid a\text{ has order }d\}\right|\leq 0+\sum_{d\mid p-1, d\neq d'} \phi(d)\text{.}
\end{equation*}

On the other hand, Fact 9.5.4 with \(n=p-1\) tells us that

\begin{equation*}
\sum_{d\mid p-1, d\neq d'} \phi(d)\lt \sum_{d\mid p-1} \phi(d)=p-1\text{.}
\end{equation*}

Combining these two inequalities yields \(p-1\lt p-1\text{,}\) an absurdity.

The proof above makes it evident that the real place primality is used is in the crucial lemmas 10.3.5 and 10.3.4. If you are still curious to see how this works, you can explore more online in the following interact; when there is not a primitive root, somehow the ‘extra’ elements of \(U_n\) which ‘would have’ had order \(\phi(n)\) are distributed nicely among the remaining potential orders.