Let $m$ and $n$ be positive integers with $\gcd(m, n) = 1$.

Let $A = \{1, 2, \dots, m\}$, $B = \{1, 2, \dots , n\}$, $X = \{1, 2, \dots, mn\}$, and let $Y = A \times B$.

a) Show that for every integer $x \in X$, there exists a unique ordered pair $(a, b)$ in $Y$ such that $x \equiv a \mod m $ and $x \equiv b \mod n$.

b) Show that this defines a one-to-one correspondence between the sets $X$ and $Y$.

My attempt:

a) By the Chinese Remainder theorem, we know that there is a unique solution $x$ to the system of congruences modulo $mn$. Assume for some $x$ there also exists a pair $(a',b')$ which satisfies the system of congruences.


$x \equiv a \equiv a' \mod m$

$x \equiv b \equiv b' \mod n$

I want to show that $(a,b) = (a',b')$ but I get stuck. Any tips as to where to go from here? Is showing that $a \equiv a' \mod m$ enough to show that $a=a'$ ?


b) For this bit, doesn't it naturally follow that since for each $x$, there is a unique $(a,b)$ such that that $F : X \to Y$ is one-to-one?


(a) Since $x\pmod{m}$ is just the remainder of the integer division between $x$ and $m$, there is only one integer $a\in[0,m-1]$ such that $x\equiv a\pmod{m}.$ Assuming that $x\equiv a\pmod{m}$ and $x\equiv a'\pmod{m}$, with $a,a'\in[0,m-1]$ and $a\neq a'$, we have that $m$ divides both $x-a$ and $x-a'$, but this is impossible since it leads to $m|(a-a')$, with $0<|a-a'|<m$.

(b) Yes, it naturally follows since, by a similar argument, for any $(a,b)\in Y$ there is only one element $x\in X$ such that $x\equiv a\pmod{m},x\equiv b\pmod{m}$. So there is an injective map from $Y$ to $X$, while $$f:X\to Y,\qquad f(x)=\left(x\!\!\!\!\pmod{m},\,x\!\!\!\!\pmod{n}\right)$$ is an injective map from $X$ to $Y$.


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.