# Chinese Remainder Theorem whose modulus are not coprime

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?

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

• Isnt it simpler ? $3$ divides $15$ and $21$ so $1\equiv 2(\mod 3)$. – Rene Schipperus May 7 '18 at 1:18
• Is there a quick way to see if a system does not have a solution? Do I just check to see if the modulus are coprime or not? – Juan May 7 '18 at 1:18
• @ReneSchipperus that is a faster method, you're right – Connor Harris May 7 '18 at 1:18
• @Juan systems with non-coprime moduli can have solutions, but they don't have to. For example, $x \equiv 2 \bmod 4, x \equiv 4 \bmod 6$ has a solution, but not (say) $x \equiv 2 \bmod 4, x \equiv 3 \bmod 6$. The simple method is to apply CRT to break every congruence into a system of congruences modulo powers of primes, and then check whether the resulting system is inconsistent. – Connor Harris May 7 '18 at 1:20
• What exactly do you mean by inconsistent? – Juan May 7 '18 at 1:22

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