Today will conclude the proof of Lagrange’s Theorem! Recall that we defined subgroups and left cosets, and defined a certain equivalence relation on a group in terms of a subgroup . Today we’re going to show that the equivalence classes of this equivalence relation are precisely the left cosets of . Since, as we saw yesterday, the equivalence classes of an equivalence relation always partition the entire set, this will mean that the left cosets of a subgroup partition the entire group . (Did you notice this when working out the cosets of in ?) But we also know that all the cosets have the same size (namely, the size of the subgroup). This means that the cosets of carve up precisely into a bunch of equal-size parts—so the size of the parts, that is, the size of , must evenly divide the size of . Otherwise there would either have to be some elements of left over, or some of the parts would have to overlap, but those things can’t happen with a partition.

So, let’s show that the left cosets of are exactly the same as the equivalence classes of the equivalence relation . Recall that by definition, if and only if for some .

Let’s first explicitly note something which was implicit in yesterday’s post: if is an equivalence relation, then if and only if and are in the same equivalence class. To see this, first, if , then both are in the equivalence class (which we know is also equal to ). Conversely, suppose and are in the same equivalence class, say, . Then and , and by symmetry and transitivity, .

What this means is that in order to show equivalence classes of are the same as left cosets of , we can prove the following:

* if and only if and are in the same coset of .*

To prove an “if and only if” we have two directions to prove.

- In the forward direction, suppose , so for some , and thus also . We have to prove that and are in the same coset of , that is, there is some such that . Expanding the definition a bit more, this means we have to find so that and . In fact, and are both in the coset : we can pick and , since and .
- In the backward direction, suppose and are both in the coset , so there are and such that and . Then we have to show , that is, for some . Well, , so the we are looking for is .

So the cosets of all have the same size and partition , which means their common size must evenly divide the size of . Thus we have proved Lagrange’s Theorem: if then divides .

We still haven’t quite proved what we originally set out to prove, namely, that the order of any *element* divides . If you want to try to prove it yourself before tomorrow, here’s a hint: can you take and use it to construct a subgroup of , to which we could apply Lagrange’s Theorem? The full proof—and triumphant conclusion of MaBloWriMo—to come tomorrow!