2
$\begingroup$

I have a system of congruences: $$ x\equiv 1\pmod 2 \\ x\equiv 2\pmod 3 \\ x\equiv 3\pmod 4 \\ x\equiv 4\pmod 5 \\ x\equiv 5\pmod 6 \\ x\equiv 0\pmod 7 $$

2, 3, 4, 5, 6, 7 are non-pairwise coprime, so i can't use Chinese Reminder Theorem in this case.

$x\equiv 3\pmod 4$ yields $x\equiv 1\pmod 2$ so i can just drop 3-rd equation from the system.

Using this principle i got new system:

$$ x\equiv 1\pmod 2 \\ x\equiv 2\pmod 3 \\ x\equiv 0\pmod 7 \\ $$

Solving this system o got the answer: $497 + 42k$, which is actually wrong.

Right answer i can get here: http://maciejkus.com/chinese_remainder/ , which is: $119 + 420k$

How can i solve this system right?

$\endgroup$
  • $\begingroup$ You cannot drop third, you can only drop first and second equation. $\endgroup$ – user164524 Jan 17 '15 at 13:57
  • $\begingroup$ Are you sure it isn't $x\equiv 6\pmod{7}$? $\endgroup$ – kingW3 Jan 17 '15 at 13:57
  • $\begingroup$ $497+42k$ is the solution of the system with the $3$ equations. Better would be the representation $35+42k$. $\endgroup$ – Peter Jan 17 '15 at 13:57
  • 1
    $\begingroup$ Considering also the equation with the $mod\ 5$, we get $119+120k$ and $119$ solves the complete system already. So, we have to find the period. It is $lcm(2,3,4,5,6,7)=420$. So, the solution of the complete system is $119+420k$. $\endgroup$ – Peter Jan 17 '15 at 14:00
  • 1
    $\begingroup$ It is enough to consider the equations with the moduli $3,4,5,7$ because the modulo-$4$-equation covers the modulo-$2$-equation and therefore (together wit the modulo-$3$-equation) also the modulo-$6$-equation. And now, you have pairwise coprime moduli. $\endgroup$ – Peter Jan 17 '15 at 14:12
1
$\begingroup$

$$ x\equiv 1\pmod 2 \\ x\equiv 2\pmod 3 \\ x\equiv 3\pmod 4 \\ x\equiv 4\pmod 5 \\ x\equiv 5\pmod 6 \\ x\equiv 0\pmod 7 $$

$x\equiv 5\pmod 6$ if and only if $x\equiv 1\pmod 2$ and $x\equiv 2\pmod 3$. and both conditions are already on the list. This leaves us with

$$ x\equiv 1\pmod 2 \\ x\equiv 2\pmod 3 \\ x\equiv 3\pmod 4 \\ x\equiv 4\pmod 5 \\ x\equiv 0\pmod 7 $$

$x\equiv 3\pmod 4$ implies that $x\equiv 1\pmod 2$ but not vice-versa. So we keep the first and remove the second.

$$ x\equiv 2\pmod 3 \\ x\equiv 3\pmod 4 \\ x\equiv 4\pmod 5 \\ x\equiv 0\pmod 7 $$

The solution is $x = 119$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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