Chapter 10 Primitive Roots
There is deeper structure in the group of units than one might at first suspect. This chapter explores that structure.
To start off, remember our search for patterns in the powers of \(a\) (mod \(n\))? That is, we looked for patterns in \(a^b\) mod(\(n\)). One of the things we discovered was Fermat's Little Theorem, which was that the first and last columns of the following graphic were the same color (representing one).
There is lots left to discover, though. Can you find more by using the following interact?
Sage note 10.0.2. Reminder for colormaps.
Remember, to get a gray-scale plot, just change the part with plt.get_cmap('gist_earth',...) to use 'gray', or some other colormap (see Sage note 8.2.2) of your choice.
Have you made the observation that sometimes we get all colors in a single row? This means that (at least sometimes) \(a^b\) (mod \(n\)) goes through every single number when we do enough powers \(a^b\text{.}\)
It turns out that this concept has a name, and is the last of the big concepts of basic congruence number theory.
Summary: Primitive Roots
This chapter uses groups to uncover one of the most profound insights of Figure 10.0.1.
We begin by defining primitive roots in Definition 10.1.1, and immediately recharacterizing in terms of group theory in Proposition 10.1.4.
A simpler way to test for whether a number is a primitive root is Lemma 10.2.3.
In the next section we see some examples of numbers which do not have primitive roots. More importantly, we tackle the key Lemmas 10.3.4 and 10.3.5 to understand the group \(U_p\) for \(p\) prime. An example of something we win from this is Fact 10.3.6.
Then we prove the famous result that Primitive Roots Exist for Primes.
We conclude the chapter by using primitive roots to help solve interesting congruences, like higher degree polynomials in Subsection 10.5.1 and discrete analogues of the logarithm in Subsection 10.5.2.
There is the usual variety of Exercises, and a short appendix about All the Primitive Roots.