# 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.

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.

• Thank you. That is a very clear answer. – letsmakemuffinstogether Jun 4 '15 at 2:53

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.

• Exactly. This seems to be the much more useful result that you should take away from this exercise. – CPM Jun 4 '15 at 2:57
• While I understand CPM's answer, I unfortunately do not understand yours. Can you please explain to me what $mod \ d: a_1 \equiv x \equiv a_2$ means? I'm not familiar with the use of the colon to the right of $d$. – letsmakemuffinstogether Jun 4 '15 at 3:04
• @lets I explained further. – Bill Dubuque Jun 4 '15 at 3:44