Section10.3When is there a primitive root?

Subsection10.3.1Primitive roots of powers of two

We'll start this investigation by proving that most powers of 2 do not have primitive roots. The following should give you an error.

Proposition10.3.1

There are elements of \(U_{2^n}\) that have order \(2^{n-2}\), just not primitive roots (which would have order \(\phi(2^n)=2^{n-1}\)). In fact, it turns out that \(\pm 5\) have this order. (We won't prove this, but it is easy if you use just a little group theory.)

Proof

Subsection10.3.2Two Important Lemmas

There follow two important lemmas for working with primitive roots.

Lemma10.3.2

Suppose \(p\) is prime and the order of \(a\) modulo \(p\) is \(d\). If \(b\) and \(d\) are coprime, then \(a^b\) also has order \(d\) modulo \(p\).

Lemma10.3.3

Suppose \(p\) is prime and \(d\) divides \(p-1\) (and hence is a possible order of an element of \(U_p\)). There are at most \(\phi(d)\) incongruent integers modulo \(p\) which have order \(d\) modulo \(p\).

Let's try to unpack these. In the first lemma, let the order of \(a\) be \(p-1\).

Then \(a\) is a primitive root modulo \(p\), and so is \(a^b\) for all \(b\) coprime to \(p-1\).
This implies that if there is a primitive root modulo \(p\), then there are in fact \(\phi(p-1)\) of them!
(This turns out to be true for general \(n\), replacing \(p-1\) by \(\phi(n)\), in fact.)
It works; let's check this out.

Subsubsection10.3.2.1How the lemmas (don't) fail

Let's pick a non-prime number we know something about to see how many numbers we have with a given order.

Last time we saw that powers of 2 don't have cyclic groups of units, but they do have lots of elements with the next smallest possible order. So for \(n=32\), we can look at whether powers \(b\) coprime to that order of such an element are in fact also elements with the same order.

So it works; indeed, the first lemma should be true whether \(p\) is prime or not, though I won't ask you to prove it. The second lemma also seems to be working; there are exactly \(\phi(8)=4\) powers here, which have order eight.

The problem, though, is that there might be some element of the same order as the ones above which is not actually one of them!

In some sense, then, there are "extra" elements with order \(8\) in the above example. If you have eight elements of order eight, and obviously at least one element of order 1, in \(U_{32}\), then it is impossible to have the required eight elements of order sixteen one would need for there to be a primitive root modulo \(32\) (because \(8+1+8>16=|U_{32}|\)). In essence, the fact that this can't happen for a prime modulus is why primitive roots do exist in that case.