Let $a,b,m,n \in \mathbb{N}$ with $\gcd(m,n)=1$ prove $\{ x = a \pmod m,x=b \pmod n\}$ has a solution

Question

Let $a,b,m,n \in \mathbb{N}$ with $\gcd(m,n)=1$ prove $\{ x = a \pmod m,x=b \pmod n\}$ has a solution and it is unique modulo $mn$

---

Definitions

$x=a \pmod m \iff m|(x-a) \iff x-a=m q_1$ where $q_1 \in \Bbb N$ $x=b \pmod n \iff n|(x-b) \iff x-b=n q_2$ where $q_2 \in \Bbb N$

Also, $\gcd(m,n)=1$ so $\exists u,v \in \Bbb N$ s.t. $mu+vn=1$

---

Stuck on Putting it together

$x=a+m q_1$ and $x=b+nq_2$,

Now $$\begin{aligned} x&=a+m q_1*1=a+m q_1*(um+vn)=a+mmuq_1+vn*mq_1 \\ x&=b+nq_2*(1)=b+nq_2(mu+vn)=b+nq_2mu+n^2 v q_2 \end{aligned}$$

Kind of lost at this point not sure if I took a wrong turn somewhere

$\vdots$

___=____ $\pmod {mn}$

---

Answer 1

You already have $mu+vn=1$, so $mub+vnb=b$ so $$mub\equiv b\pmod{n}$$

Similarly, you hvae $$vna\equiv a\pmod{m}$$

Now just let $$x=mub+vna$$

Answer 2

Alternatively: The map $f\colon \{0,\ldots,nm-1\}\to\{0,\ldots,n-1\}\times \{0,\ldots,m-1\}$, $x\mapsto (x\bmod n,x\bmod m)$is injective and between sets of same cardinality, hence surjetcive. To see injectivity, assume $f(x)=f(y)$. Then $x\equiv y\pmod n$ and $x\equiv y\pmod m$, hence $x\equiv y\pmod{\operatorname{lcm}(n,m)}$.