In which we study the structure of the multiplicative group , and start studying .
- Theorem 15: Let be prime. Then the multiplicative group is cyclic. We proved this by showing that there are exactly elements of order , for each divisor of .
- Definition of a primitive root modulo .
- Lemma 16: Let be prime. Then there is a primitive root modulo , say , such that where . We showed that if is a primitive root modulo , then either or has the required additional property.
- Lemma 17: Let be prime and let be a natural number. Then there is a primitive root modulo , say , such that . We proved this by induction, using similar ideas to those used in Lemma 16.
Understanding today’s lecture
Pick a prime . Can you find a generator (primitive root) modulo ? How many can you find? How little work can you get away with doing? Can you write each element of the multiplicative group as an explicit power of your primitive root?
Can you find any primes that have many primitive roots, or any primes that have very few primitive roots?
Pick a prime . Can you find a generator (primitive root) modulo ? Modulo ?
Can you find an example to show that in Lemma 16 we cannot always use our first choice of primitive root , we really do sometimes have to use instead?
Davenport (The Higher Arithmetic) presents a slightly different proof that is cyclic; you might like to read that for another perspective.
Preparation for Lecture 5
Next time we’ll think about . What structure will they turn out to have?