# 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. – coffeemath Feb 21 '19 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? – BLCAAN Feb 21 '19 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, i.e. 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. Similarly reducing congruence pairs modulo the gcd of their moduli yields necessary conditions for solvability (which are also sufficient, indeed, the linked post shows a congruence system is solvable iff each pair of congruences is solvable).

By CRT a pair is solvable if their moduli are coprime, so we need only check non-coprime pairs.

The first & last have noncoprime moduli $$4,6$$ so we consider 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 a sufficient condition by 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.