1
$\begingroup$

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.

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

Maybe the counting argument is not as obvious as you think.

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.