Section10.1Primitive Roots
Or, you can say it hits all the possible colors in the interact! Note that 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.
Remark10.1.2
Sage note:
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.1Two 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)\).
Proof
Subsection10.1.2Finding primitive roots
As a first exercise, the gentle reader should figure out the orders of some elements of some small groups of units. Try exploring \(U_n\) for \(n\in \{5,7,8,9,10,12,14,15\}\). 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.