# Multiplication Modulo - Group Homomorphism

Let $U(n)$ be the multiplicative group of units modulo $n$ for an integer $n$ (that is, $U(n)$ is the group containing the units of $\mathbb{Z}_n$).

Let $s$ and $t$ be relatively prime integers.

I need to prove that: $f \colon Us (st) \to U(t)$ is an onto map, where $$Us(st)= \{x\in U(st)\mid x\equiv 1 \pmod s\}.$$

Define $f$ as

$f (x) = x \bmod t$, where $x$ belongs to $Us(st)$

-

Let $a\in U(t)$. You are looking for an $x$ such that \begin{align*} x&\equiv 1 &&\pmod{s}\\ x&\equiv a &&\pmod{t}. \end{align*} The fact that such an $x$ exists and is unique modulo $st$ is a consequence of the Chinese Remainder Theorem. Since $\gcd(a,t)=1$ and $\gcd(1,s)=1$, then it also follows that $\gcd(x,st)=1$, so $x\in U(st)$, as desired.

Added. The OP wants an explicit description of $x$; this is given by the Chinese Remainder Theorem, whose proof is usually constructive.

Since $\gcd(s,t)=1$, there exist integers $\alpha,\beta$ such that $\alpha s+\beta t = 1$. Then $\alpha s \equiv 0\pmod{s}$, $\alpha s\equiv 1 \pmod{t}$, $\beta t\equiv 1\pmod{s}$, and $\beta t\equiv 0\pmod{t}$. Let $$x = (\alpha s)a + (\beta t)1.$$ Then $x \equiv 1\pmod{s}$, and $x\equiv a\pmod{t}$, as desired.

This is the argument you can find for the proof of the Chinese Remainder Theorem in any book on elementary number theory. It's even in Wikipedia.

-
Thank you so much for your feed back. I agree with you on this. But can we define clearly a preimage of this "a". – Tav Aug 15 '11 at 16:30
@Tavleen: Yes. The usual proof of the Chinese Remainder Theorem is constructive. I'll add it. – Arturo Magidin Aug 15 '11 at 16:32
Also, how to ensure that x here is strictly less than st. Only then we can say that it belongs to Us(st). – Tav Aug 15 '11 at 17:03
@Tavleen: If you need $x$ to be strictly less than $st$, then replace it with its remainder modulo $st$. It's not that hard! – Arturo Magidin Aug 15 '11 at 17:15
Thanks a lot. I got it. – Tav Aug 15 '11 at 17:24