27.1.1 Lagrange’s theorem
Let be a finite group, and a subgroup of , then divides .
This is a very useful theorem which has a lot of applications, for example in cryptography.
Let’s start by considering the set for , 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 on these sets, given by
This is an equivalence relation (TODO: proof) on the set , and very importantly, equivalence relations form a partition of the set (proof in Section TODO: write section). Intuitively, this means that we can divide up all the elements of into a number of different sets called equivalence classes.
Thus we claim that for any , and therefore
Therefore, we just need a bijection , which we can obtain by defining . Then we just need to prove that is a bijection!
Injective. Assume , then , thus and therefore , from which we have that , which means that is injective.
Surjective. Fix , then for some , thus we have that , so is surjective.
Therefore, we have some integer (equal to the number of equivalence classes) such that
That is, we have proven that divides .