27.1 Groups

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. 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

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