# Simultaneous congruence and Chinese Remainder Theorem

For example, if two given linear congruences have $m_1$ and $m_2$ not coprime, how to use CRT to show that there is no solution?

Congruences also hold modulo any divisor of the modulus. Hence, given two linear congruences \begin{align*} x\equiv a_1 \mod m_1 \\ x\equiv a_2 \mod m_2 \end{align*} it is also true that \begin{align*} x\equiv a_1 \mod (m_1,m_2) \\ x\equiv a_2 \mod (m_1,m_2) \end{align*} It follows that, if $a_1\not\equiv a_2 \pmod{(m_1,m_2)}$, you have an obvious contradiction to the existence of any solution.

Remark: It is not difficult to prove that the converse holds, too. That is, if the above condition is satisfied, then there is a solution to this system.

Suppose you are given

\begin{align} x &\equiv a_1 \mod{m_1} \\ x &\equiv a_2 \mod{m_2} \end{align}

Let $$g = \gcd(m_1,m_2)$$ and suppose

\begin{align} m_1 &= g \ n_1 \\ m_2 &= g \ n_2 \end{align}

It follows that $$a_1 \equiv a_2 \pmod g$$

If this is true, then you can write

\begin{align} x &\equiv a_1 \mod{g} \\ x &\equiv a_1 \mod{n_1} \\ x &\equiv a_2 \mod{n_2} \end{align}

where $$n_1, n_2,$$ and $$g$$ are all pairwise prime. So a solution can be found.

If $$a_1 \not \equiv a_2 \pmod g$$, then there is no solution.