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
    Thank you so much for your feed back. I agree with you on this. But can we define clearly a preimage of this "a".2011-08-15
  • 0
    @Tavleen: Yes. The usual proof of the Chinese Remainder Theorem is constructive. I'll add it.2011-08-15
  • 0
    Also, how to ensure that x here is strictly less than st. Only then we can say that it belongs to Us(st).2011-08-15
  • 0
    @Tavleen: If you need $x$ to be strictly less than $st$, then *replace it with its remainder* modulo $st$. It's not that hard!2011-08-15
  • 0
    @Tavleen: Did you bother to read what I wrote above? The proof of the Chinese Remainder Theorem, which I wrote above for the case of two congruences, **tells you exactly how to find the preimage**. I just *showed* you how to find the preimage. What exactly is the problem?2011-08-15
  • 0
    Thank you for the wonderful explaining. You have been a great teacher.2011-08-15
  • 0
    I think the comment you were referring to is old. I have no doubt anymore. Thanks for the extensive reply.2011-08-15