NTIC A Better Way to Primitive Roots

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 $ϕ (n)$ has some, but not too many, factors – say, $n = 11,$ $ϕ (11) = 10 .$ Okay, we know that every element $a \in U_{11}$ will have

a^{10} \equiv 1 (mod 11),

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 $ϕ (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 ≢ 1 (mod 11) and 2^{5} = 32 \equiv - 1 ≢ 1 (mod 11),$

so $2$ must be a primitive root.
What about with $a = 3 ?$

$3^{2} = 9 ≢ 1 (mod 11),$

so that seems promising, but

$3^{5} = 9 \cdot 9 \cdot 3 \equiv (- 2)^{2} \cdot 3 \equiv 12 \equiv 1 (mod 11)$

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.

🔗

Lemma 10.2.3. Testing for Primitive Roots.

An element $a \in U_{n}$ is a primitive root if and only if

a^{ϕ (n) / q} ≢ 1 in U_{n} for each prime q ∣ ϕ (n) .

🔗

Proof.

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

ϕ (n) :

Instead of trying powers which are divisors of $ϕ (n),$ we try powers which are $ϕ (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 $ϕ (n) / d,$ we use a trick to just need prime divisors $d .$ (See the proof.)

🔗

Doing some examples slowly will help it make sense. Once you have done so, try the interact.

xxxxxxxxxx
 
@interact
def _(n=(19,[2..100]),a=3):
    phi=euler_phi(n)
    pds=prime_divisors(phi)
    if gcd(a,n)!=1:
        pretty_print(html("Make sure $a$ and $n$ are relatively prime!"))
    else:
        a = mod(a,n)
        pretty_print(html("Is $%s$ a primitive root of $%s$?"%(a,n)))
        pretty_print(html(r"The prime divisors of $\phi(%s)=%s$ are $%s$"%(n, euler_phi(n), ','.join([str(pd) for pd in pds]))))
        pretty_print(html("The powers are "+' and '.join([r'$%s^{%s/%s}\equiv %s$'%(a,phi,pd,a^(phi/pd)) for pd in pds])))
        pretty_print(html("And the order of a=$%s$ is <tt>a.multiplicative_order()</tt>=$%s$"%( a , a.multiplicative_order())))

🔗

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,

though! As it turns out, there aren't very many test powers to try, since

ϕ (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

ϕ (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

🔗

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,

then so is

a^{- 1}

(modulo

n

🔗

Here's something harder, to show the power of this approach.

🔗

Proposition 10.2.4.

If $a$ is a primitive root of $n,$ then so is $n - a$ if $4 ∣ ϕ (n) .$

🔗

Proof.

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.

🔗

Example 10.2.5.

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 $ϕ (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.