NTIC Primitive Roots

Subsection 10.1.1 Definition

Definition 10.1.1.

We say that $a\in U_n$ is a primitive root of $n$ when $a^b$ runs through all elements of $U_n$ for $1\leq b\leq \phi(n)\text{.}$

🔗

Or, you can say the row corresponding to a primitive root hits all the possible colors in the visualization! For composite

$n\text{,}$ this won't mean all colors per se, just all colors that represent units. (See the colorbar below.) So for such moduli, we shrink the number of rows down for this visualization; it has rows only for the elements of

$U_n\text{.}$

🔗

By the way, can you ‘see’ Euler's Theorem in this graphic? (Don't forget that it generalizes Fermat's Little Theorem.) Try exploring it in the interact as well, which allows not just for prime moduli but composite ones as well.

🔗
FigureColored table of powers (of units) modulo $n=10$

xxxxxxxxxx
 
import matplotlib.pyplot as plt
from matplotlib.ticker import IndexLocator, FuncFormatter
@interact
def power_table_plot(modulus=(10,srange(3,50))):
    Zm = Integers(modulus)
    ls = Zm.list_of_elements_of_multiplicative_group()
    mycmap = plt.get_cmap('jet',modulus-1)
    myloccb = IndexLocator(ceil(modulus/10),.5)
    myloc = myloccb
    myform = FuncFormatter(lambda x,y: ls[min(int(x),len(ls)-1)])
    cbaropts = {  'ticks':myloccb, 'drawedges':True, 'boundaries':srange(.5,modulus+.5,1)}
    P=matrix_plot(matrix(euler_phi(modulus), [mod(a,modulus)^b for a in range(1,modulus) for b in srange(euler_phi(modulus)+1) if gcd(a,modulus)==1]), cmap=mycmap, colorbar=True, colorbar_options=cbaropts, ticks=[None,myloc], tick_formatter=[None,myform])
    show(P,figsize=6)

🔗

Subsection 10.1.2 Two characterizations

🔗

Proposition 10.1.4.

There are two equivalent ways to characterize/define a primitive root of $n$ among numbers such that $\gcd(a,n)=1\text{.}$

We say that $a$ is a primitive root of $n$ if $a^b$ yields every element of $U_n\text{.}$
We say that $a$ is a primitive root of $n$ if the order of $a$ is $\phi(n)\text{.}$

🔗

Proof.

Why are these true? Recalling the terminology from Section 8.3, the first one means that $U_n$ is a cyclic group (one all of whose elements are powers of a specific element), and that $a$ is a generator of that group. This is the more advanced point of view.

The second point of view also uses the group idea of the order of an element. Remember, this is the smallest number of times you can multiply something by itself and get 1 as a result. What would this idea mean without using the terminology of groups? With that viewpoint, $k$ is the order of $a$ if $a^k\equiv 1$ (mod $n$) and $a^b\not \equiv 1$ for $1\leq b<k\text{.}$

🔗

Subsection 10.1.3 Finding primitive roots

🔗

As a first exercise, the gentle reader should figure out the orders of some elements of some small groups of units. For

$n\in \{5,7,8,9,10,12,14,15\}\text{,}$ try exploring

$U_n\text{.}$ There should be at least some primitive roots.

🔗

Question 10.1.5.

In exploring $U_n$ for some $n\in \{5,7,8,9,10,12,14,15\}\text{:}$

Were all elements primitive roots?
Did all of these groups have primitive roots?
Is it particularly fun to look for them?

🔗

It's useful to try looking for primitive roots by hand. However, it's better to know whether one should bother to look, and hence to try to prove things about orders in general.

Number Theory: In Context and Interactive

Section 10.1 Primitive Roots