H,K are both subgroups of , and is abelian, so HK is a subgroup of .
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.