Skip to main content

Section 10.2 A Better Way to Primitive Roots

Subsection 10.2.1 A 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. Let's walk through an example to motivate a new approach, using a small modulus.

Example 10.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

\begin{equation*} a^{10}\equiv 1\text{ (mod }11)\text{,} \end{equation*}

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.

  • Let's try this with \(a=2\text{.}\)

    \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)\text{,} \end{equation*}

    so \(2\) must be a primitive root.

  • What about with \(a=3\text{?}\)

    \begin{equation*} 3^2 = 9\not\equiv 1\text{ (mod }11)\text{,} \end{equation*}

    so that seems promising, but

    \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\) 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 note 10.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; look for is_gener_expo and is_gener_Fp.

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

\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)\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.

Subsection 10.2.2 Using 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 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

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.

Let's think in terms of powers. If \(a^{\phi(n)/q}\not\equiv 1\text{,}\) then

\begin{equation*} (n-a)^{\phi(n)/q}\equiv (-a)^{\phi(n)/q}\equiv (-1)^{\phi(n)/q}a^{\phi(n)/q}\text{.} \end{equation*}

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.