*In which we prove Lagrange’s theorem, and deduce many interesting results as a consequence.*

- Lemma 33:
*Let be a subgroup of a group . Take , . Then if and only if .*For one direction we noted that so if the two left cosets are the same then and that gave us . For the other direction, we showed that and similarly the other way round. - Theorem 34 (Lagrange‘s Theorem):
*Let be a finite group and let be a subgroup of . Then .*We showed that the left cosets of partition , and that each left coset of has the same size as . These two immediately give . - Lemma 35:
*Let be a finite group. Take . Then is finite.*We noted that , , , … all lie in the finite set , so we must have some repetition , from which the result followed. - Corollary 36:
*Let be a finite group. Take . Then divides .*We noted that is a subgroup of with order . - Corollary 37:
*Let be prime, let be a finite group with order . Then is cyclic.*If , then we saw that , so is a generator of . - Corollary 38:
*Let be a finite group, take . Then .*This follows from the facts that and . - Theorem 39 (Fermat‘s Little Theorem):
*Let be prime. Let be an integer coprime to . Then .*This is immediate from Corollary 38, since is a group of order . - Theorem 40 (Fermat-Euler Theorem):
*Let be an integer. Define . Let be an integer coprime to . Then .*This is another consequence of Corollary 38, this time noting that is a group of order .

### Understanding today’s lecture

Can you relate Lemma 33 to the two examples of left cosets we saw at the end of the last lecture? Check that it works out.

Having proved Lagrange’s Theorem, I mentioned that there is an alternative way to prove that the left cosets of partition using equivalence relations. Define a relation on by if and only if . Can you show that this is an equivalence relation? What are the equivalence classes? Now complete the proof.

Why is Fermat’s Little Theorem a special case of the Fermat-Euler Theorem?

When I reminded you of what an equivalence relation is, I gave as an example the relation on a group , defined by if and only if or . Can you show that this really is an equivalence relation? What are the equivalence classes?

Let be a prime. Which elements of (a group under multiplication) are self-inverse ()? What are the equivalence classes for the equivalence relation from the last paragraph when applied to this group? What does this tell us about the product modulo ? The result here is called Wilson‘s theorem; you can read more about it in Richard Earl’s online notes, or in my blog post.

Let be a finite group with even order. Can you show that must contain an element of order 2? (Hint: use the equivalence relation from the paragraph before last.) Again, you can read more about this in the online notes, but I strongly recommend that you try to deduce it for yourself first, it’s good practice.

### Further reading

I’ve written about several of these topics before on this blog. I’ve written about Lagrange’s Theorem (not be confused with another Lagrange’s Theorem that I’ve also written about), and about Fermat’s Little Theorem (that post outlines the three proofs I mentioned in today’s lecture). Remember to watch out for tigers.

The Euler totient function has many interesting properties. Can you show that if is prime then ? What is for a general integer ? It turns out that is *multiplicative*: if and are coprime, then . (Note that it’s important here that and are coprime!) Can you prove this? There’s a nice connection with the Chinese Remainder Theorem. You can read more about the function in a number theory book (such as *The Higher Arithmetic* by Davenport), or online (e.g. of course Wikipedia has a page).

### Preparation for Lecture 9

Lecture 9 is weeks away, so for now I suggest that you prepare by working on the material from the first four weeks of the course. If you understand that really well, then you’ll be ready for next term. I’ll put some more specific questions up for you to consider a few days before Lecture 9, so check back nearer the time.

March 18, 2015 at 4:56 pm

I’ve just remembered that I meant to include a couple of other things in this blog post.

In an ‘understanding today’s lecture’ spirit (several days after the lecture), can you show that if is a prime with then is not a square modulo (that is, there is no with )? What if , is a square modulo then?

And for further reading, I meant to point out that Fermat-Euler underpins the RSA cryptosystem. See http://en.wikipedia.org/wiki/RSA_(cryptosystem) for example, or the second year Number Theory course http://www0.maths.ox.ac.uk/courses/course/26269 (there are online notes there from last year that describe RSA).

March 22, 2015 at 4:05 pm

Hi, originally on the online lecture notes at the start there was a page of different notations that were related to groups and group actions. I found this page quite useful, but it does not appear to be there anymore. Is there any chance that it could be uploaded?

Many thanks

March 23, 2015 at 11:13 am

Hopefully the list of notation will reappear soon…

March 23, 2015 at 2:14 pm

Take a look now, it should be sorted. (Please be very nice to Richard Earl the next time you see him!)

March 23, 2015 at 10:41 pm

Thank you every so much 🙂

April 22, 2015 at 1:40 pm

[…] Expositions of interesting mathematical results « Groups and Group Actions: Lecture 8 […]

May 1, 2015 at 11:15 am

[…] of , and takes different values on different cosets. We saw that if and only if , and then used Lemma 33 to see that this is equivalent to […]

May 4, 2015 at 10:27 am

[…] 55: Let be a finite group, let be a group, let be a homomorphism. Then . We used our proof of Lagrange’s theorem, which showed that if then […]

May 11, 2015 at 11:14 am

[…] Theorem 59 (Orbit-Stabiliser Theorem): Let be a finite group acting on a set . Take . Then . We defined a map from to and showed that it’s a bijection, then used Lagrange’s theorem. […]