Discrete Mathematics

Lagrange’s Theorem: Lagrange’s Theorem states a very important relation between the orders of a finite group and any subgroup.

Theorem 3.15 (Lagrange’s Theorem) Let H be a subgroup of a finite group G. Then the order of H divides the order of G.
Proof We already know from the last section that the group G is partitioned into the right cosets of H. We show that every right coset Hg contains the same number of elements as H.
To prove this, we construct a bijection f from H to Hg. The bijection is defined in the obvious way: Φ maps h to hg.
• Φ is one-to-one: suppose that Φ(h1) = Φ)h2, that is, h1g = h2g. Cancelling the g (by the cancellation law, or by multiplying by g−1), we get h1 = h2.
• Φ is onto: by definition, every element in the coset Hg has the form hg for some h ∈   H, that is, it is Φ(h).
So f is a bijection, and |Hg| = |H|.
Now, if m is the number of right cosets of H in G, then m|H| = |G|, so |H| divides |G|.

Remark We see that |G|/|H| is the number of right cosets of H in G. This number is called the index of H in G.
We could have used left cosets instead, and we see that |G|/|H| is also the number of left cosets. So these numbers are the same. In fact, there is another reason for this:
Exercise Show that the set of all inverses of the elements in the right coset Hg form the left coset g−1H. So there is a bijection between the set of right cosets and the set of left cosets of H.
In the example in the preceding section, we had a group S3 with a subgroup having three right cosets and three left cosets; that is, a subgroup with index 3.

Corollary 3.16 let g be an element of the finite group G. Then the order of g divides the order of G.
Proof Remember, first, that the word “order” here has two quite different meanings: the order of a group is the number of elements it has; while the order of an element is the smallest n such that gn = 1.
However, we also saw that if the element g has order m, then the set {1,g,g2, . . . ,gm−1} is a cyclic subgroup of G having order m. So, by Lagrange’s Theorem, m divides the order of G.
Example Let G = S3. Then the order of G is 6. The element (1)(2,3) has order 2, while the element (1,3,2) has order 3.