Section10.4Prime Numbers Have Primitive Roots¶ permalink
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.
Theorem10.4.1
Every prime has a primitive root. In other words, the order \(p-1\) group \(U_p\) is always cyclic.
Proof
The key to the proof is to try to write \(\phi(p)=p-1\) in two different ways:
\(p-1=\phi(p)=\sum_{d\mid p-1} \phi(d)\)
\(p-1=\sum_{d\mid p-1} \mid\{a\in U_p \mid a\text{ has order }d\}\mid\)
Note that the first fact is simply Fact 9.5.4 for \(n=p-1\).
The second equation makes sense too. We already proved (in Theorem 8.3.11) Lagrange's result 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\). Since every element of \(U_p\) has some order, the \(p-1\) elements thereof are divided up into (disjoint) sets of these different orders.
To finish the proof, we then just need to prove that the only possibility is the number of elements of \(U_p\) of order \(d\) is \(\phi(d)\). Proving this is Claim 10.4.2. Then there will certainly be at least one element of maximal order.
Before we finish the proof by examining the claim, we need some discussion. First, let's 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.
Here is the list of sets of different order elements for \(n=41\):
But here is the list of sets for \(n=32\); there aren't any for the highest possible order, and all the other sets have orders exact multiples of \(\phi(d)\).
For another set of ideas, recall that if \(g\) is a primitive root of \(p\), 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.
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'\)? Why or why not? What about even powers of a given primitive root – could they be primitive roots, at least in principle?
Now let's prove our claim.
Claim10.4.2
If \(p\) is prime, the number of elements of \(U_p\) of order \(d\) is \(\phi(d)\).
Assume that \(p\) is prime. For any of the divisors \(d\) of \(p-1\) (not just \(p-1\) itself), the size of the set \begin{equation*}|\{a\in U_p \mid a\text{ has order }d\}|\end{equation*} certainly can't be bigger than \(\phi(d)\), by Lemma 10.3.5. On the other hand, every element of \(U_p\) has some order! And by Lemma 10.3.4, once we find one \(a\) with order \(d\), then all the powers of \(a\) coprime to \(d\) also have that order, so there are \(\phi(d)\) of them.
So the entire proof boils down to finding at least one element \(a\) with order \(d\) for each potential order \(d\).
Suppose that any of the sets for \(d\) (such as the set of primitive roots for \(d=p-1\)) is empty. Then the elements which ‘would have’ had order \(d\) in our group of units have to be ‘distributed’ among the other sets. That's \(\phi(d)\) elements.
But we know that none of the sets corresponding to a divisor \(d\) is bigger than \(\phi(d)\), and \begin{equation*}\sum_{d\mid p-1, d<p-1} \phi(d)<p-1\; ;\end{equation*} yet all of the \(p-1\) elements in \(U_p\) must be in one of the sets. This doesn't make sense unless there is at least one element in each of the sets of elements with order \(d\), so in particular there is at least one of each potential order, which means there are the maximal number with each order.
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 below.
