Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section10.1Primitive Roots

Subsection10.1.1Definition

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)\).

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

Subsection10.1.3Finding 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\}\), 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.