Chinese Remainder Theorem whose modulus are not coprime

1k Views Asked by At

Is it possible to apply Chinese Remainder Theorem to the follow system of congruences?
$$\begin{align}x&\equiv1\mod 15\\ x&\equiv2\mod 21\\ x&\equiv3 \mod 35\end{align}$$ $15, 21$ aren't coprime
$21$ and $35$ aren't coprime
Is CRT applicable to this problem?

2

There are 2 best solutions below

6
On

The system doesn't have a solution, You can apply CRT to $x \equiv 1 \bmod 15$ to get $x \equiv 1 \bmod 3$ and $x \equiv 1 \bmod 5$, and since $5$ and $21$ are coprime, you can combine $x \equiv 1 \bmod 5$ and $x \equiv 2 \bmod 21$ to get $x \equiv 86 \bmod 105$, which is incompatible with $x \equiv 3 \bmod 35$.

0
On

$$x \equiv 1 \pmod{15} \iff \begin{array}{c} x \equiv 1 \pmod 3 \\ x \equiv 1 \pmod 5 \end{array} $$

$$x \equiv 2 \pmod{21} \iff \begin{array}{c} x \equiv 2 \pmod 3 \\ x \equiv 2 \pmod 7 \end{array} $$

$$x \equiv 3 \pmod{35} \iff \begin{array}{c} x \equiv 3 \pmod 5 \\ x \equiv 3 \pmod 7 \end{array} $$

Note that there are contradictions with the values of $x \pmod 3, x \pmod 5, \ \text{and} \ x \pmod 7$.

Hence there can be no solution.