Suppose $s$ and $t$ are relatively prime.Show that $U(st)$ is isomorphic to $U(s)\oplus U(t)$.
I want to show that $\phi$ :$U(st)$ $\rightarrow$ $U(s)\oplus U(t)$ defined by $\phi(x)=(x\bmod s,x\bmod t)$ is an isomorphism.
(1) Obviously $\phi$ is well defined.
(2) $\phi$ is one-one beacuse $\phi(x)=\phi(y)$ yields $x \equiv y$ mod $s$ and $x \equiv y \mod t$. Thus $x \equiv y \mod st$ since $\gcd(s,t)=1$
(3) How to show $\phi$ is onto?
(4)$\phi$ is operation preserving is also trivial.
We define $U(n)$ to be the set of all positive integers less than $n$ and relatively prime to $n$ with the operation multiplication modulo n
Best Answer
Approach one:
In this approach we directly show it is surjective. Given $(x,y)\in U(s)\times U(t)$. Consider $\phi(xt T+ys S)$ where $tT\equiv1~mod~(s),~sS\equiv1~mod~(t)$. Why does such $S,~T$ exists? Why is $xt T+ys S$ relative prime to $st$? What is $\phi(xt T+ys S)$?
Approach two:
In this approach we assume we know the fact that Euler phi function satisfies $$\varphi(st)=\varphi(s)\varphi(t)$$ , say by method of elementary number theory. Hence the cardinality of $U(st)$ and $U(s)\times U(t)$ are same.
$U(st),~U(s)\times U(t)$: these are finite sets. Now you have a injective function between two finite sets. If these two finite sets have same cardinality, then by set theory, this injection is not only an injection but also a what?
Final remark:
Approach one gives a proof that $$\varphi(st)=\varphi(s)\varphi(t)$$ for relatively prime $s,t$.