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.

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

share|improve this question
    
$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 at 21:10
2  
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 at 1:59

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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$

share|improve this answer

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.