Isomorphism from $U(st) →U(s)\oplus U(t)$

Question

Let $s,t$ are relatively prime then $U(st) $ is isomorphic to $ U(s)\oplus U(t)$.

Define a function from $U(st) →U(s)\oplus U(t)$ by $x\rightarrow (x $mod $s,x$ mod $t)$.

I proved this is 1-1 and order preserving But i'm stuck at onto.

Here is my attempt to prove onto: Since Euler's totient function is multiplicative and $s,t$ are relatively prime , both $U(st) $ and $ U(s)\oplus U(t)$ has same number of elements.So 1-1 implies the function is onto. I think it is correct

But I'm looking for a straight forward method to prove it is onto using definition of onto.( i.e every element in co domain has pre image)

Def: U(n) is set of all integers relatively prime to n and less than n

Thanks

Answer 1

You do not need to use the Chinese Remainder theorem, but its constructive proof tells you how to find the surjection. In fact you will find, if $x\in U(s), y\in U(t)$:

$$(xt\cdot(t^{-1}\text{ mod }s) + ys\cdot(s^{-1}\text{ mod }t)) \text{ mod }st\mapsto (x,y)$$

All that's left is to verify it is the case.