1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Exactly. This seems to be the much more useful result that you should take away from this exercise. $\endgroup$ – CPM Jun 4 '15 at 2:57
  • $\begingroup$ 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$. $\endgroup$ – letsmakemuffinstogether Jun 4 '15 at 3:04
  • $\begingroup$ @lets I explained further. $\endgroup$ – Bill Dubuque Jun 4 '15 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.