2

Is it a true:?

$$\begin{cases} 2x \equiv 2 \mod 5 \\ 3x \equiv 2 \mod 4 \\5x \equiv 2 \mod 6\end{cases}$$

$$2x \equiv 2 \mod 5 \iff x \equiv 1 \mod 5 $$ $$3x \equiv 2 \mod 4 \iff 6x \equiv 4 \mod 4 \iff 3x \equiv 2 \mod 2 \iff x\equiv 0 \mod 2 $$ $$5x \equiv 2 \mod 6 \iff 10x \equiv 4 \mod 6 \iff 5x \equiv 2 \mod 3 \iff x \equiv 1 \mod 3 $$ So we have got simple system: $$\begin{cases} x \equiv 1 \mod 5 \\ x \equiv 0 \mod 2 \\x \equiv 1 \mod 3\end{cases}$$ And now we can use CRT.

user180834
  • 1,453
  • Your second two derived congruences are incorrect. – paw88789 Jan 10 '15 at 11:16
  • I edited, and now? – user180834 Jan 10 '15 at 11:21
  • 1
    $3x\equiv 2 \pmod{4}$ can't be multiplied through by $2$, similarly for the third congruence. These operations (multiplying by something not relatively prime to the modulus) does not preserve solutions. – paw88789 Jan 10 '15 at 11:28
  • 2
    Well, we can multiply a congruence mod $4$ by two, but the logical connective would be $\Rightarrow$ instead of $\Leftrightarrow$ since multiplication by two is not a reversible operation when working mod $4$, and this multiplying by two can introduce extraneous solutions. – anon Jan 10 '15 at 11:29
  • ok, and when it comes to: $da \equiv db \mod dc \iff a \equiv b \mod c $ Is it correct? – user180834 Jan 10 '15 at 11:39

1 Answers1

2

As $3\equiv-1\pmod4,3x\equiv2\pmod4\iff-x\equiv2\iff x\equiv-2$

But $-2\equiv2\pmod4\implies x\equiv2\pmod4\ \ \ \ (1)$

$(1)\implies x\equiv0\pmod2$

Similarly, $5x\equiv2\pmod6\iff-x\equiv2\iff x\equiv-2\iff x\equiv4\pmod6\ \ \ \ (2) $

$(2)\implies x\equiv4\pmod3\equiv1\ \ \ \ (3)$

and $x\equiv4\pmod2\equiv0$

Like I can't use Chinese Remainder Theorem., $2x\equiv2\pmod5\iff x\equiv1\pmod5\ \ \ \ (4)$

We need CRT on $(1),(3),(4)$

Community
  • 1
lab bhattacharjee
  • 274,582