## 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.