# Chinese Remainder Theorem solvability for non-coprime moduli

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.

• If x is 2 mod 4 it's even. But if the same x is 5 mod 6 it's odd. No solution. Feb 21, 2019 at 8:41
• Ok, makes sense. But how do I solve a system of congurences that is solvable and the $m_i$ terms are not pairwise coprime? Feb 21, 2019 at 9:29

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

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.