Section 10.1 Primitive Roots
Subsection 10.1.1 Definition
Definition 10.1.1.
We say that

xxxxxxxxxx
import matplotlib.pyplot as plt
from matplotlib.ticker import IndexLocator, FuncFormatter
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)
Sage note 10.1.3. Filtering list comprehensions.
We are only looking at units here. Where does this show up in the code? The syntax [x for y in range(1,mod) if func(x)]
takes list comprehensions to another level, by βfilteringβ. This allows us to remove from the list anything which doesn't fit what we want. In this case, we removed non-units; gcd(a,mod)==1
was required.
Subsection 10.1.2 Two characterizations
Proposition 10.1.4.
There are two equivalent ways to characterize/define a primitive root of
We say that
is a primitive root of if yields every element ofWe say that
is a primitive root of if the order of is
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. ForQuestion 10.1.5.
In exploring
Were all elements primitive roots?
Did all of these groups have primitive roots?
Is it particularly fun to look for them?