# A Proof of Lagrange’s theorem

The sole goal of this post will be to prove Lagrange’s theorem. Let $H$ be a subgroup of a group $G$. Recall that a left coset of $H$ is $gH=\{gh|h\in H\}$, where $g\in G$. We proved that this is $[g]$.

Definition: Let $[G:H]$ denote the number of left cosets of $H$ in $G$; this is called the index of $H$ in $G$.

Suppose $G=\mathbf{Z}$. Then let $H=2\mathbf{Z}\leq G$. This is a subgroup of $G$, and we can ask what the cosets of $H$ are. Answering this is quite simple, and, indeed, we have nothing but the collection of odd and even integers: $0+2\mathbf{Z}=\{2n|n\in\mathbf{Z}\}$ and $1+2\mathbf{Z}=\{2n+1|n\in\mathbf{Z}\}$. Thus the index $[\mathbf{Z}:2\mathbf{Z}]$ is $2$. More generally, $[\mathbf{Z}:n\mathbf{Z}] = n$. This should be obvious by a similar observation. The index therefore says “how many copies of $H$ form $G$”.

An important theorem in group theory says that if $G$ is a finite group, and if $H\leq G$, then $|G|$ is divisible by $|H|$. More precisely:

Theorem: Let $G$ be a group, and let $H\leq G$. Then $|G|=[G:H]\times |H|$, where $|X|$ denotes the order of $X$, or the number of elements of $X$.

Proof. Recall that each left coset arises as a member of a partition (because it comes from an equivalence class, which in turn gives rise to a unique partition). Let’s digress a little, and show that if $g\in G$, then $gH$ has the same number of elements as $H$. If we want to show this, it suffices to find maps $f:H\to gH$ and $b:gH\to H$ which are inverses, i.e., such that $fb$ is the identity on $gH$ and $bf$ is the identity on $H$.

Define $f:H\to gH$ by letting $f:h\mapsto gh$. Conversely, define $b:gH\to H$ by $b:k\mapsto g^{-1}k$. Then $fb(k)=f(g^{-1}k)=gg^{-1}k=k$, and $bf(h)=b(gh)=gg^{-1}h=h$. Thus $f$ is a bijection, and $gH$ and $H$ have the same number of elements.

Now, because cosets are all disjoint, each element of $G$ is in only one coset. Since the number of left cosets of $H$ is $[G:H]$, we see that $|G|=[G:H]|H|$. This is because $G=g_1H\cup g_2H\cup\cdots$, and either $g_iH\cap g_jH=\emptyset$ or $g_iH=g_jH$, so $|G|=|g_1H|+|g_2H|+\cdots$; and since for any $g_i\in G$, we showed that $|g_iH|=|H|$, this becomes $|G|=|H|+|H|+\cdots$ where there are $d$ copies of $|H|$, which is given by the number of cosets $g_iH$, which in turn is simply $[G:H]$. Consequently, if $G$ is finite, then $|G|/|H|$ is a positive integer. QED.

Let’s now give an application of Lagrange’s theorem. Let us classify all finite groups up to order five (we choose five because it is the smallest prime number for which there is a number lesser than $5$ which is not prime). Because any group of prime order is cyclic, if the order of the finite group is $2,3$, or $5$, then it is cyclic. So suppose $G$ is a finite group whose order is $4$. If there’s an element $g$ of $G$ which has order $4$, then $G$ is cyclic (because the order of the subgroup generated by $g$ is also $4$).

Suppose $G$ doesn’t contain any elements of order $4$; by Lagrange’s theorem, this means that $G$ contains elements of order $1,2$. The only element of order $1$ is the identity, so every other element must have order $2$. We can draw out a multiplication table for elements of $G$; drawing this out will be left to you, the reader. Next time, we’ll study, in more detail, orders of elements, etc.

Have fun,
SKD