In order to find primitive roots, we might want a better approach than simply trying every single power of \(a\) for every \(a\) until we find one. Let’s walk through an example to motivate a new approach, using a small modulus.
Example10.2.1.A motivating example.
Let’s take a number \(n\) such that \(\phi(n)\) has some, but not too many, factors – say, \(n=11\text{,}\)\(\phi(11)=10\text{.}\) Okay, we know that every element \(a\in U_{11}\) will have
but which elements don’t reach the unit before the tenth power?
We know by Theorem 8.3.12 that the order of an element has to divide \(\phi(11)=10\text{,}\) so we could try \(a^{2}\) and \(a^5\text{;}\) no other \(a^k\) could yield 1. In fact, if those aren’t \(\equiv 1\text{,}\) there aren’t any other possible orders out there, so that \(a\) would work as a primitive root.
so \(3\) cannot be a primitive root modulo eleven (and in fact has order five).
The moral is that we didn’t have to check all ten possible powers of \(a=2\) or \(a=3\) to decide whether \(a\) was a primitive root modulo eleven. If you aren’t confident of this idea, try using this strategy to determine which of \(a=4,5,6\) is a primitive root (exactly one of them is).
Now we formalize and rephrase our strategy slightly more efficiently.
Sage note10.2.2.How Sage does primitive roots.
As far as I understand, the following strategy is how even Sage tests for finding primitive roots, at least for basic cases. You can check for yourself by looking at the code from the component program, PARI 1 ; look for is_gener_expo and is_gener_Fp.
Lemma10.2.3.Testing for Primitive Roots.
An element \(a\in U_n\) is a primitive root if and only if
\begin{equation*}
a^{\phi(n)/q}\not\equiv 1\text{ in }U_n\text{ for each prime }q\mid \phi(n)\text{.}
\end{equation*}
If \(a\) is in fact a primitive root, then \(\phi(n)\) is the smallest number \(k\) such that \(a^{k}\equiv 1\text{,}\) so certainly for numbers smaller than \(\phi(n)\text{,}\) like \(\phi(n)/q\text{,}\) those powers shouldn’t be \(\equiv 1\text{.}\)
On the other hand, if \(a\) isn’t a primitive root, then its order \(k\) must be a proper divisor of \(\phi(n)\text{.}\)
Now look at the prime divisors \(q\) of \(\phi(n)/k\text{.}\) For such a divisor,
\begin{equation*}
q\mid \phi(n)/k\text{ so }qk\ell=\phi(n)\text{ for some }\ell\in \mathbb{Z}\text{.}
\end{equation*}
That means \(\phi(n)/q=k\ell\) and so the power \(\phi(n)/q\) in the statement is actually a multiple of the order \(k\text{.}\) Since \(a^k\equiv 1\text{,}\) then certainly
This proof is a little terse, so let’s unpack this test. Essentially, we change two things from the initial idea of trying all divisors of \(\phi(n)\text{:}\)
Instead of trying powers which are divisors of \(\phi(n)\text{,}\) we try powers which are \(\phi(n)\) divided by divisors. So \(2^5\) becomes \(2^{10/2}\) and \(3^2\) becomes \(3^{10/5}\text{.}\) That seems like it’s not doing anything other than rewriting, but at least it organizes things differently.
Then, instead of having to try all \(\phi(n)/d\text{,}\) we use a trick to just need prime divisors \(d\text{.}\) (See the proof.)
Doing some examples slowly will help it make sense. Once you have done so, try the interact.
Subsection10.2.2Using the test lemma
If you tried various \(n\) and various attempts at primitive roots \(a\) above, you will see that Lemma 10.2.3 really works. Make sure you are trying \(a\) that are actually coprime to \(n\text{,}\) though! As it turns out, there aren’t very many test powers to try, since \(\phi(n)\) in general doesn’t have a lot of prime divisors, even if \(n\) is a fairly large prime.
Why not try it by hand for \(n=17\text{?}\) There is only one prime divisor of \(\phi(17)\text{,}\) which makes things easier. Fill in Table 10.2.4, where PR means primitive root.
Table10.2.4.Check which numbers are primitive roots
\(a\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PR?
No
No
The lemma also makes easy some statements that would otherwise be quite hard. For instance, you should (Exercise 10.6.2) see how to use the test lemma to prove that if \(a\) is a primitive root of \(n\text{,}\) then so is \(a^{-1}\) (modulo \(n\)).
Here’s something harder, to show the power of this approach.
Proposition10.2.5.
If \(a\) is a primitive root of \(n\text{,}\) then so is \(n-a\) if \(4\mid \phi(n)\text{.}\)
So, as long as \(\phi(n)/q\) is even for all prime divisors of \(\phi(n)\text{,}\) the two powers (the one of \(a\) and the one of \(n-a\)) come to the same thing.
Since \(\phi(n)\) is already assumed to be even, the only possible odd \(\phi(n)/q\) comes from \(q=2\text{,}\) but \(\phi(n)\) is assumed to be divisible by four, so \(\phi(n)/q\) will be even.
Example10.2.6.
If you did the table at the beginning of this subsection properly, you will note that \(3\) and \(14\) are a pair of primitive roots of seventeen. There should be three other such pairs.
On the other hand, from the proof we can see that if \(\phi(n)\) is even, but not divisible by four, then we expect that if \(a\) is a PR then \(n-a\) will not be. For example, since two is a primitive root of eleven in Example 10.2.1, we expect that nine is not; try computing this yourself.
