Chapter 5 - Order and Primitive Roots

Chapter 5 is all about orders modulo m. The big theorem in this chapter is the theorem of the primitive element, which characterizes those moduli m for which a primitive root exists.

Lecture 22: Order Calculations
We started the class by introducing the notion of order for a given integer a modulo m, as well as what it meant for a to be a primitive root modulo m. We calculated the order of a few integers, and we began talking about one of the basic arithmetic properties of order including its relationship to $\phi(m)$ as well as how one can predict the order of a power of an integer based on the order of the integer itself. We also discussed primitive roots more deeply, counting the number of primitive roots when they exist.
Lecture 23: Primitive Roots mod p
In today's class we began by paying back some IOUs from last class, particular proving a lemma and a corollary which allow us to compute the order of a power of a once you know the order of a itself. Afterwards we settled on trying to determine which numbers have primitive roots, and we began our hunt with prime numbers. In particular we saw that polynomials "behave nicely" modulo p, in the sense that the number of solutions to a congruence $f(x) \equiv 0 \mod{p}$ is bounded by the degree of f (at least when the coefficients of f aren't all multiples of p). We used this to count exactly the number of solutions to a certain equation, which is a key step in showing that primitive roots exist modulo p.
Lecture 24: Moduli without Primitive Roots
In today's class we finished proving a critical result concerning the number of elements of order d modulo p, where p is a prime number. This let's us conclude that primitive roots do exist modulo p. We then spent the second half of the class discussing integers for which primitive roots do not exist. We finished the class by classifying exactly those integers which do have primitive roots.
Lecture 25: The Primitive Root Theorem
Today we proved the (majority of) the primitive root theorem, and so we are now able to determine exactly which moduli m have primitive roots. Indeed, this means we can count precisely how many primitive roots a number m has just by looking at a factorization of m.
Lecture 26: Index Arithmetic
Today we covered the final topic of Chapter 5, and we spent the bulk of the day discussing the idea of index relatively to a given primitive root mod m. The index is akin to the logarithm functions you have seen in your pre-number theory years, and it obeys many of the same rules. We'll use index arithmetic to determine when a given number a is an nth power residue mod m — at least when m has a primitive root.