Let be a group and let be subgroups of finite index; say and . Prove that . Deduce that if and are relatively prime, then .

Lemma 1: Let and be sets, a map, and an equivalence relation on . Suppose that if then for all . Then given by is a function. Moreover, if is surjective, then is surjective, and if implies for all , then is injective. Proof: is clearly well defined. If is surjective, then for every there exists such that . Then , so that is surjective. If , then , so that , and we have .

First we prove the second inequality.

Lemma 2: Let be a group and let be subgroups. Then there exists an injective map . Proof: Define by . Now if , then we have , so that , and , so that . Thus . Moreover, if then we have , so that . By Lemma 1, there exists an injective mapping given by .

As a consequence, if and are finite, .

Now to the first inequality.

Lemma 3: Let be a group and . Let be a set of coset representatives of . Then the mapping given by is bijective. Proof: (Well defined) Suppose . Then , so that , and we have . (Surjective) Let . Now for some ; say . Then , so that is surjective. (Injective) Suppose . Then ; in particular, , so that and hence . So , and in fact . Thus , and is injective.

As a consequence, we have .

Now in this case we have . Thus divides and divides , so that divides . In particular, since all numbers involved are natural, .

Finally, if and are relatively prime, then , and we have .