2
$\begingroup$

Wikipedia states the Chinese Remainder Theorem as follows:

Suppose $n_1, \dots, n_k$ are positive integers which are pairwise coprime. Then for any given sequence of integers $a_1, \dots, a_k$, there exists an integer $x$ such that $$ \begin{cases} x \equiv a_1 \operatorname{mod} n_1 \\ x \equiv a_2 \operatorname{mod} n_2 \\ \vdots \\ x \equiv a_k \operatorname{mod} n_k \end{cases}$$ and all solutions $x$ are congruent mod $n_1n_2 \cdots n_k$.

My notes state the theorem as follows:

Let $m$ and $n$ be relatively prime positive inters. Let $r$ and $s$ be integers such that $$rm + sn =1.$$ Then the function $$f: \mathbb{Z} / m \times \mathbb{Z}/n \to \mathbb{Z} / mn$$ defined by $$f(x,y)= y \cdot rm + x \cdot sn$$ is a bijection.

How does the bijection give us that there always exists a solution to the system of modular congruences ?

$\endgroup$
2
$\begingroup$

The inverse of $f$ is $g:\mathbb Z_{mn}\to\mathbb Z_m\times\mathbb Z_n$ defined by $g(a\bmod mn)=(a\bmod m,a\bmod n)$. (Check this!)

If $a_1,a_2$ are given then, by the surjectivity of $g$, there is $x$ such that $g(x\bmod mn)=(a_1\bmod m,a_2\bmod n)$, and this means $x\equiv a_1\bmod m$ and $x\equiv a_2\bmod n$.

This generalizes as follows: if $n_1,\dots,n_k$ are coprime integers, then the map $g:\mathbb Z_{n_1\cdots n_k}\to\mathbb Z_{n_1}\times\cdots\times\mathbb Z_{n_k}$ defined by $g(a\bmod n_1\cdots n_k)=(a\bmod n_1,\dots,a\bmod n_k)$ is an isomorphism (of rings) and now use again the surjectivity of $g$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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