# 27.1 Groups

## 27.1.1 Lagrange’s theorem

###### Theorem 27.1.1

Let $(G,\Delta)$ be a finite group, and $(H,\Delta)$ a subgroup of $G$, then $|H|$ divides $|G|$.

This is a very useful theorem which has a lot of applications, for example in cryptography.

Let’s start by considering the set $gH$ for $g\in G$, which we will define as

$gH=\{g\Delta h:h\in H\}$ (27.1)

Here’s one of those magic tricks we can pull as though straight from a hat; we can define an equivalence relation $\sim$ on these sets, given by

$g_{1}\sim g_{2}\iff g_{1}H=g_{1}H_{2}$ (27.2)

This is an equivalence relation (TODO: proof) on the set $G$, and very importantly, equivalence relations form a partition of the set $G$ (proof in Section TODO: write section). Intuitively, this means that we can divide up all the elements of $G$ into a number of different sets called equivalence classes.

Thus we claim that for any $g$, $|gH|=|H|$ and therefore

$|G|=\text{number of equivalence classes}\cdot|H|.$ (27.3)

Therefore, we just need a bijection $\phi:H\to gH$, which we can obtain by defining $h\mapsto gh$. Then we just need to prove that $\phi$ is a bijection!

1. 1.

Injective. Assume $\phi(a)=\phi(b)$, then $ga=gb$, thus $g^{-1}(ga)=g^{-1}(gb)$ and therefore $(g^{-1}g)a=(g^{-1}g)b$, from which we have that $a=b$, which means that $\phi$ is injective.

2. 2.

Surjective. Fix $k\in gH$, then $k=gh$ for some $h$, thus we have that $k=\phi(h)$, so $\phi$ is surjective.

Therefore, we have some integer $n$ (equal to the number of equivalence classes) such that

$|G|=n|H|$ (27.4)

That is, we have proven that $|H|$ divides $|G|$.