Chinese Remainder Theorem solvability criterion for noncoprime moduli

Question

I'm trying to learn how to use the Chinese Remainder Theorem (CRT), and in order to give some context:

We search for all $x ∈ Z$, where $Z$ is the set of integers.

$x≡a_1\pmod{m_1}$

$x≡a_2\pmod{m_2}$

...

$x≡a_k\pmod{m_k}$

The easy case (which I can solve) is if all $m_i$, where $i=1,2,...,k$ are pairwise coprime.

Example:

$x≡4\pmod 5$

$x≡5\pmod 6 $

$x≡3\pmod 7$

Then the first equation is satisfied iff $x=4+5s$, for some $s ∈ Z$.

These $x$ also satisfy the second equation iff $4+5s≡_6 5 ↔ -s≡_6 1 ↔ s=-1+6t$, for some $t ∈ Z$. Thus $x=4+5(-1+6t)=-1+30t$.

Lastly, these $x$ also satisfy the third equation iff $-1+30t ≡_7 3 ↔ 2t ≡_7 4 ↔ t ≡_7 2 ↔ t = 2+7n$, for some $n ∈ Z$. Thus $x=59+210n$.

Now to my issue, I have the problem:

$x≡2\pmod 4$

$x≡3\pmod 5$

$x≡5\pmod 6$

Here $\gcd(4,6)=2$, so they are not coprime and I don't know how to solve this. Can someone please solve it and explain why the problem becomes more difficult to solve when $m_i$ are not pairwise coprime.

Answer 1

Hint $ $ An analogy: there is no integer $\,x\,$ whose units digit is even in decimal but odd in hex, because the former implies that $\,x\,$ is even but the latter implies that $\,x\,$ is odd. Said more arithmetically, recalling that congruence persists $\!\bmod \rm\color{#0a0}{factors}$ of the modulus we have

$$\begin{align}x\equiv 0\!\!\!\pmod{\!\color{#0a0}2\cdot 5}\,\Rightarrow\, x\equiv \color{#c00}0\!\!\!\pmod{\!\color{#0a0}2}\\[.2em] {\rm vs.}\ \ \ x\equiv 1\!\!\!\pmod{\!\color{#0a0}2\cdot 8}\,\Rightarrow\, x\equiv\color{#c00} 1\!\!\!\pmod{\!\color{#0a0}2}\end{align}\qquad $$

We obtained a $\rm\color{#0a0}{parity}$ $\rm\color{#c00}{contradiction}$ by reducing the system mod a $\rm\color{#0a0}{common}$ modulus factor, i.e. the first congruence implies that every solution $\,x\,$ is even: $\,x \equiv\color{#c00} 0\pmod{\! 2},\,$ but the second congruence implies that $\,x\,$ is odd: $\,x\equiv\color{#c00} 1\pmod{\! 2}.\,$

Similarly, in general, reducing congruence pairs modulo the $\rm\color{#0a0}{gcd}$ of their moduli yields necessary conditions for solvability (also sufficient if we include such conditions for every pair of moduli).

For your system, recall that by CRT a pair is solvable if their moduli are coprime, so we need only examine non-coprime pairs of moduli to check for nonsolvability. Doing so reveals a parity contradiction - so they are inconsistent - just like in our example above, i.e. the first & last have noncoprime moduli $4,6$ so we reduce them mod their $\,\gcd(4,6)=\color{#0a0}2.$

Then $\,x\equiv 2\pmod{\!\color{#0a0}2\cdot 2}\,\Rightarrow\, x\equiv 2\equiv\:\!\color{#c00}0\pmod{\!\color{#0a0}2}$

But $\ \ \ x\equiv 5\pmod{\!\color{#0a0}2\cdot 3}\,\Rightarrow\, x\equiv 5\equiv\color{#c00}1\pmod{\!\color{#0a0}2},\, $ contra $\rm\color{#c00}{prior}$, so the system is inconsistent.

Similarly if $\,\color{#0a0}d = \gcd(m,n)\,$ then $\,x\equiv a\pmod{\! m},\ x\equiv b\pmod{\!n}\,\Rightarrow\, a\equiv x\equiv b\pmod{\!\color{#0a0}d}\,$ thus $\,\color{#0a0}d\mid a-b\,$ is a necessary condition for solvability (also sufficient as explained above).

Answer 2

The general result is this:

The linear system of congruences: \begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\[-1ex] \vdots \\[-1ex] x\equiv a_k\pmod{m_k} \end{cases} has solutions if and only if $$a_i\equiv a_j\mod{\gcd(m_i,m_j)}\quad\text{for all } i,j \enspace(1\le i,j\le k)$$

Here, $2\not\equiv 5\mod 2$, so there are no solutions.