The following system of linear congruences in its given form cannot be solved
using the Chinese Remainder Theorem. Can you help me transform the system sufficiently
such that the Chinese Remainder Theorem can be applied, without actually solving the system?
$$x \equiv 1 \pmod {15}$$
$$2x \equiv 11 \pmod {21}$$
$$4x \equiv −6 \pmod {35}$$
(I can reduce $x \equiv 1 \pmod {15}$ to $x \equiv 1 \pmod 5$ and $x \equiv 1 \pmod 3$.
But I'm not sure how to reduce the other two congruences to end up with mod $3,5$ and $7$?)
Thanks in advance
Best Answer
$$x \equiv 1 \pmod{15}$$ $$2x \equiv 11 \pmod{21}$$ This means $$x \equiv a \pmod{105}$$ Note that possible values of $a$ consistent with $x \equiv 1 \pmod{15}$ are $\{1,16,31,46,61,76,91\}$. Hence, $2a \in \{2,32,62,92,122,152,182\}$. Now we are given that $2a \equiv 11 \pmod{21}$. Hence, $2a = 32$ is the only possible solution. Hence, $$x \equiv 16 \pmod{105}$$ Further, you have $2x \equiv -3 \pmod{35}$, which is consistent with $x \equiv 16 \pmod{105}$. Hence, we get that $$x \equiv 16 \pmod{105}$$