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.

Suppose that $m$ and $n$ are positive prime number, and $r$ and $s$ are some integers.

we can define the following: $rm + sn = 1$.

The question is, how do we lead to the following?

$rm + sn = 1 \mod {mn}$

$sn = 1 \mod {m}$

Also,

the function f : $\mathbb{Z}/m$ × $\mathbb{Z}/n$ -> $\mathbb{Z}/mn$ defined by $f(x, y) = y · rm + x · sn$ is a bijection. The inverse map $f^{−1} : \mathbb{Z}/mn -> \mathbb{Z}/m × \mathbb{Z}/n$ is $f^{−1}(z) = $ ($x$-mod-m, $y$-mod-n).

What does this function imply in the usage of Chinese remainder theorem? Also, what does $x$-mod-m exactly mean?

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

If $rm+sn=1$, then certainly $rm+sn\equiv 1\mod mn$.

Also, $sn\equiv 0+sn\equiv rm+sn\equiv 1\mod m.$

The function $f$ takes $(\overline x,\overline y)\in\mathbb Z/m\times\mathbb Z/n$ to $\overline{xrm+ysn} = yrm+xsn\mod mn.$

Your inverse expression can be written $f^{-1}(\overline z)=(z\mod m, z\mod n)\in \mathbb Z/m\times\mathbb Z/n.$ You should try to justify that these are group homomorphisms, and that $f\circ f^{-1}$ and $f^{-1}\circ f$ are identity maps.

share|improve this answer
add comment

$x \pmod{m}$ can be interpreted as the remainder of $x$ after division by $m$ is performed. With this interpretation, $x\equiv y\pmod{m}$ means "$x$ and $y$ have the same remainder after divsion by $m$." Further, $x\equiv 0 \pmod{m}$ means "$x$ is divisible by $m$."

So for your first question, if $rm+sn$ is the same number as $1$, then certainly they have the same remainders after division by $mn$.

So at this point, you have $rm+sn-1\equiv 0 \pmod{mn}$. This says the left hand side is a multiple of $mn$, but certainly a multiple of $mn$ is a multiple of $m$, so $rm+sn-1\equiv 0\pmod{m}$ as well. However since $m\equiv0 \pmod{m}$, we can further reduce this to $sn-1\equiv 0\pmod{m}$. Thus $sn\equiv 1\pmod{m}$.

share|improve this answer
add comment

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.