How do I prove that if $\gcd(n,m)$ divides $a-b$, then $x\equiv a \pmod n$ and $x\equiv b \pmod m $ has a solution? Let $n,m$ be positive integers $>1$.
Assume that $\gcd(n,m)\mid (a-b)$
Then how do I show that $x\equiv a \pmod n$ and $x\equiv b \pmod m$ has a solution?
I"m struggling with this for an hour and I can't find a solution..
 A: In fact it can be proven that the system 
$\begin{align}
x&\equiv a\mod(n)\\
x&\equiv b\mod(m) 
\end{align}$
has a solution $x$ if and only if $(n,m)|a-b$. The $\Rightarrow)$ proof is obvious, but the other direction, which is precisely OP's question, is slightly less obvious. 
Let $d=(n,m)$, then by Bezout's identity we know that there exists $s,t\in\mathbb{Z}$ such that $ns+mt=d$. Given $d|a-b$, then we know $a-b=dk$ for some $k\in \mathbb{Z}$. Therefore we have $nsk+mtk=a-b$. Rearrange the expression and we have $m(-tk)+a=nsk+b$. Let $x=m(-tk)+a$, we have $x-a=m(-tk)$, which immediately means $x\equiv a \mod(m)$. On the other hand we have $x=nsk+b$, which gives us $x-b=nsk$, which entails $x\equiv b \mod(n)$.
A: Assume $m>n$.  Let $g=\gcd{(m,n)}$.  Since $g|(a-b)$, there exists an integer $k$ such that $a-b=gk$
Since $g=\gcd{(m,n)}$, $gk_1=m, gk_2=n$ for integers $k_1, k_2$.
Finally, since $x\equiv a\pmod{n}$, then $$x-a=nb=gk_2b$$ and thus $x\equiv a\pmod{g}$ as well
Now, suppose that there is no solution to the system.  Then 
$$x\not\equiv a\pmod{n}$$$$ x\equiv b\pmod{m}$$
is one case then.  This implies
$$x-a=nb+c, \text{ where }b,c\in \mathbb{Z}, 0\le c\lt n$$
$$x-b=md, \text{ where } d\in \mathbb{Z}$$
Now look at $(x-b)-(x-a)$
$$(x-b)-(x-a)=md-(nb+c)$$
$$a-b=gk_1d-gk_2b-c$$
$$a-b=g(k_1d-k_2b)-c$$
Note that it is possible that $c=g$, since $g\le n$.  But 
$$x\not\equiv a\pmod{n}\Rightarrow x-a\neq nb\Rightarrow x-a\neq gk_2b$$And thus $x\not\equiv a\pmod{g}$. This implies that $c\neq g$ since 
$$x-a=nb+c\Rightarrow x-a=gk_2b+g \Rightarrow x-a=g(k_2b+1)$$ which contradicts the fact that $x\not\equiv a\pmod{g}$. 
But we have the initial condition that $a-b=gk$ for some integer $k$, but here, since letting $k=k_1d-k_2b$ gives us $a-b=gk+c$, we have a contradiction.  Therefore, our assumption that there is no solution is wrong and the system has a solution.
A: Write $n=\prod p^{e_p}$ and $m=\prod p^{v_p}$. For each $p$ we want
$$x\equiv a\bmod p^{e_p} \quad{\rm and}\quad x\equiv b\bmod p^{v_p} \quad {\rm given} \quad a\equiv b\bmod p^{\min\{e_p,v_p\}}.$$
So set $c_p:=a$ if $e_p\ge v_p$ and $c_p:=b$ if $e_p<v_p$ and then solve the system $x\equiv c_p\bmod p^{\max\{e_p,v_p\}}$.
