Suppose that $x \equiv 3 \pmod 7, x \equiv 3 \pmod {10}$ and $x \equiv 23 \pmod{25}$. Explain why the Chinese Remainder Theorem does not apply to compute x. Transform the problem to an equivalent problem where the Chinese Remainder Theorem can be used and solve it.
The question is unsolvable before transformation because the theorem requires modular numbers to be relatively prime to each other and $\gcd(10,25)=5$ so they are not relatively prime. How do I transform it and solve it?
Best Answer
Note that you can write $x \equiv 3 \pmod {10}$ as system of two equations namely $x \equiv 3 \pmod{5}$ and $x \equiv 3 \pmod{2}$. But note that the first first equation is already contained in $x \equiv 23 \pmod{25}$, so it's redundant. Therefore we have:
$$ \begin{cases} x \equiv 3 \pmod 7 \\ x \equiv 3 \pmod {10} \\ x \equiv 23 \pmod{25} \end{cases}\iff \begin{cases} x \equiv 3 \pmod 7 \\ x \equiv 3 \pmod {2} \\ x \equiv 3 \pmod {5} \\ x \equiv 23 \pmod{25} \end{cases}\iff \begin{cases} x \equiv 3 \pmod 7 \\ x \equiv 3 \pmod {2} \\ x \equiv 23 \pmod{25} \end{cases}$$
Now solving the system on the right is just a simple application of Chinese Remainder Theorem.