Definition10.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)\).
Section10.1Primitive Roots¶ permalink
Subsection10.1.1Definition
Or, you can say it hits all the possible colors in the interact! For composite \(n\), this won't mean all colors per se, just all colors that represent units. So for such moduli, we shrink the number of rows down for this final interact. This has rows that are the elements of \(U_n\), but certainly not labeled correctly.
Sage note10.1.2Filtering list comprehensions
We are only looking at units here. 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.
Subsection10.1.2Two characterizations
Proposition10.1.3
There are two equivalent ways to characterize/define a primitive root of \(n\) among numbers such that \(\gcd(a,n)=1\).
We say that \(a\) is a primitive root of \(n\) if \(a^b\) yields every element of \(U_n\).
We say that \(a\) is a primitive root of \(n\) if the order of \(a\) is \(\phi(n)\).
Subsection10.1.3Finding primitive roots¶ permalink
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\}\), try exploring \(U_n\). There should be at least some primitive roots.
Were all elements primitive roots?
Did all of these groups have them?
Is it particularly fun to look?
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.