3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – Klaas van Aarsen Aug 3 '14 at 21:10
  • 2
    $\begingroup$ 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). $\endgroup$ – Hao Ye Aug 4 '14 at 1:59
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

$x \equiv 1 \mod 2$

$x \equiv 2 \mod 3$

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

$x \equiv 4 \mod 5$

$x \equiv 5 \mod 6 \iff \left.\begin{cases} x \equiv 1 \mod 2 \\ x \equiv 2 \mod 3 \end{cases} \right\}$ By the CRT.

$x \equiv 0 \mod 7$


So first we replace $x \equiv 5 \mod 6$ with $\left.\begin{cases} x \equiv 1 \mod 2 \\ x \equiv 2 \mod 3 \end{cases} \right\}$


$x \equiv 1 \mod 2$

$x \equiv 2 \mod 3$

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

$x \equiv 4 \mod 5$

$x \equiv 1 \mod 2$

$x \equiv 2 \mod 3$

$x \equiv 0 \mod 7$


Now, because $x \equiv 1 \pmod 2$ is redundant, we remove all instanced of it and we remove all but one instance of $x \equiv 2 \mod 3$.


$x \equiv 2 \mod 3$

$x \equiv 3 \mod 4$

$x \equiv 4 \mod 5$

$x \equiv 0 \mod 7$


In this case, we can cheat a little if we change the first three congruences to equivalent congruences.

$ \left. \begin{array}{l} x \equiv -1 \mod 3 \\ x \equiv -1 \mod 4 \\ x \equiv -1 \mod 5 \end{array} \right\} \ \iff x \equiv -1 \mod 60$ (Again, by the CRT.)

$x \equiv 0 \mod 7$


So we now have


$x \equiv -1 \mod 60$

$x \equiv 0 \mod 7$


To solve this, we start with $x \equiv 0 \mod 7$, which implies that $x = 7n$ for some integer $n$. Substitute that into $x \equiv -1 \mod 60$ and you get

$7n \equiv -1 \mod 60$

So we need to find $\dfrac 17 \pmod{60}$ The most fundamental way to do this is to inspect numbers congruent to $1 \pmod{60}$ until we find one that is a multiple of $7$. At worst, we will have to examint $7$ such numbers.

$1, 61, 121, 181, 241, \color{red}{301}$

Since $7 \times 43 = 301$, then $\dfrac 17 \equiv 43 \pmod{60}$. So we conclude that $n \equiv -43 \equiv 17 \mod{60}$.

Then $x = 7n = 119 \mod{420}$.

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