Modular Arithmetic, GCDs, and Potential use of the Chinese Remainder Theorem I am trying to prove the following as a study problem for an upcoming number-theory exam: if $a_1 \not \equiv a_2$ (mod gcd($m_1,m_2$)) then the system of equations 
$x \equiv a_1$ (mod $m_1$) 
$x \equiv a_2$ (mod $m_2$) 
has no solution.
My attempt so far is this. Suppose $c \in \mathbb{Z}$ is a solution. Then $c \equiv a_1$ (mod ($m_1$) $\implies$ $c - a_1 = m_1k, \ k \in \mathbb{Z}$ $\implies$ $c - a_2 = m_2r$, $r \in \mathbb{Z}$ $\implies$ $a_2 - a_1 = m_1 k - m_2r$. Any hints would be appreciated.
 A: Suppose there were a solution as you say $c \equiv a_1 $ (mod $m_1$) and $c \equiv a_2$ (mod $m_2$).  But then let $d=gcd(m_1,m_2)$, so $d \mid m_1, m_2$, say $m_1=ds_1$ and $m_2=ds_2$.  But then $c \equiv a_1 $ (mod $m_1=ds_1$) and $c \equiv a_2$ (mod $m_2=ds_2$).  This means $ds_1 \mid (a_1-c)$ and $ds_2 \mid (a_2 -c)$.  Thus $d \mid (a_1 -c)$ and $d \mid (a_2 -c)$.  But this means $a_1 \equiv a_2 \equiv c$ (mod $d=gcd(m_1,m_2)$).  This is a contradiction.
A: The congruences persist mod $\,d\,$ for any common divisor $\,d\mid m_1,m_2.\,$ Therefore
$$a_1\equiv x\equiv a_2\!\!\pmod d\qquad$$
Remark $\ $ Persistence is easy: $\:d\mid m_i\!\mid x-a_i\Rightarrow\, x\equiv a_i\!\pmod{\!d}.\: $  A well-known example of such congruence persistence is: $ $ an integer $\,n\,$ has the same parity as its least digit $\,n_0,\,$ i.e.
$$\begin{align} n \equiv n_0\!\!\!\!\pmod{10}\ &\Rightarrow\ \ \ \ n\equiv n_0\!\!\!\!\pmod 2\\[4pt]
\rm{e.g.}\ \ \ 32\color{#c00}1\equiv \color{#c00}1\!\!\!\!\pmod{10}\ &\Rightarrow\,321\equiv\color{#c00}1\!\pmod 2\end{align}$$  
Written in simpler language: $\,32\color{#c00}1\,$ is odd because its least digit $\,\color{#c00}1\,$ is odd. 
