Loading [MathJax]/extensions/TeX/newcommand.js
Skip to main content

Section 10.3 When Does a Primitive Root Exist?

Recall your experimentation in Subsection 10.1.3. You should have discovered that there is not always a primitive root.

This is also the case for n=8 (Exercise 10.6.3). So, when do we have primitive roots?

Subsection 10.3.1 Primitive 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.

Assume \(n=2^k\) for \(k>2\text{.}\) (For \(n=2\) and \(n=4\text{,}\) there are primitive roots – check this if you haven't already). In Exercise 10.6.3 we show that \(n=8\) does not have a primitive root. In particular, each element of \(U_8\) has order \(2^{3-2}=2\text{,}\) so that \(a^2\equiv 1\) (mod \(8\)) for all \(a\in U_8\text{.}\)

Think of \(n=8=2^3\) as a base case for induction on \(k\geq 3\text{.}\) Now assume by induction that for \(n=2^k\) it is true that no element has order higher than \(2^{k-2}\text{.}\) I.e.,

\begin{equation*} a^{2^{k-2}}\equiv 1\text{ (mod }2^k)\text{.} \end{equation*}

By definition of divisibility, that means for any odd number \(a\text{,}\) we have that

\begin{equation*} a^{2^{k-2}}=1+2^k\cdot m \end{equation*}

for some integer \(m\text{.}\)

Next, let's look at what happens to everything in modulus \(2^{k+1}\text{.}\) We want that

\begin{equation*} a^{2^{(k+1)-2}}=a^{2^{k-1}}\equiv 1\text{ (mod }2^{k+1})\text{.} \end{equation*}

While it's easy to get \(2^{k+1}\) from \(2^k\text{,}\) the only way to easily get \(a^{2^{k-1}}\) from \(a^{2^{k-2}}\) is by squaring. (Recall Fact 4.5.5 where we found powers quickly by using \((a^{2^e})^2=a^{2^{e+1}}\text{.}\))

So we write \(a^{2^{k-1}}\) as a square, substitute the above, and look at the remainders.

\begin{equation*} a^{2^{k-1}}=\left(a^{2^{k-2}}\right)^2=(1+2^k m)^2=1+2^{k+1}m+2^{2k}m^2 \end{equation*}
\begin{equation*} =1+2^{k+1}(m+2^{k-1}m^2)\equiv 1\text{ mod }2^{k+1} \end{equation*}

By induction we are done; because the highest possible order of an element is less than \(\phi\text{,}\) there are no primitive roots modulo \(2^k\) for \(k>2\text{.}\) (Remember by Lagrange's Theorem on Group Order in any case the order is a power of two.)

We won't prove this, but it is easy if you use just a little group theory.

One can also demonstrate this fact computationally for a given example.

Subsection 10.3.2 Two important lemmas

There follow two important lemmas 1 Or lemmata, but who's counting? for working with primitive roots, whose proofs are valuable exercises.

Subsubsection 10.3.2.1 How the lemmas work

Before using them a lot, we should unpack these results a little bit. Here is a first taste.

We will only deal with the case of \(n=p\) prime (see Exercise 10.6.10 for the rest).

In Lemma 10.3.4, let the order of \(a\) be \(p-1\text{.}\) Then \(a\) is a primitive root modulo \(p\text{,}\) and so is \(a^b\) for every \(b\) coprime to \(p-1\text{.}\) Since there are \(\phi(p-1)\) of these, it satisfies the claim. By the Lemma 10.3.5, there can't be more.

It works; let's check this out interactively.

Subsubsection 10.3.2.2 How the lemmas (don't) fail

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

We saw in Proposition 10.3.2 that powers of two (past 4) do not have primitive roots, but U_{2^k} does have lots of elements with the next smallest possible order. So, for example, for n=32 we can look at whether powers b coprime to that order (8) of such an element are in fact also elements with the same order.

The interact confirms that this is true; in fact Lemma 10.3.4 should be true whether p is prime or not, though I won't ask you to prove it.

Lemma 10.3.5 also seems to be working; there are exactly \phi(8)=4 powers here, each of which has order eight. The problem in deciding if there are primitive roots, though, is that there might be another element of the same non-maximal order as the powers of a above which is not one of them! This code shows them for powers of two.

We see that in some sense there are β€˜extra’ elements with order 8 when n=32 (confirming Fact 10.3.3 for this n). If you have eight elements of order eight, and obviously at least one element of order 1, in U_{32}\text{,} then it is impossible to have the required eight elements of order sixteen that one would need for there to be a primitive root modulo 32\text{.} (Why? Because 8+1+8>16=|U_{32}|\text{.}) In essence, the fact that this can't happen for a prime modulus is why primitive roots do exist in that case.