The term has just started, and so I have been contemplating the exciting mathematics in store for the new first years. This week I thought I’d tell you about one such result.

New students often find that some of the mathematics they meet at university is more abstract than the mathematics they studied at school. Abstraction can be an extremely useful tool. Broadly speaking, here’s what happens. Mathematicians notice several examples of the same behaviour. They want to explore why: what is it about those situations that leads to the same behaviour? They try to write down a list of those key properties. They then define a new object: it’s anything that has those properties. (So all of the initial situations should be examples of this new kind of object.) That should hopefully lead to a better understanding of what’s going on. Moreover, if mathematicians can prove something about this object using only the knowledge that the object has those key properties, then they have proved a result about *every* example of that object — all in one go!

One good example of this is the notion of a group. I’m not going to go through the definition of a group in great detail here, so if you haven’t come across the concept before then you might like to read this article on NRICH. Here, I’ll remind you of the definition of a group and give a few examples.

A *group* is a set and a binary operation that satisfy the group axioms. So is a map that takes two elements of as input, and gives one element of as output. There are three group axioms.

- The operation is associative. That is, for any , and in . (So one can write without any ambiguity.)
- There is an identity element in . That is, there is some in so that for any in . (“Combining with has no effect.”)
- Each element of has an inverse in . That is, for each in there is some element in so that . (The inverse of is often written as — this should not be confused with the usual reciprocal !)

Here are some examples of groups.

- The integers under addition. (The identity is , and the inverse of is .)
- The positive rational numbers under multiplication. (The identity is , and the inverse of is .)
- The symmetries of a square, illustrated on Wikipedia. The operation is composition of transformations (do one and then the other). This is not an Abelian group: the order of the transformations matters.
- The non-zero remainders modulo a prime , under multiplication (mod ). (The identity is . The existence of inverses is not totally obvious, but is not too hard to prove. Here’s a quick description of a proof. Take a non-zero remainder (mod ), say . Then and are coprime (why?), so Bézout’s theorem says that there are integers and so that . Now is an inverse of (mod ) (why?). There a full proof in this NRICH article.)

This week, I’d like to give you an example of a theorem about groups, and then show how it immediately gives a theorem about a specific example of a group (example 4 in the list above) that is an interesting theorem in its own right. I need to define one more concept before I can state this week’s theorem.

A *subgroup* of the group is a subset of that is also a group. What does that mean? Combining two elements of gives an element of . The operation is automatically associative, but one has to check that contains the identity, and that if is in then so is the inverse of . It turns out that to check whether is a subgroup, it is enough to check that for any and in the element is also in . You might like to think about why that check suffices.

Here are some examples of subgroups of those groups I mentioned earlier.

- integers, addition. The even numbers form a subgroup, but the odd numbers do not (because the set of odd numbers does not contain the identity, ).
- positive rationals, multiplication. The powers of ( for any integer ) form a subgroup. The identity is , and the inverse of is , which is also in the set.
- symmetries of a square, composition of transformations. The rotations (including the identity) form a subgroup.
- non-zero remainders modulo a prime , multiplication (mod ). For example, when , the non-zero remainders are , , , , , . The set is a subgroup (check this for yourself!).

This week’s theorem tells us about the size (the *order*, to use the technical term) of a subgroup of a finite group. (Examples 1 and 2 above are infinite groups, examples 3 and 4 are finite.) It’s called Lagrange‘s theorem, but that doesn’t identify it uniquely (hence the title of this post)!

Theorem (Lagrange)The order of a subgroup of a finite group divides the order of the group.

Let’s check this on the examples above.

3. symmetries of a square, composition of transformations, {rotations}. There are 8 symmetries, so (the order of ) is 8. There are 4 rotations, so . And 4 does indeed divide 8.

4. non-zero remainders (mod 7), multiplication, . We have , and , and 3 does divide 6.

Phew — it works in these two cases! (But that’s hardly a proof…)

Note that Lagrange’s theorem does *not* say that if divides the order of a group then has a subgroup of order . In general, that isn’t true.

So, how does one go about proving Lagrange’s theorem? Here’s one approach.

We have a finite group , and a subgroup of that group, and we want to show that divides .

The plan is to show that we can *partition* the elements of into several subsets, each of size . (The word “partition” indicates that the subsets don’t overlap, but between them they include every element of . So each element of lies in exactly one of the subsets forming the partition.) That will immediately show that divides .

So how can we do that? I think that it seems natural to try to find some way of breaking into subsets that are somehow “copies” of , since a “copy” of will certainly have the same size as . It turns out that one can do exactly that. The “copies” are called *cosets*. The coset consists of elements of the form , with an element of . (Strictly speaking, this is a *left coset*; is not, in general, the same as . But since I’m only using left cosets in this post, I’ll continue to call them cosets.)

We have lots of cosets , one for each element in . But they might overlap, or even be the same. Let’s see what happens with one of our examples from earlier: under multiplication (mod ), and . We have six cosets.

.

It seems that either two cosets are the same, or they are disjoint (they don’t overlap at all). That’s the key. We choose one copy of each coset (so we might choose and , say), and those give the partition we want. Now there is still some checking to do in order to have a proof of the general result. One has to show that it is indeed the case that either two cosets are the same or they are disjoint, and one then has to show that picking one copy of each coset does indeed give a partition of . This is not hard, but this post is getting rather long so I think that I’ll skip it.

I said that I’d show that Lagrange’s theorem gives another interesting theorem as a corollary, so let me tell you about that now. The theorem is called Fermat‘s little theorem. There’s a lot to say about it, so I plan for it to be a future Theorem of the week in its own right. For now, I’ll just introduce it fairly briefly.

In that NRICH article introducing the idea of a group (link at the start of this post), there’s a proof that every element of a finite group has some power that’s equal to the identity. Let’s test that for our favourite group of non-zero remainders (mod 7), under multiplication. I’ll record the first few powers of each element.

, , , , , .

, , , , , .

, , , , , .

, , , , , .

, , , , , .

, , , , , .

There are all sorts of interesting things to notice there, and I encourage you to think about them. For now, the thing I really want you to notice is that the sixth power of each element is . Some elements have a smaller power that is also (e.g. ), some don’t (e.g. ), but they all agree on the sixth powers. Fermat’s little theorem tells us that this is an example of a much more general phenomenon.

**Theorem (Fermat)** Let be a prime, and let be an integer not divisible by . Then (mod ).

This theorem is sometimes stated in a slightly different way: (mod ) for all (not just divisible by ). You might like to think about why the two statements are equivalent (it’s not hard).

How can we prove this using Lagrange’s theorem? Well, we have a group consisting of the non-zero remainders (mod ) under multiplication, and .

We need a subgroup. Our element *generates* a subgroup: we take to be the powers of . (For example, if and , we’d take ; if and , we’d take .)

How big is ? Well, we have , where is the smallest positive number such that (mod ), so .

Now Lagrange’s theorem tells us that divides . That is, it says that divides . Say . Now we can calculate . We have (mod ) — just as we wanted!

Fermat’s little theorem and its generalisation to moduli that aren’t prime, the Fermat-Euler theorem, are, I think, very elegant in their own right. They also have important applications, for example to cryptography (the RSA algorithm depends on them). I’ll say more about this when they are the main topic of a post. I’ll also give some other proofs.

Wikipedia has a page about Lagrange’s theorem. The theorem will be covered in any decent first introduction to group theory. Similarly, Fermat’s little theorem will be in most introductions to number theory. There’s a section about it in this NRICH article.

January 20, 2010 at 8:03 pm

[…] to this week’s theorem. I have previously promised to write about Fermat’s Little Theorem, and I think it’s time to keep that […]

January 27, 2010 at 10:57 pm

[…] Theorem 15: Lagrange’s theorem about sums of four squares By theoremoftheweek I found myself telling someone about this theorem the other day (as a way of introducing the area of my research), and remembered what a remarkable theorem it is. So it seems like a good time to write about it, even if it does mean I’ll have two theorems by Lagrange in quite close succession! […]

March 28, 2010 at 2:10 pm

thanks.

May 20, 2010 at 11:35 pm

[…] written previously about groups, when I wrote about Lagrange’s theorem in group theory. Today I’d like to talk some more about groups, so if you don’t know what one is I […]

July 12, 2010 at 7:55 am

[…] this theorem previously in this blog. I used it to give an example of a group in my post about Lagrange’s theorem in group theory, and mentioned it again in Proof 3 in my post about Fermat’s little theorem. It’s a […]

October 23, 2011 at 4:32 pm

[…] you know about Lagrange’s theorem about finite groups, then you’ll know that the order of an element divides the order of the […]

March 20, 2012 at 7:08 am

Thank you so much..this was great help for me

November 7, 2012 at 6:00 pm

[…] can multiply by scalars. And the addition behaves nicely (officially, the set of vectors forms a group under addition), and the multiplication behaves nicely, and the two operations interact nicely. […]

April 25, 2013 at 7:55 pm

Hey. I just stumbled upon this website by looking for the first isomorphism theorem. I really like the introduction to this article. Ever since they taught us abstract notions such as functions and the rules like: “functions assign only 1 element to an element in its domain”, I wondered why. And nobody ever really explains this part. That was always confusing for me.

Only recently as I have started to study applied math I have started to come to a conclusion myself. It makes me happy to see that this conclusion is confirmed by the introduction you wrote.

October 14, 2013 at 10:15 am

[…] Theorem 8 (Fermat-Euler): Let be a natural number, and let be an integer coprime to . Then . We proved this using Lagrange‘s theorem from group theory. […]

March 13, 2015 at 11:57 am

[…] 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 […]

April 22, 2015 at 1:40 pm

[…] Lagrange’s theorem says that the order of a subgroup divides the order of the group, and a consequence of that is that the order of an element divides the order of the group. I was careful to stress that the converse is not true: if divides the order of the group, there might not be an element of order (although of course there might be). Sometimes, though, the world is a very nice place. Can you show that if a group has even order then it contains an element of order 2? […]

March 10, 2016 at 2:26 pm

[…] 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 […]

April 22, 2016 at 1:22 pm

[…] Lagrange’s theorem says that the order of a subgroup divides the order of the group, and a consequence of that is that the order of an element divides the order of the group. I was careful to stress that the converse is not true: if divides the order of the group, there might not be an element of order (although of course there might be). Sometimes, though, the world is a very nice place. Can you show that if a group has even order then it contains an element of order 2? […]

May 15, 2016 at 12:51 am

“This is not hard, but this post is getting rather long so I think that I’ll skip it.”

This really should be the most important part of your post, but instead you included everything around it.