# Chinese Remainder Theorem, redundant information

I want to solve the following system of congruences:

$x \equiv 1 \mod 2$

$x \equiv 2 \mod 3$

$x \equiv 3 \mod 4$

$x \equiv 4 \mod 5$

$x \equiv 5 \mod 6$

$x \equiv 0 \mod 7$

I know, but do not understand why, that the first two congruences are redundant. Why is this the case? I see that the modulo of the congruences are not pairwise relatively prime, but why does this cause a redundancy or contradiction? Further, why is it that in the solution to this system, we discard the first two congruences and not

$x \equiv 3 \mod 4$

$x \equiv 5 \mod 6$

being that $gcd(3,6) = 3$ and $gcd(2,4) = 2$ ?

EDIT:

How is the modulo of the unique solution effected if I instead consider the system of congruences without the redundancy i.e. does $M = 4 * 5 * 6 * 7$ or does it remain $M= 2*3*4*5*6*7$?

-
$x\equiv 1 \pmod 2$ means that $x$ is odd. And $x \equiv 3 \pmod 4$ implies that $x$ is odd, but the implication does not work the other way around. – I like Serena Aug 3 '14 at 21:10
For your edit: you can't apply Chinese Remainder Theorem if the moduli are not relatively prime. You can very easily reach a contradiction this way (e.g. $x \equiv 1 \bmod 2$ and $x \equiv 2 \bmod 4$ has no solutions). – Hao Ye Aug 4 '14 at 1:59

Note that:

$$x\equiv 3 \mod 4 \Rightarrow x= 4k+3\Rightarrow x\equiv 1 \mod 2\\ x\equiv 5\mod 6 \Rightarrow x = 6k'+5\Rightarrow x\equiv 2\mod 3$$

-

Hint $\ x\equiv -1\$ mod $\,2,3,4,5,6\iff x\equiv -1 \pmod m\$ for $\, m = {\rm lcm}(2,3,4,5,6) = {\rm lcm}(4,5,6)$

because $\ 2,3,4,5,6\mid x\!+\!1\iff 4,5,6\mid x\!+\!1,\$ since $\,4,6\mid x\!+\!1\,\Rightarrow\,2,3\mid x\!+\!1$

-

If $n|N$, then $x \equiv a \pmod N \implies x \equiv a \pmod n$. Note that the converse is not true.

So $x \equiv 3 \pmod 4 \implies x \equiv 3 \pmod 2 \implies x \equiv 1 \pmod 2$

Similarly,

$\quad x \equiv 5 \pmod 6 \implies x \equiv 5 \pmod 2 \implies x \equiv 1 \pmod 2$

and

$\quad x \equiv 5 \pmod 6 \implies x \equiv 5 \pmod 3 \implies x \equiv 2 \pmod 3$

As I said before, it is not true that

$\quad x \equiv 2 \pmod 3 \implies x \equiv 5 \pmod 6 (e.g.,\; x = 8)$ and

$\quad x \equiv 1 \pmod 2 \implies x \equiv 5 \pmod 6 (e.g.,\; x = 9)$

-