Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
    
Why "Note that from the first congruence we had x≡4(mod7)." ? When I use CRT I get $x\equiv 39 \pmod{3^3*7}$. And why –  xawey Sep 6 at 19:17
    
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. –  André Nicolas Sep 6 at 20:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.