2
$\begingroup$

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.

$\endgroup$
  • 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 '19 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 '19 at 9:29
2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.