Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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|cite|improve this question
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|cite|improve this answer

$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|cite|improve this answer

Your Answer


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.