What's the remainder of a natual number divided by lcm(m,n)? Let $x,m,n \in \mathbb N$, $m,n>0$,
and $x \equiv r \pmod m$,
$x \equiv s \pmod n$ ($r-s \equiv 0 \pmod{gcd(m,n)}$).
It seems $x \equiv r \equiv s \pmod {gcd(m,n)}$;
But $x \equiv ? \pmod {lcm(m,n)}$
 A: The general solution first requires that you solve the equation $mu+nv=\gcd(m,n)$.
Then the value is $$x\equiv \frac{(s-r)}{\gcd(m,n)}mu+r\pmod {lcm(m,n)}$$
That might seem a bit gross, but it is just an application of the Chinese Remainder Theorem. It obviously only works if $\gcd(m,n)|s-r$.
It's clear that this $x$ satisfies $x\equiv r\mod m$. substituting $mu=\gcd(m,n)-nv$ shows that $x\equiv s\pmod n$
A: Existence: $\rm\ \ d = (m,n)\mid m\mid x\!-\!r,\ \ d\mid n\mid x\!-\!s\ \Rightarrow\ \color{#C00}{d\mid r\!-\!s}\, =\, x\!-\!s-(x\!-\!r)\:$  is necessary; $\ $ sufficient too: $ $ Bezout $\rm\,\Rightarrow\:\exists\,j,\,k\in\Bbb Z\!:\ kn-jm = r\!-\!s,\: $ so $\rm\  x = s+kn = r+jm\ $ is a solution. 
Uniqueness: $\rm\:x,x'$ solutions $\rm\!\iff\! x'\equiv x\ mod\ m,n\!\iff\! m,n\mid x'\!-\!x\!\iff\! lcm(m,n)\mid x'\!-\!x.$
Construction: $ $ use the extended Euclidean algorithm to find $\rm\:u,v\in\Bbb Z\!:\ um+vn = d = (m,n)\:$ then multiply this equation by $\rm\:(r\!-\!s)/d,\:$ yielding $\rm\:kn-jm = r\!-\!s,\:$ then proceed as above. This yields the formula in the answer of Thomas (general CRT = Chinese Remainder Theorem).
