NTIC When Does a Primitive Root Exist?

Section 10.3 When Does a Primitive Root Exist?

Recall your experimentation in Subsection 10.1.3. You should have discovered that there is not always a primitive root.

🔗

Fact 10.3.1.

There is no primitive root for $n=12\text{.}$

🔗

Proof.

See Exercise 10.6.4.

🔗

This is also the case for

$n=8$ (Exercise 10.6.3). So, when do we have primitive roots?

🔗

Subsection 10.3.1 Primitive roots of powers of two

🔗

We'll start this investigation by proving that most powers of 2 do not have primitive roots. The following should give you an error.

xxxxxxxxxx
 
power=25
primitive_root(2^power)

🔗

Proposition 10.3.2.

For $k> 2\text{,}$ there are no elements of $U_{2^k}$ that have order $\phi(2^k)=2^{k-1}\text{,}$ because the highest order they can have is $2^{k-2}\text{.}$

🔗

Assume $n=2^k$ for $k>2\text{.}$ (For $n=2$ and $n=4\text{,}$ there are primitive roots – check this if you haven't already). In Exercise 10.6.3 we show that $n=8$ does not have a primitive root. In particular, each element of $U_8$ has order $2^{3-2}=2\text{,}$ so that $a^2\equiv 1$ (mod $8$) for all $a\in U_8\text{.}$

Think of $n=8=2^3$ as a base case for induction on $k\geq 3\text{.}$ Now assume by induction that for $n=2^k$ it is true that no element has order higher than $2^{k-2}\text{.}$ I.e.,

\begin{equation*} a^{2^{k-2}}\equiv 1\text{ (mod }2^k)\text{.} \end{equation*}

By definition of divisibility, that means for any odd number $a\text{,}$ we have that

\begin{equation*} a^{2^{k-2}}=1+2^k\cdot m \end{equation*}

for some integer $m\text{.}$

Next, let's look at what happens to everything in modulus $2^{k+1}\text{.}$ We want that

\begin{equation*} a^{2^{(k+1)-2}}=a^{2^{k-1}}\equiv 1\text{ (mod }2^{k+1})\text{.} \end{equation*}

While it's easy to get $2^{k+1}$ from $2^k\text{,}$ the only way to easily get $a^{2^{k-1}}$ from $a^{2^{k-2}}$ is by squaring. (Recall Fact 4.5.5 where we found powers quickly by using $(a^{2^e})^2=a^{2^{e+1}}\text{.}$)

So we write $a^{2^{k-1}}$ as a square, substitute the above, and look at the remainders.

\begin{equation*} a^{2^{k-1}}=\left(a^{2^{k-2}}\right)^2=(1+2^k m)^2=1+2^{k+1}m+2^{2k}m^2 \end{equation*}

\begin{equation*} =1+2^{k+1}(m+2^{k-1}m^2)\equiv 1\text{ mod }2^{k+1} \end{equation*}

By induction we are done; because the highest possible order of an element is less than $\phi\text{,}$ there are no primitive roots modulo $2^k$ for $k>2\text{.}$ (Remember by Lagrange's Theorem on Group Order in any case the order is a power of two.)

xxxxxxxxxx
 
primitive_root(64)

🔗

Fact 10.3.3.

It turns out that $\pm 5$ have order $2^{k-2}$ in $U_{2^k}\text{.}$

🔗

Proof.

We won't prove this, but it is easy if you use just a little group theory.

🔗

One can also demonstrate this fact computationally for a given example.

xxxxxxxxxx
 
@interact
def _(power=5):
    a = mod(5,2^power)
    pretty_print(html("Powers of 5 modulo $2^{%s}$ are"%power))
    print([a^i for i in [1..2^(power-1)]])

🔗

Subsection 10.3.2 Two important lemmas

🔗

There follow two important lemmas¹Or lemmata, but who's counting? for working with primitive roots, whose proofs are valuable exercises.

🔗

Subsubsection 10.3.2.1 How the lemmas work

🔗

Lemma 10.3.4.

Suppose $p$ is prime and the order of $a$ modulo $p$ is $d\text{.}$ If $b$ and $d$ are coprime, then $a^b$ also has order $d$ modulo $p\text{.}$

🔗

Proof.

See Exercise 10.6.6.

🔗

Lemma 10.3.5.

Suppose $p$ is prime and $d$ divides $p-1$ (and hence is a possible order of an element of $U_p$ ). There are at most $\phi(d)$ incongruent integers modulo $p$ which have order $d$ modulo $p\text{.}$

🔗

Proof.

See Exercise 10.6.7.

🔗

Before using them a lot, we should unpack these results a little bit. Here is a first taste.

🔗

Fact 10.3.6.

If there is one primitive root of $n\text{,}$ then there are actually $\phi(\phi(n))$ of them.

🔗

Proof.

We will only deal with the case of $n=p$ prime (see Exercise 10.6.10 for the rest).

In Lemma 10.3.4, let the order of $a$ be $p-1\text{.}$ Then $a$ is a primitive root modulo $p\text{,}$ and so is $a^b$ for every $b$ coprime to $p-1\text{.}$ Since there are $\phi(p-1)$ of these, it satisfies the claim. By the Lemma 10.3.5, there can't be more.

🔗

It works; let's check this out interactively.

xxxxxxxxxx
 
@interact
def _(p=(41,prime_range(100))):
    a=mod(primitive_root(p),p)
    pretty_print(html("$%s$ is a primitive root of $%s$, with order $%s$"%(a,p,p-1)))
    L=[(i,a^i,(a^i).multiplicative_order()) for i in range(2,p-1) if gcd(i,p-1)==1]
    for item in L:
        pretty_print(html(r"$%s^{%s}\equiv %s$ also has order $%s$ (and $\gcd(%s,%s)=1$)"%(a, item[0], item[1], item[2], item[0], p-1)))

🔗

Subsubsection 10.3.2.2 How the lemmas (don't) fail

🔗

To continue, let's pick a non-prime number we know something about to see how many numbers we have with a given order.

🔗

We saw in Proposition 10.3.2 that powers of two (past 4) do not have primitive roots, but

$U_{2^k}$ does have lots of elements with the next smallest possible order. So, for example, for

$n=32$ we can look at whether powers

$b$ coprime to that order (

$8$ ) of such an element are in fact also elements with the same order.

xxxxxxxxxx
 
@interact
def _(n=5):
    pretty_print(html("Modulo $2^%s"%n))
    a=mod(5,2^n)
    L=[(i,a^i,(a^i).multiplicative_order()) for i in range(1,a.multiplicative_order()) if gcd(i,a.multiplicative_order())==1]
    for item in L:
        pretty_print(html(r"$%s^{%s}\equiv %s$ has order $%s$ (and $\gcd(%s,%s)=1$)"%(a, item[0], item[1], item[2], item[0], a.multiplicative_order())))

🔗

The interact confirms that this is true; in fact Lemma 10.3.4 should be true whether

$p$ is prime or not, though I won't ask you to prove it.

🔗

Lemma 10.3.5 also seems to be working; there are exactly

$\phi(8)=4$ powers here, each of which has order eight. The problem in deciding if there are primitive roots, though, is that there might be another element of the same non-maximal order as the powers of

$a$ above which is not one of them! This code shows them for powers of two.

xxxxxxxxxx
 
@interact
def _(n=5):
    pretty_print(html("Modulo $2^%s"%n))
    a=mod(-5,2^n)
    L=[(i,a^i,(a^i).multiplicative_order()) for i in range(1,a.multiplicative_order()) if gcd(i,a.multiplicative_order())==1]
    for item in L:
        pretty_print(html(r"$%s^{%s}\equiv %s$ has order $%s$ (and $\gcd(%s,%s)=1$)"%(a, item[0], item[1], item[2], item[0], a.multiplicative_order())))

🔗

We see that in some sense there are ‘extra’ elements with order

$8$ when

$n=32$ (confirming Fact 10.3.3 for this

$n$ ). If you have eight elements of order eight, and obviously at least one element of order 1, in

$U_{32}\text{,}$ then it is impossible to have the required eight elements of order sixteen that one would need for there to be a primitive root modulo

$32\text{.}$ (Why? Because

$8+1+8>16=|U_{32}|\text{.}$ ) In essence, the fact that this can't happen for a prime modulus is why primitive roots do exist in that case.