Section10.2A Better Way to Primitive Roots¶ permalink
Subsection10.2.1A useful lemma
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.
Example10.2.1A motivating example
Let's walk through an example to motivate a new approach, using a small modulus.
Take some number \(n\) with a \(\phi(n)\) with a few factors. Say, \(n=11\) and \(\phi(11)=10\). Okay, we know that every element \(a\in U_{11}\) will have \begin{equation*}a^{10}\equiv 1\text{ (mod }11)\; ,\end{equation*} but which elements don't reach the unit before the tenth power?
Well, we know that the order of an element has to divide \(\phi(11)=10\), so we could try \(a^{2}\) and \(a^5\); no other \(a^k\) could yield 1. In fact, if those aren't \(\equiv 1\), there aren't any other possible orders out there, so that \(a\) would work as a primitive root.
Let's try this with \(a=2\). \begin{equation*}2^2\equiv 4\not\equiv 1\text{ (mod }11)\text{ and }2^5=32\equiv -1\not\equiv 1\text{ (mod }11)\;, \end{equation*} so \(2\) must be a primitive root.
What about with \(a=3\)? \begin{equation*}3^5=9\cdot 9\cdot 3\equiv (-2)^2\cdot 3\equiv 12\equiv 1\text{ (mod }11)\end{equation*} so \(3\) is not a primitive root modulo eleven.
The moral is that we didn't have to check all ten possible powers to decide whether \(a\) was a primitive root modulo eleven.
Now we formalize this, and in fact rephrase it in a slightly more efficient way.
Sage note10.2.2How Sage does primitive roots
As far as I understand the code, this is how even Sage tests for finding primitive roots.
Lemma10.2.3Testing 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)\; .\end{equation*}
If \(a\) is in fact a primitive root, then \(\phi(n)\) is the smallest number \(k\) such that \(a^{k}\equiv 1\), so certainly for numbers smaller than \(\phi(n)\), like \(\phi(n)/q\), those powers shouldn't be \(\equiv 1\).
On the other hand, if \(a\) isn't a primitive root, then its order \(k\) must be a proper divisor of \(\phi(n)\).
Now look at the prime divisors \(q\) of \(\phi(n)/k\).
For such a divisor, \begin{equation*}q\mid \phi(n)/k\end{equation*}
So \(qk\ell=\phi(n)\) for some \(\ell\).
That means \(k\ell=\phi(n)/q\).
But then \(\phi(n)/q\) is a multiple of \(k\).
So since \(a^k\equiv 1\), then certainly \begin{equation*}a^{k\ell}=a^{\phi(n)/q}\equiv 1\text{ (mod }n)\end{equation*} as well, which completes the proof.
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)\):
Instead of trying powers which are divisors of \(\phi(n)\), we try powers which are \(\phi(n)\) divided by divisors. So \(2^5\) becomes \(2^{10/2}\) and \(3^2\) becomes \(3^{10/5}\). 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\), we use a trick to just need prime divisors \(d\). (See the proof.)
Doing some examples slowly will help it make sense.
Subsection10.2.2Using the test lemma
If you try various \(n\) and various attempts at primitive roots \(a\), you will see that this really works. Make sure you are trying \(a\) that are actually coprime to \(n\), though! As it turns out, there aren't very many things 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\)? There is only one prime divisor of \(\phi(17)\), which makes things easier. Fill in this table, where PR means primitive root.
\(a\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PR?
No
No
This 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\), then so is \(a^{-1}\) (modulo \(n\)).
Here's something harder, to show the power of this approach.
Proposition10.2.4
If \(a\) is a primitive root of \(n\), then so is \(n-a\) if \(4\mid \phi(n)\).
Let's think in terms of powers. If \(a^{\phi(n)/q}\not\equiv 1\), then \begin{equation*}(n-a)^{\phi(n)/q}\equiv (-a)^{\phi(n)/q}\equiv (-1)^{\phi(n)/q}a^{\phi(n)/q}\; .\end{equation*}
So, as long as \(\phi(n)/q\) is even for all prime divisors of \(\phi(n)\), the two powers (the one of \(a\) and the one of \(n-a\) are the same.
Since \(\phi(n)\) is already even, the only possible odd \(\phi(n)/q\) comes from \(q=2\).
