Simultaneous congruence and Chinese Remainder Theorem

Question

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?

Should the solution start with assume there exists a solution then prove the contradiction?

Answer 1

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.