Theorem 10: Lagrange’s theorem in group theory

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 G and a binary operation \bullet that satisfy the group axioms.  So \bullet is a map that takes two elements of G as input, and gives one element of G as output.  There are three group axioms.

  1. The operation \bullet is associative.  That is, a \bullet (b\bullet c) = (a \bullet b) \bullet c for any a, b and c in G.  (So one can write a \bullet b \bullet c without any ambiguity.)
  2. There is an identity element in G.  That is, there is some e in G so that a \bullet e = a = e \bullet a for any a in G.  (“Combining with e has no effect.”)
  3. Each element of G has an inverse in G.  That is, for each a in G there is some element b in G so that a \bullet b = e = b \bullet a.  (The inverse of a is often written as a^{-1} — this should not be confused with the usual reciprocal 1/a!)

Here are some examples of groups.

  1. The integers under addition.  (The identity is 0, and the inverse of n is -n.)
  2. The positive rational numbers under multiplication.  (The identity is 1, and the inverse of a/b is 1/(a/b) = b/a.)
  3. 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.
  4. The non-zero remainders modulo a prime p, under multiplication (mod p).  (The identity is 1.  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 p), say a.  Then a and p are coprime (why?), so Bézout’s theorem says that there are integers h and k so that ah+pk=1.  Now h is an inverse of a (mod p) (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 H of the group G is a subset of G that is also a group.  What does that mean?  Combining two elements of H gives an element of H.  The operation is automatically associative, but one has to check that H contains the identity, and that if a is in H then so is the inverse of a.  It turns out that to check whether H is a subgroup, it is enough to check that for any a and b in H the element a \bullet b^{-1} is also in H.  You might like to think about why that check suffices.

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

  1. G = integers, \bullet = addition.  The even numbers form a subgroup, but the odd numbers do not (because the set of odd numbers does not contain the identity, 0).
  2. G = positive rationals, \bullet = multiplication.  The powers of 3 (3^n for any integer n) form a subgroup.  The identity is 1 = 3^0, and the inverse of 3^n is 3^{-n}, which is also in the set.
  3. G = symmetries of a square, \bullet = composition of transformations.  The rotations (including the identity) form a subgroup.
  4. G = non-zero remainders modulo a prime p, \bullet = multiplication (mod p).  For example, when p=7, the non-zero remainders are 1, 2, 3, 4, 5, 6.  The set \{1, 2, 4\} 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. G = symmetries of a square, \bullet = composition of transformations, H = {rotations}.  There are 8 symmetries, so |G| (the order of G) is 8.  There are 4 rotations, so |H| = 4.  And 4 does indeed divide 8.

4. G = non-zero remainders (mod 7), \bullet = multiplication, H=\{1,2,4\}.  We have |G|=6, and |H|=3, 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 n divides the order of a group G then G has a subgroup of order n.  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 G, and a subgroup H of that group, and we want to show that |H| divides |G|.

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

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

We have lots of cosets aH, one for each element a in G.  But they might overlap, or even be the same.  Let’s see what happens with one of our examples from earlier: G=\{1,2,3,4,5,6\} under multiplication (mod 7), and H=\{1,2,4\}.  We have six cosets.

1H=\{1,2,4\}

2H=\{1,2,4\}

3H=\{3,5,6\}

4H=\{1,2,4\}

5H=\{3,5,6\}

6H=\{3,5,6\}.

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 2H and 5H, 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 G.  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.

1^1=1, 1^2=1, 1^3=1, 1^4=1, 1^5=1, 1^6=1.

2^1=2, 2^2=4, 2^3=1, 2^4=2, 2^5=4, 2^6=1.

3^1=3, 3^2=2, 3^3=6, 3^4=4, 3^5=5, 3^6=1.

4^1=4, 4^2=2, 4^3=1, 4^4=4, 4^5=2, 4^6=1.

5^1=5, 5^2=4, 5^3=6, 5^4=2, 5^5=3, 5^6=1.

6^1=6, 6^2=1, 6^3=6, 6^4=1, 6^5=6, 6^6=1.

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 1.  Some elements have a smaller power that is also 1 (e.g. 2^3=1), some don’t (e.g. 3), 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 p be a prime, and let a be an integer not divisible by p.  Then a^{p-1}\equiv 1 (mod p).

This theorem is sometimes stated in a slightly different way: a^p\equiv a (mod p) for all a (not just a divisible by p).  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 G consisting of the non-zero remainders (mod p) under multiplication, and |G|=p-1

We need a subgroup.  Our element a generates a subgroup: we take H to be the powers of a.  (For example, if p=7 and a=2, we’d take H=\{1,2,4\}; if p=7 and a=3, we’d take H=\{1,2,3,4,5,6\}.)

How big is H?  Well, we have H=\{a,a^2,a^3,\dotsc,a^k\}, where k is the smallest positive number such that a^k\equiv 1 (mod p), so |H|=k.

Now Lagrange’s theorem tells us that |H| divides |G|.  That is, it says that k divides p-1.  Say p-1=km.  Now we can calculate a^{p-1}.  We have a^{p-1}=a^{km}=(a^k)^m\equiv 1^m\equiv 1 (mod p) — 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.

About these ads

10 Responses to “Theorem 10: Lagrange’s theorem in group theory”

  1. Theorem 14: Fermat’s Little Theorem « Theorem of the week Says:

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

  2. Theorem 15: Lagrange’s theorem about sums of four squares « Theorem of the week Says:

    [...] 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! [...]

  3. yen Says:

    thanks.

  4. Theorem 26: the first isomorphism theorem « Theorem of the week Says:

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

  5. Theorem 31: the non-zero integers (mod p) form a group under multiplication « Theorem of the week Says:

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

  6. Theorem 38: There is a primitive root modulo a prime « Theorem of the week Says:

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

  7. Eshitha Says:

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

  8. Theorem 43: the Steinitz Exchange Lemma « Theorem of the week Says:

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

  9. Ka S Per Says:

    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.

  10. Number Theory: Lecture 2 | Theorem of the week Says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 133 other followers

%d bloggers like this: