# Lagrange's Theorem

Lemma: Let $$H$$ be a subgroup of $$G$$. Let $$r, s \in G$$. Then $$H r = H s$$ if and only if $$r s^{-1}\in H$$. Otherwise $$H r, H s$$ have no element in common. Similarly, $$r H = s H$$ if and only if $$s^{-1} r \in H$$, otherwise $$r H, s H$$ have no element in common.

Proof: If $$r s^{-1} = h \in H$$, then $$H = H h = (H r) s^{-1}$$. Multiplying both sides on the right by $$s$$ gives $$H r = H s$$. Conversely, if $$H r = H s$$, then since $$r \in H r$$ (because $$1 \in H$$) we have $$r = h' s$$ for some $$h' \in H$$. Multiplying on the right by $$s^{-1}$$ shows that $$r s^{-1}\in H$$.

Now suppose $$H r, H s$$ have some element in common, that is $$h_1 r = h_2 s$$ for some $$h_1,h_2 \in H$$. This implies $$r s^{-1} = h_1^{-1} h_2 \in H$$, thus $$H r = H s$$ by above.

Lagrange’s Theorem: If $$H$$ is a subgroup of $$G$$, then $$|G| = n|H|$$ for some positive integer $$n$$. This is called the index of $$H$$ in $$G$$. Furthermore, there exist $$g_1,...,g_n$$ such that $$G = H r_1 \cup ... \cup H r_n$$ and similarly with the left-hand cosets relative to $$H$$.

Proof: Take any $$r_1 \in G$$. Note $$|H r_1 | = |H|$$. If $$H r_1 \ne G$$ then take any $$r_2 \in G \setminus H r_1$$. By the lemma, $$H r_1, H r_2$$ are disjoint so we have $$|H r_1 \cup H r_2| = 2|H|$$. By continuing in this fashion, after $$n$$ steps for some positive integer $$n$$, we will eventually have accounted for all of the elements of $$G$$. We will have $$|G| = n|H|$$ and $$G = H r_1 \cup ... \cup H r_n$$.

Corollary: Let $$G$$ be a group and $$g \in G$$. Then the order of $$g$$ divides $$|G|$$.

Corollary: Let $$G$$ be a group of prime order. Then $$G$$ has no subgroups and hence is cyclic.

Ben Lynn blynn@cs.stanford.edu 💡