27.1 Groups

27.1.1 Lagrange’s theorem

Theorem 27.1.1

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

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

Let’s start by considering the set gHgH for gGg\in G, which we will define as

gH={gΔh:hH}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

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

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

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

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

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

  1. 1.

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

  2. 2.

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

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

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

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