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