# Show that $HK=\mathbb{Z}_n^\times$

Let $p$ and $q$ be distinct prime numbers and $n=pq$. Show that $HK=\mathbb{Z}_n^\times$ for the subgroups $H=\{[x]\in\mathbb{Z}_n^\times\mid x\equiv 1\pmod{p}\}$ and $K=\{[y]\in\mathbb Z_n^\times \mid y\equiv 1\pmod{q} \}$.

What I have so far is that I know that $\phi(pq)=(p-1)(q-1)$. My book says that I should use a counting argument or CRT.

I chose a counting argument. So would it be correct if I said that there are $p-1$ congruence classes relatively prime to $p$ and $q-1$ congruences classes relatively prime to $q$. Thus set $HK$ has a total of $\phi(pq)$ distinct equivalence classes. Thus $HK=\mathbb Z_n^\times$.

By the chinese remainder theorem way. Suppose $$x \equiv 1 \pmod{p}$$ and $$y \equiv 1 \pmod{q}$$ where $\gcd(p,q)=1$. By the chinese remainder theorem we know that there exists a unique solution call it $a$. It follws that $p|(a-1)$ and $q|(a-1)$ From here im stuck now.

• in fact, this (unique) solution is $a=1$ (because works and its unique!) – Martín Vacas Vignolo Dec 28 '17 at 11:40

First of all $|H|=q-1$, and not $p-1$ as you claimed. This deserves a proof, because at first sight it seems that $H$ contains $q$ elements, namely $[1],[p+1],[2p+1],\dots,[(q-1)p+1]$. But one of these classes (and only one!) is not in $\mathbb Z_n^{\times}$ since the numbers $1,p+1,\dots,(q-1)p+1$ give different remainders modulo $q$.
Furthermore, $H\cap K=\{[1]\}$. (This also has to be proved!)
In the end, $HK\simeq H\times K$, so $|HK|=|H||K|=(q-1)(p-1)$.