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
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
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
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.
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.
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
That is, we have proven that $H$ divides $G$.