Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.