Using Chinese Remainder Theorem for two equations with non-coprime moduli I have
\begin{align}
x & \equiv a\mod m \\
x & \equiv b \mod n
\end{align}
Normally I would solve for $x$ by doing $(an\cdot \operatorname{inverse}(n,m) + bm\cdot \operatorname{inverse}(m,n)) \bmod mn$ but I am not sure how to modify this for when $m$ and $n$ are not coprime. Assume a solution exists.
 A: Assume $m = m_1 d$, $n = n_1 d$ where $m_1$ and $n_1$ are coprime.
And $d < min(m,n)$.
$x \equiv a~(\mod m_1 d) \Rightarrow x \equiv a\mod d~(\mod m_1) \qquad\mbox{and}\qquad x\equiv a\mod m_1~(\mod~d) $
Similary, $ x \equiv a\mod~d~(\mod{n_1})
~\mbox{and}~x\equiv a\mod~{n_1}~(\mod d) $.
So, we have additional condition of solution existance: $a\mod{m_1} \equiv a\mod{n_1}~(\mod d)$.
Now we compute $x_{n_1, m_1}$ for $n_1$ and $m_1$. Then we have new system:
$x \equiv x_{n_1,m_1}~(\mod n_1m_1)$
$x \equiv a ~(\mod d) $
Notice, $\min(d, n_1m_1) < \min(m,n)$, it is a semi-invariant. So we can solve it recursively.
A: Hint $\ $ A solution exists $\rm\!\iff\! \exists\, j,k\in\Bbb Z\!:\  a+jm = x = b+kn\!\iff\! kn-jm = a\!-\!b.\:$ If so $\rm\:(n,m)\mid a\!-\!b.\:$ Conversely, if $\rm\:(n,m)\mid a\!-\!b\:$ then the Bezout identity $\rm\:xn - ym = (n,m)\:$ scales to a solution $\rm\: kn-jm = a\!-\!b\:$  by multiplying the Bezout identity by $\rm\:(a\!-\!b)/(n,m).$
A solution is unique $\rm\:mod\,\  lcm(m,n),\ $ since if $\rm\:x,x'$ are solutions then
$$\rm \begin{eqnarray}x'\equiv x\ \ (mod\ m)\\ \rm x'\equiv x\ \ (mod\ n)\ \end{eqnarray}\!\!\iff\! m,n\mid x'\!-\!x\!\iff\! lcm(m,n)\mid x'\!-\!x\!\iff\! x'\!\equiv x\ \ (mod\ lcm(m,n))$$
So we reduce to solving $\rm\ xn - ym = (n,m) =: d,\:$ or $\ \rm x\, \hat n - y\, \hat m\, = 1,\ $ for $\rm\ \hat n = n/d,\,\ \hat m = m/d.\ $ This is equivalent to $\rm\ mod\ \hat m:\ x\,\hat n\equiv 1,\ $ so $\rm\ x\equiv 1/{\hat n},\:$ which exists since $\rm\:(\hat n,\hat m) = 1.$
