In order to find primitive roots, we might want to better approach than simple 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 \[a^{10}\equiv 1\text{ mod }(11)\; ,\] but which ones don't have it 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\). \[2^2\equiv 4\not\equiv 1\text{ mod }(11)\text{ and }2^5=32\equiv -1\not\equiv 1\text{ mod }(11)\;, \] so \(2\) must be a primitive root.
What about with \(a=3\)? \[3^5=9\cdot 9\cdot 3\equiv (-2)^2\cdot 3\equiv 12\equiv 1\text{ mod }(11)\] 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.
Remark10.2.2
Sage note: 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 \[a^{\phi(n)/q}\not\equiv 1\text{ in }U_n\text{ for each prime }q\mid \phi(n)\; .\]
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, \[q\mid \phi(n)/k\] so \[qk\ell=\phi(n)\text{ for some }\ell\] which means \[k\ell=\phi(n)/q\; .\] But then \(\phi(n)/q\) is a multiple of \(k\), and if \(a^k\equiv 1\), then certainly \[a^{k\ell}=a^{\phi(n)/q}\equiv 1\text{ mod }(n)\] as well.
This is a little terse, so let's unpack this test. Essentially, two things change from trying all divisors of \(\phi(n)\):
Instead of trying divisors of \(\phi(n)\), we try \(\phi(n)\) divided by divisors. So \(2^5\) becomes \(2^{10/2}\) and \(3^2\) becomes \(3^{10/5}\). Which seems like it's not doing anything other than rewriting, but at least organizes things differently.
Now, instead of having to try all \(\phi(n)/d\), we will use a trick to just need prime \(d\). See the proof below.
Even so, the lemma is probably still a little hard to understand, but with some examples it will make sense.
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.
Subsection10.2.1Using the test lemma
Why not try it by hand for \(n=17\)? There is only one prime divisor of \(\phi(17)\), which makes things easier.
\(a\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Primitive?
This lemma also makes easy some statements that would otherwise be quite hard. For instance, you should see how to prove (using this) that if \(a\) is a primitive root of \(n\), then so is \(a^{-1}\) (modulo \(n\)).
Here's something harder.
Proposition10.2.5
If \(a\) is a primitive root of \(n\), then so is \(n-a\) if \(4\mid \phi(n)\).
