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.





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


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

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

2 Answers 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.