# questions regarding the proof and consequence of chinese remainder theorem

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?

-

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.

-

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

-