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