1
$\begingroup$

Find all solutions: $\begin{cases} x\equiv 39 \mod(189) \\ x\equiv 25 \mod(539) \\ x\equiv 399 \mod(1089) \end{cases}$

But $189=3^3\cdot7$, $539=11\cdot7^2$ and $1089=3^2\cdot 11^2$, so I can't use here Chinese remainder theorem.

1 Answers 1

2

You can find a system of congruences equivalent to the original system, but with pairwise relatively prime moduli.

For example, the first congruence is equivalent to the system $x\equiv 39\pmod{3^3}$, $x\equiv 39\pmod{7}$.

The second original congruence is equivalent to the system $x\equiv 25\pmod{11}$ $x\equiv 25\pmod{7^2}$.

Note that from the first congruence we had $x\equiv 4\pmod{7}$. If $ \equiv 25\pmod{7^2}$ then $x\equiv 4\pmod{7}$, our first two original congruences are equivalent to the system $x\equiv 39\pmod{3^3}$, $x\equiv 25\pmod{7^2}$, $x\equiv 25\pmod{11}$.

The third original congruence can be similarly dealt with. When we are through we end up with a system with moduli $3^3$, $7^2$, and $11$.

  • 0
    The congruence of your comment is certainly correct. But for the first part of the analysis, we are kind of doing CRT backwards, we are *separating* a congruence to a complicated modulus $3^3\cdot 7$ into two congruences modulo $3^3$ and $7$. And $39\equiv 4\pmod{7}$. The congruence modulo $3^3$ can similarly be rewritten as $x\equiv 12\pmod{3^3}$. All three congruences we started with can be thus separated, and then we look at the pieces and put them together at the end. There are other ways to do the job, but I tried to pick one that has a clean logical structure.2014-09-06