Number Theory Proof with Chinese Remainder Theorem

Question

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.

Then,

$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'$ ?

Since

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?

Answer 1

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