*In which we study the multiplicative group .*

We saw last time that we could reduce the problem of understanding the multiplicative group to studying the groups for primes and for . Today we began on this new task, starting with the case of for prime .

- Lemma 13:
*For any , we have (where the sum is over all divisors of ).*We proved first that the function is multiplicative, and then that when is prime. We also noted that the only property of that we used to show that is multiplicative is that is multiplicative, and so our proof showed that if is a multiplicative function, then is also multiplicative. - Theorem 14 (Lagrange):
*Let be a prime. Let be a polynomial with integer coefficients, with not divisible by . Then the polynomial congruence has at most solutions.*We saw that this can be proved in a similar way to the analogous result in ordinary arithmetic (by induction on the degree of the polynomial), making use of the fact that implies or (that is, is an integral domain). We saw an example that shows that the result does not hold if the requirement that is prime is relaxed. We also saw that the result does not (indeed, cannot) tell us that the congruence has exactly solutions, because there are some polynomial congruences with fewer (indeed, with none). - Theorem 15:
*Let be a prime. Then the multiplicative group is cyclic.*That is, there is some element so that the numbers , , , …, give the whole group. We call such an element a*primitive root*modulo . (Quick check: find all the primitive roots modulo 11, for example. Try to do this with as little work as possible! Can you say anything interesting about which primes have many primitive roots and which have only a few?) We proved this by showing that in , for each divisor of there are exactly elements of order . - Definition of
*primitive roots*(in the statement of the above result).

#### Postscript

I had a question via e-mail from someone who wasn’t quite comfortable with part of the proof that is cyclic. That particular part was the point where I mentioned during the lecture that we were going to use an idea repeatedly, so I’d like people to be clear about it. I’ll state the more general fact here, and hopefully that will be useful to you when you’re working through your lecture notes.

Lemma: *Let be a finite group, and let be an element of with order . Suppose that (using multiplicative notation, so is the multiplicative identity in ). Then . * How could you prove this? You’d like to show that divides , so why not try dividing by , to get say where ? Then what might you do?

#### 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 move on to . Will these groups also turn out to be cyclic?

October 15, 2011 at 5:07 pm

Hi i have something written in my notes that says “log p prime power”.

But i don’t see how log p can be a prime? i mean it isn’t even an integer usually (i tried p = 1,2,3,4 up to 20 and they’re all fractions). Have i misunderstood something?

October 15, 2011 at 5:09 pm

Oh wait. Is it log based then? so log 100 = 2 which is a prime e.g.

October 15, 2011 at 5:17 pm

I’m not quite sure where you mean. Can you be a bit more precise about where this was in your notes?

October 15, 2011 at 10:52 pm

I’ve been a bit of a tfool. i t actually said “wlog p a prime power”.

October 19, 2011 at 12:08 pm

[…] In one we proved that if and only if , which gives the result. In the second, we used the existence of a primitive root modulo , say , and showed that is a quadratic residue if and only if is even. And in the third […]

October 23, 2011 at 4:32 pm

[…] is something that I was lecturing on the other day. There I was talking to third-year Cambridge undergraduates, who know quite a bit of mathematics […]