NTIC Prime Numbers Have Primitive Roots

Section 10.4 Prime Numbers Have Primitive Roots

We use many of the same techniques and ideas in by proving that every prime number

$p$ has a primitive root. Let's check that this claim is true for at least some primes.

xxxxxxxxxx
 
L=[(p,primitive_root(p)) for p in prime_range(100)]
for item in L:
    print("A primitive root of %s is %s"%(item[0],item[1]))

🔗

So at least we get a primitive root for the first 25 primes.

🔗

Theorem 10.4.1. Primitive Roots Exist for Primes.

Every prime has a primitive root. In other words, the order $p-1$ group $U_p$ is always cyclic.

🔗

Proof.

We will actually prove a stronger claim below, Claim 10.4.4, that the number of elements of order $d$ (a positive divisor of $n$) is $\phi(d)\text{.}$ Naturally this will be non-zero for $d=p-1\text{,}$ which proves the theorem.

For those with more experience with groups, a good exercise would be to convert it into a statement about the number of elements of each order of any cyclic group.

🔗

Before we examine the claim, we need some discussion.

🔗

Example 10.4.2.

First, it is useful to see what these sets look like for two examples – one where we know we have a primitive root, and one where we know we don't.

Assuming you are online, evaluate the next cell to get the list of sets of different order elements for $n=41\text{:}$

xxxxxxxxxx
 
for d in divisors(40):
    L=[]
    for a in range(1,41):
        if mod(a,41).multiplicative_order()==d:
            L.append(a)
    pretty_print(html(r"There are $%s=\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))

But here is the list of sets for $n=32\text{;}$ there aren't any for the highest possible order, and all the other sets have orders exact multiples of $\phi(d)\text{.}$

xxxxxxxxxx
 
for d in divisors(euler_phi(32)):
    L=[]
    for a in range(1,32):
        if mod(a,2)==1 and mod(a,32).multiplicative_order()==d:
            L.append(a)
    if len(L)==euler_phi(d):
        pretty_print(html(r"There are $%s=\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))
    else:
        pretty_print(html(r"There are $%s\neq\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))

As always, doing an entire example manually is very instructive too.

🔗

For another set of ideas, recall that if

$g$ is a primitive root of

$p\text{,}$ by definition

$g^{p-1}\equiv 1$ but no previous positive power is. Assuming

$p$ is an odd prime, then

$p-1$ is even, and we could try to separate out the odd and even powers

$\begin{equation*} g,g^3,g^5,\ldots\text{ and }g^2,g^4,g^6,\ldots \end{equation*}$

🔗

and compare them or their products.

🔗

Question 10.4.3.

Let $g$ be a primitive root of $p\text{.}$

Can you see why the inverse of an even power of a primitive root is also an even power?
Do you think an odd power (greater than one) of a primitive root $g$ could be a different primitive root $g'\text{?}$ Why or why not? What about even powers of a given primitive root – could they be primitive roots, at least in principle?

🔗

Now let's prove our claim.

🔗

Claim 10.4.4.

If $p$ is prime, the number of elements of $U_p$ of order $d$ is $\phi(d)$ (where of necessity $d$ is a positive divisor of $\phi(p)=p-1$ ).

🔗

Proof.

Assume that $p$ is prime. For any of the divisors $d$ of $p-1$ (not just $p-1$ itself), consider the possible number of elements of $U_p$ with that order,

\begin{equation*} \left|\{a\in U_p \mid a\text{ has order }d\}\right|\text{.} \end{equation*}

By Lemma 10.3.5, this quantity is clearly between zero and $\phi(d)\text{.}$ On the other hand, by Lemma 10.3.4, once we find one $a$ with order $d\text{,}$ then all the powers of $a$ coprime to $d$ also have that order (and are distinct), so there are at least $\phi(d)$ of them.

In particular, the cardinality of the set of elements of $U_p$ of order $d$ is always either zero or $\phi(d)>0\text{,}$ so the entire proof boils down to finding at least one element $a$ with order $d$ for each potential order $d\text{.}$ (The reason we just need to consider $d\mid p-1$ is Theorem 8.3.12 that the order of any element of a group divides the order of the group, so the only possible orders of elements in $U_p$ are positive divisors of $p-1\text{.}$)

Suppose that at least one of the sets for some divisor $d'$ (such as the set of primitive roots, if $d'=p-1$) is empty. Then on the one hand, every element of $U_p$ has some order, so

\begin{equation*} p-1=\sum_{d\mid p-1} \left|\{a\in U_p \mid a\text{ has order }d\}\right|\leq 0+\sum_{d\mid p-1, d\neq d'} \phi(d)\text{.} \end{equation*}

On the other hand, Fact 9.5.4 with $n=p-1$ tells us that

\begin{equation*} \sum_{d\mid p-1, d\neq d'} \phi(d)\lt \sum_{d\mid p-1} \phi(d)=p-1\text{.} \end{equation*}

Combining these two inequalities yields $p-1\lt p-1\text{,}$ an absurdity.

🔗

The proof above makes it evident that the real place primality is used is in the crucial lemmas 10.3.5 and 10.3.4. If you are still curious to see how this works, you can explore more online in the following interact; when there is not a primitive root, somehow the ‘extra’ elements of

$U_n$ which ‘would have’ had order

$\phi(n)$ are distributed nicely among the remaining potential orders.

xxxxxxxxxx
 
@interact
def _(n=(25,[0..100])):
    for d in divisors(euler_phi(n)):
        L=[]
        for a in range(1,n):
            if gcd(a,n)==1 and mod(a,n).multiplicative_order()==d:
                L.append(a)
        if len(L)==euler_phi(d):
            pretty_print(html(r"There are $%s=\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))
        else:
            pretty_print(html(r"There are $%s\neq\phi(%s)$ elements of order $%s$ - "%(len(L),d,d)+str(L)))