[summary: Lagrange's Theorem gives us a restriction on the size of a subgroup of a finite group: namely, subgroups have size dividing the parent group.]

Given a finite Group $~$G$~$, it may have many subgroups. So far, we know almost nothing about those subgroups; it would be great if we had some way of restricting them.

An example of such a restriction, which we do already know, is that a subgroup $~$H$~$ of $~$G$~$ has to have size less than or equal to the size of $~$G$~$ itself. This is because $~$H$~$ is contained in $~$G$~$, and if the set $~$X$~$ is contained in the set $~$Y$~$ then the size of $~$X$~$ is less than or equal to the size of $~$Y$~$. (This would have to be true for any reasonable definition of "size"; the usual definition certainly has this property.)

Lagrange's Theorem gives us a much more powerful restriction: not only is the size $~$|H|$~$ of $~$H$~$ less than or equal to $~$|G|$~$, but in fact $~$|H|$~$ divides $~$|G|$~$.

%%hidden(Example: subgroups of the cyclic group on six elements): A priori, all we know about the subgroups of the Cyclic group $~$C_6$~$ of order $~$6$~$ is that they are of order $~$1, 2, 3, 4, 5$~$ or $~$6$~$.

Lagrange's Theorem tells us that they can only be of order $~$1, 2, 3$~$ or $~$6$~$: there are no subgroups of order $~$4$~$ or $~$5$~$. Lagrange tells us nothing about whether there are subgroups of size $~$1,2,3$~$ or $~$6$~$: only that if we are given a subgroup, then it is of one of those sizes.

In fact, as an aside, there are indeed subgroups of sizes $~$1,2,3,6$~$:

• the subgroup containing only the identity is of order $~$1$~$
• the "improper" subgroup $~$C_6$~$ is of order $~$6$~$
• subgroups of size $~$2$~$ and $~$3$~$ are guaranteed by Cauchy's theorem.

%%

Proof

In order to show that $~$|H|$~$ divides $~$|G|$~$, we would be done if we could divide the elements of $~$G$~$ up into separate buckets of size $~$|H|$~$.

There is a fairly obvious place to start: we already have one bucket of size $~$|H|$~$, namely $~$H$~$ itself (which consists of some elements of $~$G$~$). Can we perhaps use this to create more buckets of size $~$|H|$~$?

For motivation: if we think of $~$H$~$ as being a collection of symmetries (which we can do, by Cayley's Theorem which states that all groups may be viewed as collections of symmetries), then we can create more symmetries by "tacking on elements of $~$G$~$".

Formally, let $~$g$~$ be an element of $~$G$~$, and consider $~$gH = \{ g h : h \in H \}$~$.

Exercise: every element of $~$G$~$ does have one of these buckets $~$gH$~$ in which it lies. %%hidden(Show solution): The element $~$g$~$ of $~$G$~$ is contained in the bucket $~$gH$~$, because the identity $~$e$~$ is contained in $~$H$~$ and so $~$ge$~$ is in $~$gH$~$; but $~$ge = g$~$. %%

Exercise: $~$gH$~$ is a set of size $~$|H|$~$. %%note:More formally put, Left cosets are all in bijection.%% %%hidden(Show solution): In order to show that $~$gH$~$ has size $~$|H|$~$, it is enough to match up the elements of $~$gH$~$ bijectively with the elements of $~$|H|$~$.

We can do this with the Function $~$H \to gH$~$ taking $~$h \in H$~$ and producing $~$gh$~$. This has an inverse: the function $~$gH \to H$~$ which is given by pre-multiplying by $~$g^{-1}$~$, so that $~$gx \mapsto g^{-1} g x = x$~$. %%

Now, are all these buckets separate? Do any of them overlap?

Exercise: if $~$x \in rH$~$ and $~$x \in sH$~$ then $~$rH = sH$~$. That is, if any two buckets intersect then they are the same bucket. %%note:More formally put, Left cosets partition the parent group.%% %%hidden(Show solution): Suppose $~$x \in rH$~$ and $~$x \in sH$~$.

Then $~$x = r h_1$~$ and $~$x = s h_2$~$, some $~$h_1, h_2 \in H$~$.

That is, $~$r h_1 = s h_2$~$, so $~$s^{-1} r h_1 = h_2$~$. So $~$s^{-1} r = h_2 h_1^{-1}$~$, so $~$s^{-1} r$~$ is in $~$H$~$ by closure of $~$H$~$.

By taking inverses, $~$r^{-1} s$~$ is in $~$H$~$.

But that means $~$\{ s h : h \in H \}$~$ and $~$\{ r h : h \in H\}$~$ are equal. Indeed, we show that each is contained in the other.

• if $~$a$~$ is in the right-hand side, then $~$a = rh$~$ for some $~$h$~$. Then $~$s^{-1} a = s^{-1} r h$~$; but $~$s^{-1} r$~$ is in $~$H$~$, so $~$s^{-1} r h$~$ is in $~$H$~$, and so $~$s^{-1} a$~$ is in $~$H$~$. Therefore $~$a \in s H$~$, so $~$a$~$ is in the left-hand side.
• if $~$a$~$ is in the left-hand side, then $~$a = sh$~$ for some $~$h$~$. Then $~$r^{-1} a = r^{-1} s h$~$; but $~$r^{-1} s$~$ is in $~$H$~$, so $~$r^{-1} s h$~$ is in $~$H$~$, and so $~$r^{-1} a$~$ is in $~$H$~$. Therefore $~$a \in rH$~$, so $~$a$~$ is in the right-hand side. %%

We have shown that the "cosets" $~$gH$~$ are all completely disjoint and are all the same size, and that every element lies in a bucket; this completes the proof.