# Chinese remainder problem

$\begin{cases} x \equiv 39 \pmod{189}\\ x \equiv 25 \pmod{539}\\ x \equiv 39 \pmod{1089}\end{cases}$

but two moduli are not pairwise prime $(189, 1089)=3$ What do we do to solve it then? Should we try to solve $x\equiv 39 \pmod{189}$ and $x\equiv 25 \pmod{539}$ First?

Thanks

-

There are no solutions: both $539$ and $1089$ are divisible by $11$, so their corresponding congruences imply $$x \equiv 3 \pmod {11}$$ and $$x \equiv 6 \pmod {11}.$$

-
I should have noticed that:) Thank you! –  user124471 Jul 6 '14 at 7:38

As $\displaystyle189=27\cdot7, x\equiv39\pmod{189}\implies x\equiv39\pmod7\equiv4$ and $x\equiv39\pmod{27}\equiv12$

As $\displaystyle1089=9\cdot121, x\equiv39\pmod{1089}\implies x\equiv39\pmod9\equiv3$ and $x\equiv39\pmod{121}$

As $\displaystyle539=49\cdot11,x\equiv25\pmod{1089}\implies x\equiv25\pmod{11}\equiv3$ and $x\equiv25\pmod{49}$

Now, $\displaystyle x\equiv3\pmod9$ is a subset of $x\equiv39\pmod{27}\equiv12\implies x\equiv12\pmod9\equiv3$

and $\displaystyle x\equiv4\pmod7$ is a subset of $x\equiv25\pmod{49}\implies x\equiv25\pmod7\equiv4$

But $\displaystyle x\equiv3\pmod{11}$ contradicts $\displaystyle x\equiv39\pmod{121}\implies x\equiv39\pmod{11}\equiv6\not\equiv3\pmod{11}$

-
Thank you! Nicely proved. Clear and readable. –  user124471 Jul 6 '14 at 7:38