# Chinese Remainder Theorem with with non-pairwise coprime moduli

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?

• You cannot drop third, you can only drop first and second equation. – user164524 Jan 17 '15 at 13:57
• Are you sure it isn't $x\equiv 6\pmod{7}$? – kingW3 Jan 17 '15 at 13:57
• $497+42k$ is the solution of the system with the $3$ equations. Better would be the representation $35+42k$. – Peter Jan 17 '15 at 13:57
• 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$. – Peter Jan 17 '15 at 14:00
• 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. – Peter Jan 17 '15 at 14:12

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