How to prove that $|HK| = \dfrac{|H| \; |K|}{|H \cap K|}$? [duplicate]

Solution 1:

Let us write down all the elements of $H=\{ h_1, ... , h_n\}$ and $K=\{k_1, ... , k_m\}$, where $n=|H|$ and $m = |K|$. List them down as follows: $$ h_1k_1\quad h_1k_2 \quad \ldots \quad h_1k_m $$ $$ h_2k_1\quad h_2k_2 \quad \ldots \quad h_2k_m $$ $$ \quad \ \vdots \quad \ \ \ \ \vdots \quad $$ $$ h_nk_1\quad h_nk_2 \quad \ldots \quad h_nk_m $$

There are $nm$ of these elements. Now, all we have to do is to somehow divide them into sets of size $|H \cap K|$ and then we are done by picking one element from each set.

How do we do this? Well, consider $h_ak_b = h_ck_d$. Then, note that $h_c^{-1}h_a = k_b^{-1}k_d$. Hence these elements(which are the same) are in $H \cap K$. Similarly, if there is an element $l \in H \cap K$, then $l = h_a=k_b$ for some $a$ and $b$. From here, $h_ae = k_be$, where $e$ is the identity of the group containing $H$ and $K$ as subgroups.

Hence,

Every pair of equal elements in the grid produces an element of $H \cap K$

And

every element of $H \cap K$ produces a pair of equal elements in the grid.

By this duality, we divide the above grid into exactly $|H \cap K|$ parts, where each part contains elements which are all equal. How many parts are there? The answer is $\frac{nm}{|H \cap K|}$. Hence, the number of (distinct) elements of $HK$ is obtained by picking one element from each of these parts, which gives $|HK| = \dfrac{|H||K|}{|H\cap K|}$

Solution 2:

The idea is that every element in $HK$ is a multiplication of $h\in H$ and $k\in K$. But if $k\in H\cap K$ then $hk$ is already an element of $H$ and therefore if we take $h'=hk \in H$ and $k'=e \in K$ you get a different way of getting the element $hk$ and therefore $|H||K|$ is overcounting.

Therefore, to get the actual size, you need to first remove all the elements that cause the overcounting, so every element will be counted only once.