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