Lagrange Theorem

In this post, we will build up towards proving Lagrange's Theorem, which can be viewed as an extension of Euler's Theorem.

Let $G$ be a group with operation $*$ and consider an arbitrary subset $H \subseteq G$. In general, $H$ is not a group under $*$. In fact, $*$ may not even be a well-defined function on $H \times H \rightarrow H$, since its image may lie outside $H$. Hence, we make the following definition.

A subgroup of $G$ is a subset $H \subseteq G$ such that:
(a) $e \in H$,
(b) $h \in H \Rightarrow h^{-1} \in H$,
(c) $h, h' \in H \Rightarrow hh' \in H$.

Note that any such $H$ becomes a group in its own right, with the operation $*$ "inherited" from $G.$

For any group $G,$ $G$ itself and $\{e\}$ are subgroups of $G.$ Most groups have other, non-trivial subgroups. The following are some examples of subgroups, that correspond to the example list of groups from the post Group Theory.

1) $\mathbb{Z}$, the set of integers
2) $\mathbb{R}^+$, the set of positive real numbers.
3) $S_{n-1}$, the set of functions which also satisfy $f(n) = n$.
4) $m \mathbb{Z}_n$, the subset of multiples of $m$. Note that this is strictly smaller than $\mathbb{Z}_n$ if $\gcd(m,n)\neq 1 .$
5) $(\mathbb{Z}_n ^\times )^2$, the set of squares modulo $n$.

A general example of a subgroup is obtained by picking an element $g \in G$ and taking all powers of $g$. This is known as the subgroup generated by $g$, and is denoted by:

$< g > := \{ \ldots, g^{-2}, g^{-1}, e, g, g^2, \ldots \}.$

Proposition. The order of the subgroup $< g >$ is the smallest positive $m$ for which $g^m = e$. If such an $m$ does not exist, then the order is infinite.

As such, we define the order of element $g$ to be the smallest positive $m$ for which $g^m = e$, and write $o(g) = m$.

Let $H$ be a subgroup of the group $G$, and let $g \in G$. The set $g H = \{ gh : h \in H \}$ is called a (left) coset of $H$ in $G.$ . In other words, the coset $gH$ is the image (range) of the function $\phi_g : H \rightarrow G$ where $\phi_g (h) = gh$. Because this function is one-to-one (by the Cancellation Property!) $\lvert gH \rvert = \lvert H \rvert.$ Note also that $g=ge\in gH.$

The most important property of the cosets is that $g_1H$ and $g_2H$ either coincide or do not intersect (see Worked Example 2 below). This implies the following classical theorem.

Lagrange's Theorem. If $G$ is a finite group and $H$ is a subgroup of $G$, then $\lvert H \rvert$ divides $\lvert G \rvert$.

As an immediate corollary, we get that if $G$ is a finite group and $g\in G$, then $o(g)$ divides $G$. In particular, $g^{ \lvert G \rvert} = e$ for all $g \in G$.

Worked Examples

1. Prove the proposition.

Solution: Suppose $m$ is finite. We claim that $< g > = \{e, g, g^2, \ldots, g^{m-1} \}$ and that all these $m$ elements are distinct. For the first statement, note that for any $n \in \mathbb{Z}$, we can write $n = qm+r$ where $0 \leq r \leq m-1$. Hence $g^n = (g^m)^q(g^r) = e(g^r) = g^r$. To prove the second statement, suppose $g^i = g^j$ for $0 \leq i \leq j \leq m-1$, then $g^{j-i} = e$, which contradicts the minimality of $m$.

2. Let $g, g' \in G$ and $H \subseteq G$ be a subgroup.

(a) If $g^{-1} g' \in H$, then $gH = g'H$;

(b) If $g^{-1} g' \not \in H$, then $gH \cap g'H = \emptyset$.

Solution: For the first statement, any element of $g'H$ can be written as $g'h$, for some $h\in H$. But $g' h = g(g^{-1} g') h \in gH$ since $g^{-1} g' \in H$. This tells us that $g'H \subseteq gH$.
Conversely, any element of $gH$ can be written as $gh, h \in H$ and $gh = g'(g'^{-1}g)h$. But $g'^{-1}g = (g^{-1}g')^{-1}$ lies in $H$ since $H$ is a subgroup of $G$. Hence the result follows and $gH = g′H$.
For the second statement, suppose $x \in gH \cap g'H$. Then it can be written as $x = gh = g'h'$ for some $h, h' \in H$. Thus $g^{-1}g' = hh'^{-1} \in H$ which contradicts the fact that $g^{-1}g' \not \in H$.

3. Prove Lagrange's Theorem

Solution: The above shows that the cosets partition the entire group $G$ into mutually disjoint subsets, all of which have $\lvert H \rvert$ elements. Hence, Lagrange's Theorem follows.