4.7 Cosets and Lagrange’s Theorem

Definition 4.13 Let $(G, *)$ be a group, H a subgroup of G, and $g \in G$.

The left coset of H by g is $gH := \{ g*h : h \in H\}$.
The right coset of H by g is $Hg := \{ h*g : h \in H\}$.

We write $G:H$ for the set of left cosets of H by elements of G so $G:H = \{ gH : g \in G\}$, and $|G:H|$ for its size. Similarly $H:G$ is the set of right cosets of H by elements of G.

Let’s look at some example cosets.

Example 4.8

The 3-cycle $(1,2,3) \in S_4$ has order 3, so $H=\langle (1,2,3) \rangle$ is equal to $\{ e, (1,2,3), (1,2,3)^2 = (1,3,2)\}$. Then \[\begin{align*} (1,2)H &= \{ (1,2), (1,2)(1,2,3), (1,2)(1,3,2) \} \\ &= \{ (1,2), (2,3), (1,3) \} \\ H(1,2) &= \{ (1,2), (1,2,3)(1,2), (1,3,2)(1,2) \} \\ &= \{ (1,2), (1,3), (2,3) \}. \end{align*}\] So in this case, $(1,2)H = H(1,2)$.
The 2-cycle $(1,2) \in S_3$ has order 2, so $H := \langle (1,2) \rangle$ is equal to $\{ e, (1,2) \}$. Then \[\begin{align*} (2,3)H &= \{ (2,3), (2,3)(1,2)\} = \{ (2,3),(1,3,2)\} \\ H(2,3)&= \{ (2,3), (1,2)(2,3) \} = \{ (2,3), (1,2,3) \} \end{align*}\] So in this case $(2,3)H \neq H(2,3)$.
We know that $2\ZZ = \{ 2 z : z \in \ZZ\}$, the set of all even integers, is a subgroup of $(\ZZ,+)$. Then the coset $1+2\ZZ = \{ 1+ 2z : z \in \ZZ\}$ is the set of all odd integers. More generally if $n \in \ZZ$ then $n\ZZ$ is a subgroup of $\ZZ,+$ and $1 + n\ZZ$ is the set of all integers congruent to 1 mod n, $2+n\ZZ$ is the set of all integers congruent to 2 mod n, and so on.

Consider the cosets $0+3\ZZ=3\ZZ, 1+3\ZZ, 2+3\ZZ$ of the subgroup $3\ZZ$ of $(\ZZ,+)$. Each element of $\ZZ$ belongs to exactly one of them, for any integer is congruent to exactly one of 0, 1, or 2 mod 3. So we have \[\begin{equation*} \ZZ = 3\ZZ \sqcup (1+3\ZZ) \sqcup (2+3\ZZ) \end{equation*}\] (the symbol $\sqcup$ means that this is a disjoint union). Furthermore, $3n \mapsto i+3n$ is a bijection between $3\ZZ$ and $i+3\ZZ$, so all three cosets have the same size. So the cosets of the subgroup $3\ZZ$ split $\ZZ$ into three disjoint pieces, each of the same size. If $\ZZ$ were a finite set this would imply that its size was three times that of the subgroup $3\ZZ$. When we prove Lagrange’s theorem, which says that if G is finite and H is a subgroup then the order of H divides that of G, our strategy will be to prove that you get exactly this kind of decomposition of G into a disjoint union of cosets of H.

Example 4.9 The 3-cycle $(1,2,3) \in S_3$ has order 3, so $H= \langle (1,2,3) \rangle$ is equal to $\{ e, (1,2,3), (1,3,2) \}$. Then \[\begin{align*} (1,2)H& = \{(1,2), (1,2)(1,2,3), (1,2)(1,3,2) \} \\ &= \{ (1,2), (2,3), (1,3) \} \\ (2,3)H &= \{ (2,3), (2,3)(1,2,3), (2,3)(1,3,2) \} \\ &= \{ (2,3), (1,3), (1,2) \} \end{align*}\] So $(1,2)H = (2,3)H$.

This last example is important, because it tells us we can have $g_1H = g_2 H$ even if $g_1 \neq g_2$. The next result tells us exactly when this happens.

From now on I’ll be lazy and write $gh$ instead of $g*h$.

Lemma 4.8 (the coset equality lemma) Let G be a group and H a subgroup of G. Then $gH=kH$ if and only if $g^{-1}k \in H$, and $Hg = Hk$ if and only if $kg^{-1} \in H$.

Proof. We prove only the statement about left cosets, the proof for right cosets being analogous.

If $gH=kH$ then $k \in gH$, so $k = gh$ for some $h\in H$, so multiplying on the left by the inverse of g we get $g^{-1}k \in H$.

If $g^{-1}k =h \in H$ then $k = gh$. Every element of $kH$ is equal to $kh'$ for some $h' \in H$, and $kh' = ghh' = g(hh') \in gH$ as $H$ is a subgroup so $hh' \in H$. This shows $kH \subseteq gH$. Since $g=kh^{-1}$ and $h^{-1} \in H$ as $H$ is a subgroup, a similar argument shows $gH \subseteq kH$ so $gH=kH$.

Corollary 4.1 If $gH\cap kH \neq \emptyset$ then $gH = kH$

Proof. Let $x \in gH \cap kH$. Then $x=gh_1 = kh_2$ for some $h_1, h_2 \in H$. Rearranging gives $g^{-1}k = h_1h_2^{-1}$ which is an element of H because H is a subgroup. By the coset equality lemma, $gH=kH$.

Of course, there’s a version of this for right cosets as well: $

Each coset of a subgroup H has the same size as H.

Lemma 4.9 $|gH| = |H| = |Hg|$.

Proof. We will prove the first of these equalities, the second being similar. The proof is by writing down a bijection between H and $gH$. Define $\alpha : H \to gH$ by $\alpha(h) = g*h$.

$\alpha$ is one-to-one: for if $\alpha(h_1)=\alpha(h_2)$ then $g*h_1=g*h_2$, so multiplying on the left by $g^{-1}$ we get that $h_1=h_2$.

$\alpha$ is onto: for any element of $gH$ equals $g*h$ for some $h \in H$, and $\alpha(h)=g*h$, so $g*h$ is in the image of $\alpha$.

Thus $\alpha$ is a bijection, and $|gH| = |H|$.

Theorem 4.2 (Lagrange’s Theorem) Let G be a finite group and let H be a subgroup. Then $|G| = |G:H||H| = |H:G||H|$.

In particular, Lagrange’s theorem tells you that the order of a subgroup of a finite group divides the order of the group. A group of order 4 cannot possibly have a subgroup of order 3.

Proof. Let the distinct left cosets of H in G be $g_1H,\ldots,g_mH$, so $m=|G:H|$. We will show that every element of G belongs to exactly one of these cosets. For any $g\in G$ we have $g \in gH$, so every element of $G$ belongs to at least one of these cosets. Corollary 4.1 shows that the cosets $g_1H, \ldots, g_mH$ don’t have any elements in common, so

\[|G| = |g_1H|+\cdots + |g_mH|.\] Since $|g_iH|=|H|$ by Lemma 4.9 we get $|G|=m|H|= |G:H||H|$ as required. The result for right cosets can be proved similarly.

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

Proof. The order of g equals the order of the cyclic subgroup $\langle g \rangle \leq G$ by Lemma 4.7. This divides $|G|$ by Lagrange’s theorem.

Corollary 4.3 Let G be a group whose order is a prime number p. Then G is cyclic.

Proof. Let $e \neq g \in G$. Consider the subgroup $\langle g \rangle \leq G$. Its size divides $|G|=p$ by Lagrange’s theorem, so it is 1 or p, but it is larger than one as it contains e and g so $|\langle g \rangle|=p$. So $\langle g \rangle = G$ and G is cyclic.

Corollary 4.4 (Fermat’s Little Theorem). Let $a \in \ZZ$ and let p be a prime number. Then $a^p \equiv a \mod p$.

Proof. If a is divisible by p this is easy, so let’s suppose a is not divisible by p. Since $\ZZ_p^\times, \times$ is a group of order $p-1$, the order of $[a]_p$ divides $p-1$ so $[a]_p^{p-1}=[1]_p$, that is, $[a^{p-1}]_p=[1]_p$. Therefore $a^{p-1} \equiv 1 \mod p$, and so $a^p \equiv a \mod p$.