Now we can unify a lot of this by proving that every prime number \(p\) has a primitive root. It uses both of the above as lemmas. Let's check that it seems true:

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

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)\).

So what is going on here? Let's go back to our assumption that \(p\) is prime.

• For any of the divisors \(d\) of \(p-1\) (not just \(p-1\) itself), the size of the set \[|\{a\in U_p \mid a\text{ has order }d\}|\] certainly can't be bigger than \(\phi(d)\), by our second lemma.
• On the other hand, as we just pointed out, every element of \(U_p\) has some order!
• 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 - and no more than \(\phi(d)\) of them - again, once we find such an \(a\).

This means that if 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 \[\sum_{d\mid p-1, d<p-1} \phi(d)<p-1\; ;\] 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 proves there is one with full order, a primitive root!)

If you are curious, you can explore more below.