Chinese Remainder Theorem Transformation with not coprime moduli

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?

• You can apply the CRT because here $\gcd(7,10,25)=1$ so you just have to build the right $x$ using an interesting Bézout relation ! Nov 26 '17 at 13:22

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.

• why is it already implied by? Nov 25 '17 at 22:29
• If $x\equiv 23 \pmod{25}$ then $x\equiv 23 \equiv 3 \pmod{5}$ Nov 25 '17 at 22:32

The idea is to find modulo the highest powers of distinct primes

$x\equiv3\pmod{10}\implies x\equiv3\pmod2\ \ \ \ (1)$

and $x\equiv3\pmod5$

which is already implied by $$x\equiv23\pmod{25}$$

• why is it already implied by? Nov 25 '17 at 22:29