Fact 10.3.1.
There is no primitive root for \(n=12\text{.}\)
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.
Proof.
See Exercise 10.6.4.
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.
Proposition 10.3.2.
For \(k> 2\text{,}\) there are no elements of \(U_{2^k}\) that have order \(\phi(2^k)=2^{k-1}\text{,}\) because the highest order they can have is \(2^{k-2}\text{.}\)
Proof.
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.)
Fact 10.3.3.
It turns out that \(\pm 5\) have order \(2^{k-2}\) in \(U_{2^k}\text{.}\)
Proof.
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 2 about order in the group of units used for working with primitive roots, whose proofs are valuable exercises.
Subsubsection 10.3.2.1 How the lemmas work
Lemma 10.3.4.
Suppose \(p\) is prime and the (multiplicative) order of \(a\) modulo \(p\) is \(d\text{.}\) If \(b\) and \(d\) are coprime, then \(a^b\) also has order \(d\) modulo \(p\text{.}\)
Proof.
See Exercise 10.6.6.
Lemma 10.3.5.
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 multiplicative order \(d\) modulo \(p\text{.}\)
Proof.
See Exercise 10.6.7.
Before using them a lot, we should unpack these results a little bit. Here is a first taste.
Fact 10.3.6.
If there is one primitive root of \(n\text{,}\) then there are actually \(\phi(\phi(n))\) of them.
Proof.
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.
Or lemmata, but who’s counting?
