*In which we study the multiplicative groups .*

- Lemma 16:
*Let be prime. Then there is a primitive root modulo , say , such that where is coprime to . That is, but .*We saw last time that there is*some*primitive root modulo ; we proved this lemma by showing that either this or will do the job.

- Lemma 17:
*Let be a prime greater than 2, and let be a natural number. Then there is a primitive root modulo , say , such that .*We proved this by induction on , using the previous lemma to give the base case. - Theorem 18:
*Let be a prime greater than 2, and let be a natural number. Then is cyclic.*We showed that the of the previous two lemmas is a primitive root modulo (so if is a primitive root modulo and also modulo , then it is a primitive root modulo for all ). (Quick check: why did I bother to prove separately that is cyclic, rather than deducing it as a special case of this theorem?)

#### Further reading (and thinking!)

You might well now wonder what the group is like, and this would be a good question to investigate. You could also try to classify those for which is cyclic. Baker (*A concise introduction to the theory of numbers*) deals with this and the material from today’s lecture in an extremely concise way; Jones and Jones (*Elementary Number Theory*) explain it in gory detail, with examples.

#### Preparation for Lecture 6

Our next questions will be to do with when we can solve the congruence . (We’ll look at moduli that aren’t prime too, but we’ll start with primes.) Here are a few questions that you could usefully consider (you could try numerical examples to get a feel for what’s going on, then make some conjectures, and then try to prove those conjectures).

- How many squares are there modulo a prime ? And how many proofs can you find for your answer? (Example of what I mean: 1, 2 and 4 are squares modulo 7, because , , and , but 3, 5 and 6 are not squares modulo 7. We tend not to worry too much about 0, since this is never going to be an interesting case.)
- Let be a prime. Why must be congruent to modulo ? Which give , and which give ?
- For which primes is a square?
- For which primes is a square?

October 23, 2011 at 4:32 pm

[…] let you experiment a bit to find an example of a modulus where there are no primitive roots. But it turns out that if is an odd prime then there is a primitive root modulo any power of , and thanks to the […]