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?
2026-03-25 09:24:05.1774430645
On
Chinese Remainder Theorem whose modulus are not coprime
1k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
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.
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$.