How do I solve a congruence system that doesn't satisfies the Chinese Remainder Theorem?

Question

I have the following system

$ x \equiv 2 (mod 4)$

$ x \equiv 2 (mod 6) $

$ x \equiv 2 (mod 7) $

And I can't apply the Chinese remainder Theorem.

I tried applying the Chinese remainder Theorem to the last 2 congruences, which gave me that the set of solutions of that 2 congruences is $ 2 + 42 \cdot \beta $ with $\beta$ belonging to $\Bbb Z$.

Then I solved the set of solutions of the first congruence, which is $ 6 + 4 \cdot \alpha $ with $\alpha$ belonging to $\Bbb Z$.

A common solution would be the one that satisfies $ 2 + 42 \cdot \beta = 6 + 4 \cdot \alpha$, equivalently, the one that satisfies $ 42 \cdot \beta + 4 \cdot \alpha = 4$, and this (because of Bezout Identity) have solution only if $mcd(42,4)=4$ which is not true. So this would mean this system have no solution, which is incorrect (I think).

Then, what can I do?

Answer 1

First of all you have that the solution of the first relations are given by $4\alpha + 2$. Then this will give you the relation:

$$2 + 4\alpha = 2 + 42\beta \iff 42 \beta = 4 \alpha \iff 21 \beta = 2 \alpha$$

And certainly this one have solution. In fact the Bezout Lemma says that $xa + by = m$ has a solution iff $\operatorname{gcd}(x,y) \mid m$. It doesn't have to be equal.

Answer 2

Hint $\,\ 4,6,7\mid x\!-\!2\iff {\rm lcm}(4,6,7)\mid x\!-\!2$

For more see here on CCRT = Constant case optimization of CRT = Chinese Remainder Theorem.

Answer 3

In a system of congruences $x\equiv a_i\pmod {n_i}$, the Chinese theorem applies when all $n_i$ are relatively prime.

When this is not the case, there is an additional condition to know if there are solutions, which is :

$\forall (i,j)\mid a_i\equiv a_j\pmod{\gcd(n_i,n_j)}$

In that case, the solutions are to be computed modulo the LCM of all $n_i$.

Here since all $a_i$ are equal the criterion is trivially met and $2$ is a trivial solution

$x\equiv 2\pmod{\operatorname{lcm}(4,6,7)}\equiv 2\pmod {84}$

In general to solve such system you have to find $n'_i$ such that $\begin{cases} n'_i\mid n_i\\ \operatorname{lcm}\limits_{i=1..N}(n'_i)=\operatorname{lcm}\limits_{i=1..N}(n_i)\\ \gcd(n'_i,n'_j)=1\end{cases}$

Here we have $n_1=4,n_2=6,n_3=7$ whose LCM is $84$.

The equivalent system while be $n'_1=4,n'_2=3,n'_3=7$ with the same LCM.

The remainders are then recomputed with these new $n'_i\quad:\ x\equiv a_i\pmod{n'_i}$

$\begin{cases} x\equiv 2\pmod{4}\\ x\equiv 2\pmod{6}\\ x\equiv 2\pmod{7} \end{cases} \implies \begin{cases} x\equiv 2\pmod{4}\\ x\equiv 2\pmod{3}\\ x\equiv 2\pmod{7} \end{cases}$

Now we can apply Chinese theorem and $x\equiv 2\pmod{84}$ as previously.