Cosets and Lagrange's Theorem

Again let $G$ be an arbitrary group and let $H\subset G$. We shall now introduce another equivalence relation on $G$. Namely, define for $a,b \in G$

$$a\sim b\ \ \ {\rm if \ and\ only\ if}\ \ \ a^{-1}b\in H.$$ (4.5)

Let us show, first of all, that this is indeed an equivalence relation.

(1)

(Reflexivity) $a \sim a$ since $a^{- 1}a = e \in H$.

(2)

(Symmetry) $a \sim b$ implies $a^{- 1}b \in H$, but since $H\subset G$, so $b^{- 1}a = (a^{- 1}b)^{- 1}\in H$ and $b \sim a$.

(3)

(Transitivity) If $a \sim b$ and $b \sim c$ then $a^{- 1}b \in H$ and $b^{- 1} c \in H$, so $a^{- 1}b \cdot b^{- 1}c = a^{- 1}c \in H$, and $a \sim c$.

Therefore we do have an equivalence relation on $G$.

Let us investigate what the equivalence classes, $[a]$, for $a \in G$, look like for this equivalence relation. We have $a \sim b$ if and only if $a^{- 1}b \in H$, i.e., if and only if $b\in aH$. Thus $[a] = aH$. These classes, $aH$, are called left cosets of $H$ (recall from the previous section $aH = \{ah\ \vert\ h\in H\}$). We know from properties of equivalence relations (Theorem 1.1.4) that either $aH = bH$ or $aH\cap bH = \emptyset$. Moreover,

$$G=\coprod aH,$$ (4.6)

where, as usual, the (disjoint) union is taken over certain $a \in G$.

We also note that $aH = bH$ if and only if $a \sim b$, i.e., if and only if $a^{- 1}b \in H$, i.e., $b = ah$, for some $h\in H$. In particular, $bH = H = eH$ if and only if $b\in H$.

One could define another equivalence relation by defining $a \sim b$ if and only if $ba^{- 1}\in H$. Again this can be shown to be an equivalence relation on $G$, and the equivalence classes here are sets of the form $Ha$, called right cosets of $H$. Also, of course, one can write $G = \coprod Ha$, where, as above, the (disjoint) union is taken over certain $a \in G$.

It is easy to see that any two left (right) cosets have the same order (number of elements). To demonstrate this consider the mapping $aH \rightarrow bH$ via $ah \longmapsto bh$ where $h\in H$. It is not hard to show that this mapping is 1-1 and onto (see exercise 1 for this section). Thus we have $aH = bH$. (This is also true for right cosets and can be established in a similar manner.) Letting $b\in H$ in the above discussion, we see $\vert aH\vert = \vert H\vert$, for any $a \in G$.

One can also see that the collection $\{aH\}$ of all distinct left cosets has the same number of elements as the collection $\{Ha\}$ of all distinct right cosets. In other words, the number of left cosets equals the number of right cosets (this number may be infinite). For consider the map

$$f:aH\rightarrow Ha^{-1}.$$ (4.7)

This mapping is well-defined: for if $aH = bH$, then $b = ah$ where $h\in H$. Thus $f (bH) = Hb^{- 1} = Hh^{- 1}a^{- 1} = f(aH)$. We did not choose the more suggestive ``mapping'' $aH \rightarrow Ha$, which need not be well-defined. The reader should find an example where $aH \rightarrow Ha$ is not well-defined. (Hint: Think of $H = \{1, (1,2)\}$ in $G = S_3$.) It is not hard to show that the mapping in (4.7) is 1-1 and onto (see exercise 2 for this section). Hence the number of left cosets equals the number of right cosets; this number is called the index of $H$ in $G$, denoted by $[G: H]$.

From the decomposition (4.6), in the special case where G is finite, we have

$$\vert G\vert=[G:H]\vert H\vert,$$ (4.8)

or

$$[G:H]=\frac{\vert G\vert}{\vert H\vert}.$$ (4.9)

This establishes the following extremely important theorem in the theory of finite groups.

Theorem 4.3.1 (Lagrange's Theorem)   The order of a subgroup of a finite group is a divisor of the order of the group.

As an immediate corollary, we have the following result.

Corollary 4.3.2   If $\vert G\vert = n$, then $a^n =e$ for all $a \in G$.

Proof: Let $a \in G$ and $o(a) = m$. Then $H = \{e, a, ..., a^{m- 1}\}$ is a subgroup of $G$. Moreover $m = \vert H\vert$. So $m\vert n$, i.e., $n = mk$ for $k \in\mathbb{Z}$. Hence, $a^n = a^{mk} = e$. $\Box$

In the course of proving Corollary 4.3.2, we have shown the following result.

Corollary 4.3.3   The order of any element of a finite group is a divisor of the order of the group.

Let us now return to the relation of conjugacy (see (4.1)) introduced in the previous section. We first wish to get some information on the number of elements in a conjugacy class.

Theorem 4.3.4   Let $a$ be an element of the finite group $G$. Then $Cl(a) = [G: C_G(a)]$.

Proof: Let $G=\coprod_{\alpha\in\Lambda}g_\alpha C_G(a)$, where $\Lambda$ is an indexing set such that $\vert\Lambda\vert = [G: C_G(a)]$. If we can show that any 2 elements of $g_\alpha C_G(a)$ yield the same conjugate of $a$ while elements from different left cosets, $g_\beta C_G(a)$, yield different conjugates of $a$ then we will be done. This is because the number of distinct conjugates of $a$ will then be equal to the number of distinct left cosets of $C_G(a)$ in $G$, that number being $[G: C_G(a)]$. Thus consider $g_\alpha x$ and $g_\alpha y$, where $x, y \in C_G(a)$, then

$$g_\alpha x a x^{-1}g_\alpha^{-1} = g_\alpha a g_\alpha^{-1},$$

and

$$g_\alpha y a y^{-1}g_\alpha^{-1} = g_\alpha a g_\alpha^{-1}.$$

(WHY?) However if $\alpha,\beta\in \Lambda$ with $\alpha\not= \beta$ and if

$$g_\alpha a g_\alpha^{-1} = g_\beta a g_\beta^{-1},$$

then $g_\beta^{-1}g_\alpha a g_\alpha^{-1}g_\beta (g_\beta^{-1}g_\alpha)a(g_\beta^{-1}g_\alpha)^{-1}=a$, which means that $g_\beta^{-1}g_\alpha\in C_G(a)$. In other words, $g_\alpha \in G_\beta C_G(a)$, which implies that $g_\alpha C_G(a) = g_\beta C_G(a)$. This is a contradiction because the decomposition was assumed to be a disjoint one. $\Box$

Since the number of elements conjugate to $a$ in a finite group $G$ is $[G: C_G(a)]$, that number is a divisor of $G$. With this information at our disposal, we can prove the important fact that any prime power group (i.e., a group of order $p^m$, where $p$ is a prime) has a non-trivial center.

Theorem 4.3.5   Let $\vert G\vert = p^m$, $p$ a positive prime and $G$ a group; then $Z(G)$ is non-trivial.

Proof: We first decompose $G$ via (4.2): $G = Z(G) \cup Cl(a) \cup Cl(b)\cup ... \cup Cl(h)$ (disjoint), where $Cl(a)$, $Cl(b)$, ..., $Cl(h)$ are called nontrivial conjugacy classes because in each case their order is $>1$. Moreover, each of their orders divides $G$ from Theorem 4.3.4. However since $\vert G\vert = p^m$, it is clear then that $p\vert \vert Cl(a)\vert$, $p \vert \vert Cl(b)\vert$, ..., $p\vert \vert Cl(h)\vert$. However from the disjoint decomposition it follows that

$$\vert G\vert = \vert Z(G)\vert+ \vert Cl(a)\vert + \vert Cl(b)\vert + ... + \vert Cl(h)\vert,$$ (4.10)

and we see that $p$ must divide $\vert Z(G)\vert$ which completes the proof. $\Box$

We remark that equation (4.10) is itself an important result which holds in any finite group. It is called the class equation. The class equation says that the order of the group is the order of the center added to the sum of the orders of the non-trivial conjugacy classes.

We next consider a rather useful theorem. Denote again by $\vert S\vert$ , the number of elements in the complex $S$ of the group $G$.

Theorem 4.3.6   If $H_1\leq G$, $H_2 \leq G$, $G$ a finite group, then

$$\vert H_1H_2\vert = \frac{\vert H_1\vert\cdot \vert H_2\vert}{\vert H_1\cap H_2\vert}.$$

Proof: Let $H = H_1 \cap H_2$. Then $H \leq G$ since $H_1$ and $H_2$ are subgroups. Moreover, $H \leq H_2$ and so we can decompose $H_2$ into right cosets relative to $H$. In other words,

$$H_2 = Ha_1 \cup H a_2 \cup ... \cup Ha_n\ \ \ \ {\rm (disjoint)},$$

where $n = [H_2: H] = \vert H_2\vert / \vert H\vert$ . Now from this decomposition, we see that

$$H_1H_2 = H_1Ha_1 \cup H_1H a_2 \cup ... \cup H_1Ha_n .$$

Since $H \leq H_1$, $H_1H = H_1$,

$$H_1H_2 = Ha_1 \cup H a_2 \cup ... \cup Ha_n .$$ (4.11)

Moreover, we contend that this union is disjoint. For suppose $H_1a_i \cap H_1a_j\not= \emptyset$, where $i \not= j$. Then there exist elements $b, c \in H_1$ such that $ba_i = ca_j$ or $c^{-1}b = a_ja_i^{-1}$. But $c^{-1} b \in H_1$ and also $a_ja_i^{-1} \in H_2$. Thus $c^{-1}b = a_ja_i^{-1} \in H_1\cap H_2 = H$ and so $Ha_j = Ha_i$. This implies that the decomposition for $H_2$ given above is not disjoint, a contradiction. Thus the union in (4.11) is disjoint and we have then

$$\vert H_1H_2\vert = n\vert H_1\vert=\frac{\vert H_1\vert\cdot \vert H_2\vert}{\vert H\vert}.$$

$\Box$

We end this section with an application of Lagrange's theorem, in particular of the first corollary of this theorem, to number theory.

Consider ${\cal R} (m)$, the residue classes prime to $m$ which was first discussed at the end of section 1.2. ${\cal R} (m)$ is a group with respect to the binary operation

$$[a][b]=[ab],$$ (4.12)

where $[a], [b] \in {\cal R} (m)$. First of all this operation is well-defined, for if $[a] = [c]$ and $[b] = [d]$, then

$$a \equiv c \ ({\rm mod}\ m) \ \ \ {\rm and}\ \ \ b \equiv d \ ({\rm mod}\ m).$$

Hence $ab \equiv cd \ ({\rm mod}\ m)$, using Theorem 1.2.12, i.e., $[ab] = [cd]$. Also $[ab] \in {\cal R} (m)$, for if $gcd (a,m) = 1$ and $gcd(b,m)= 1$, then it follows, by the corollary to Theorem 1.2.8 that $gcd(ab, m) = 1$.

It is now a simple matter to check that the group axioms are satisfied. We shall do so this just for one of the axioms, viz, the existence of inverses. (See exercise 3 of this section for verification of the other group axioms.) Indeed, let $[a] \in {\cal R} (m)$, therefore $gcd (a,m) = 1$. By Theorem 1.2.3 there exist $x, y \in \mathbb{Z}$ such that

$$1 = ax+my \ \ \ \ {\rm or}\ \ \ [1]=[a][x]+[m][y],$$ (4.13)

where we define $[a + b] = [a] + [b]$, a well-defined operation also by Theorem 1.2.12. (However, this addition is not necessarily a mapping into ${\cal R} (m)$ - actually this is a binary operation on the set of all equivalence classes. See exercise 4 for this section.)

But $[m] = [0]$. Therefore (4.13) gives that $[1] = [a][x]$. To be done, we must show $[x] \in {\cal R} (m)$, i.e., $gcd(x,m) = 1$. Suppose $c\vert x$ and $c\vert m$, then by (4.13) $c\vert 1$, so $gcd(x,m) = 1$, and $[x] \in {\cal R} (m)$. Hence, ${\cal R} (m)$ is a group and $\vert{\cal R} (m)\vert = \phi(m)$. Thus by Corollary 1 to Lagrange's Theorem,

$$[a]^{\phi(m)} =[1],$$

which implies the following result.

Theorem 4.3.7 (Euler's theorem)   : If $gcd (a,m) = 1$, then $a^{\phi(m)}\equiv 1$ (mod $m$).

In the special case where $m = p$, a prime, $\phi(m) = \phi(p) = p - 1$, and we get Fermat's Little Theorem.

Corollary 4.3.8 (Fermat)   If $p$ is a positive prime such that $p\not\vert a$, then $a^{p- 1}\equiv 1$ (mod $p$)..