Chapter 5: 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 21: A Proof of Quadratic Reciprocity; Order Calculations
Today we finished our discussion of quadratic reciprocity by providing a proof of the theorem which is based on Eisenstein's Lemma. Afterwards we began talking about 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 divisibility properties of order.
Lecture 22: Properties of Order
Today we continued our discussion of the order of an integer a modulo m. We discussed many 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 and Polynomials mod p
Today we started our search for those integers which do have a primitive root. We began by considering the case of a prime number p. The main tool we used was an analysis of the properties of polynomials mod p, particularly the number of roots that a given polynomial can have. By counting roots in this way, we were able to conclude that every prime number has a primitive root.
Lecture 24: The Primitive Root Theorem
Today we stated and proved the primitive root theorem, giving a full description of those integers m for which there exists a primitive root modulo m. This involved showing that certain integers can't have primitive roots (based on their prime factorization), and then showing the existence of primitive roots for other moduli. In particular we saw that primitive roots mod $p^2$ can be used to find primitive roots mod $p^m$, where p is an odd prime.
Lecture 25: Order and a Primality Test
We started class by finishing the proof of the Primitive Root theorem: first by reviewing the case when the modulus is $p^m$, then using this to find primitive roots mod $2p^m$. Afterwards we saw an application of order in the land of primality testing. This is our first example of an "easy" test for primality which doesn't require tremendous computation.
Lecture 26: Checking Order; Fun Facts on Mersenne and Fermat Numbers
Today we spent time discussing techniques for checking whether a given number is a primitive root for a given modulus. Hopefully this cleared up some confusion that people had when they worked on Homework 9. We then spent time discussing properties of the Fermat and Mersenne Numbers.
Lecture 27: Index Arithmetic
Today was our last day discussing 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.
page revision: 13, last edited: 03 Nov 2008 18:08