3
$\begingroup$

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

1 Answers 1

4

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.

  • 0
    I think the comment you were referring to is old. I have no doubt anymore. Thanks for the extensive reply.2011-08-15