# Group Theory 6: Lagrange’s Theorem

In this lecture, we study Lagrange’s Theorem which is named after the Italian/French mathematician, physicists and astronomer Joseph-Louis Lagrange. It states that the order of a subgroup $H$ of a finite group $G$ divides the order of $G$. Lagrange’s Theorem has many important applications in group theory. Before we discuss the theorem we first need to study an important class of binary relations called equivalence relations.

Definition. A binary relation $R$ on a nonempty set $S$ is a subset $R\subset S\times S$. If $(a,b)\in R$, we say $a$ is $R$-related to $b$ and write $aRb$. A binary relation $R$ on a set $S$ is called an equivalence relation on $S$ if it satisfies:

1. $aRa$ $\forall a\in S$. ($R$ is reflexive.)

2. $\forall a,b,\in S$, $aRb\Longrightarrow bRa$. ($R$ is symmetric.)

3. $\forall a,b,c\in S$, $aRb$ and $bRc$ $\Longrightarrow$ $aRc$. ($R$ is transitive.)

Examples. 1. Define a binary relation $\equiv\mod n$ on $\mathbb{Z}$, the set of integers by
$$\forall a,b\in\mathbb{Z},\ a\equiv b\mod n\ \mbox{if}\ n|(a-b).$$ Then $\equiv\mod n$ is an equivalence relation in $\mathbb{Z}$, called the congruence relation modulo $n$. If $a\equiv b\mod n$, we say $a$ is congruent to $b$ modulo $n$. Note that $n|(a-b)$ if and only if $a-b=nk$ for some $k\in\mathbb{Z}$ if and only if $a$ and $b$ have the same remainder when they are divided by $n$ if and only if $a-b\in n\mathbb{Z}$ where
$$n\mathbb{Z}=\{nk: k\in\mathbb{Z}\},$$ the set of all integer multiples of $n$. $\forall n\in\mathbb{Z}$, $n\mathbb{Z}$ is a subgroup of the additive group $(\mathbb{Z},+)$.

2. Let $G$ be a group and $H\leq G$. Define a binary relation $R$ on $G$ by
$$\forall a,b\in G,\ aRb\ \mbox{if}\ ab^{-1}\in H.$$ Then $R$ is an equivalence relation on $G$.

Definition. If $R$ is an equivalence relation on a set $S$, then $[a]$, the equivalence class of $a\in S$, is defined by
$$[a]=\{b\in S: bRa\}.$$

Theorem. Let $R$ be an equivalence relation on a set $S$. Then

1. $S=\bigcup_{a\in S}[a]$.

2. $\forall a,b\in S$, either $[a]=[b]$ or $[a]\cap [b]=\emptyset$.

This means that an equivalence relation $R$ on a set $S$ partitions $S$ into equivalence classes. The set of all equivalence classes $\{[a]: a\in S\}$ is denoted by $S/R$ and is called the quotient set of $S$ modulo $R$.

The converse of the above theorem is also true, namely

Theorem. Let $\wp=\{A_i:i\in I\}$ be a partition of a set $S$ i.e. $S=\bigcup_{i\in I}A_i$ and $\forall i\ne j\in I$, $A_i\cap A_j=\emptyset$. Define a binary relation $R$ on $S$ by
$$\forall a,b\in S,\ aRb\ \mbox{if}\ a,b\in A_i\ \mbox{for some}\ i\in I.$$ Then $R$ is an equivalence relation on $S$, called the equivalence relation induced by the partition $\wp$.

Example. Let $f: X\longrightarrow Y$ be a surjective map. Then $\{f^{-1}(y): y\in Y\}$ forms a partition of $X$. The equivalence relation induced by this partition is
$$\ker f=\{(a,b)\in X\times X: f(a)=f(b)\}.$$ This equivalence relation is called the kernel of the function $f$.

Let $G$ be a group and $H\leq G$. Consider the equivalence relation $R$ on $G$ given by
$$\forall a,b\in G,\ aRb\ \mbox{if}\ ab^{-1}\in H.$$
Then for each $a\in G$, $[a]=Ha$ where $Ha=\{ha:h\in H\}$. $Ha$ is called a right coset of $H$ in $G$.

Example. Consider $\equiv\mod n$, the congruence relation modulo $n$ on $\mathbb{Z}$. For each $a\in \mathbb{Z}$, $[a]=n\mathbb{Z}+a$. The right coset $n\mathbb{Z}+a$ is called the congruence class of $a$ modulo $n$.

Now we are ready to discuss Lagrange’s Theorem.

Theorem [Lagrange’s Theorem] If $G$ is a finite group and $H\leq G$, then $|H|||G|$.

Proof. $G=Ha_1\cup Ha_2\cup\cdots\cup Ha_k$ and $Ha_i\cup Ha_j=\emptyset$ if $i\ne j$, $i,j=1,2,\dots, k$. Due to the cancellation law, we see that $|H|=|Ha_i|$ for all $i=1,2,\cdots, k$. Therefore,
\begin{align*}
|G|&=\sum_{i=1}^k|Ha_i|\\
&=\sum_{i=1}^k|H|\\
&=k|H|.
\end{align*}
This completes the proof.

If $G$ is finite, the number of right cosets of $H$ in $G$, namely $\frac{|G|}{|H|}$ is called the index of $H$ in $G$ and is written as $|G:H|$ or $i_G(H)$. Here, we use the notation $|G:H|$.

It should be noted that the converse of Lagrange’s Theorem need not be true. For example, the alternating group of index 4
$$A_4=\{1,(123),(132),(124),(142),(134),(143),(234),(243),(12)(34),(13)(24),(14)(23)\}$$ has no subgroup of order 6 though $|A_4|=12$ and $6|12$.

Theorem. A group $G$ of prime order is cyclic.

Proof. Let $|G|=p$, a prime. Let $H\leq G$. Then by Lagrange’s Theorem, $|H|||G|$ and so either $|H|=1$ or $|H|=p$. If $H\ne\{e\}$, then $H=G$. If $a\ne e\in G$, $\langle a\rangle=G$.

Let $G$ be a finite group and $a\ne e\in G$. Then $H=\langle a\rangle\leq G$. So, $a^m=e$ for some $m\in\mathbb{N}$.

Definition. If $G$ is finite, then the order of $a\ne e\in G$, written $|a|$ or $o(a)$, is the least positive integer $n$ such that $a^n=e$.

Corollary. If $G$ is finite and $a\ne e\in G$, then $|\langle a\rangle|||G|$.

Theorem. If $G$ is a finite group of order $n$, then $a^n=e$ for all $a\in G$.

Proof. Let $a\ne e\in G$ and $|\langle a\rangle|=k$. Then by Lagrange’s Theorem $k|n$ i.e. $n=kl$ for some $l\in\mathbb{N}$. So,
$$a^n=a^{kl}=(a^k)^l=e^l=e.$$