Skip to main content
Logo image

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).
Colored table of powers modulo \(n=11\)
Figure 10.0.1. Colored table of powers modulo \(n=11\)
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.