*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?

#### Further reading

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?

October 18, 2013 at 1:00 pm

If g is a primitive root mod p but not mod p^2 we use g+p instead; but g and g+p are the same thing mod p. So I started wondering whether there always exists a primitive root mod p^2 smaller than p. I did not come up with anything and if it is not the case it will probably be pretty hard to find a counterexample since the chance of g not being a primitive root mod p^2 is 1/p. However, I have found a website (http://primes.utm.edu/curios/page.php/40487.html) according to which there are not many p^2 such that the smallest primitive root mod p is not a primitive root mod p^2 and, more interestingly, that it is not known whether there are infinitely many of those.

October 21, 2013 at 10:36 am

[…] Expositions of interesting mathematical results « Number Theory: Lecture 4 […]

October 25, 2013 at 10:33 pm

We proved in the supervision today that if g is a primitive root mod p, then either g or g^(-1) is a primitive root mod p^2. The proof is not difficult and it solves my problem from the post above.