H,K are both subgroups of , and is abelian, so HK is a subgroup of .

now

first question: what is |H| and |K|?

one is tempted, at first, to say that:

, but this is incorrect. why? consider the two congruences:

by the CRT, this has a unique solution (mod pq). therefore, one (and only one) of the numbers (mod pq) 1,1+p,1+2p,....,1+(q-1)p is not in .

therefore |H| = q-1 = φ(q), and similarly, |K| = p-1 = φ(p).

second question: what is |H∩K|?

if x is in H∩K, this means:

which, again, by the CRT, has a unique solution (mod pq), namely, 1.

thus, |HK| = φ(p)φ(q).

is this equal to φ(pq) = ?

we can verify this by counting the positive integers less than pq, co-prime to pq.

if gcd(x,pq) > 1, then x is either a multiple of q, or a multiple of p (can't be both, since pq isn't less than pq).

multiples of p: p,2p,.....,(q-1)p, we have q-1 of these (and q doesn't divide any of these)

multiples of q: q,2q,....,.(p-1)q, we have p-1 of these (and p doesn't divide any of these).

so φ(pq) = (pq-1) - (p-1) - (q-1) = pq - 1 - p + 1 - q + 1 = pq - p - q + 1 = (p-1)(q-1).

since HK is a subgroup of with the same order, it must be the entire group.