# I can't use Chinese Remainder Theorem.

I have a problem with: $$\begin{cases} 6x\equiv 2 \mod 8 \\ 5x \equiv 5 \mod 6 \end{cases}$$ I want to use the Chinese Remainder Theorem, but I can't because of the fact $\gcd(8,6) > 1$. How can I deal with it?

For the first equation, it is equivalent to say, for some $n\in\Bbb Z$

\begin{align*} 6x&\equiv2\pmod8&6x &= 8n + 2\\ 3x&\equiv1\pmod4&3x &= 4n + 1\\ 3\cdot3x&\equiv3\pmod4&3\cdot3x&= 3\cdot4n + 3\\ x&\equiv3\pmod4&x &= 4(3n-2x)+3\\ \end{align*}

For the second equation, \begin{align*} 5x&\equiv5\pmod6\\ 5\cdot5x &\equiv 5\cdot5\pmod6\\ x &\equiv 1 \pmod 6 \end{align*}

Then following @mathh's hint above, $x\equiv1\pmod2$ (which does not conflict with first equation) and $x\equiv1\pmod3$.

The system is now $$\begin{cases} x\equiv3 \pmod 4\\ x\equiv1 \pmod 3 \end{cases}$$

$$6x\equiv2\pmod8\iff3x\equiv1\pmod4$$

As $3\equiv-1\pmod4,$

$$3x\equiv-x\equiv-1\iff x\equiv-1\pmod4\ \ \ \ (1)$$

$(1)\implies x\equiv-1\pmod2\equiv1$

$5x\equiv5\pmod6\iff x\equiv1\pmod6\ \ \ \ (2)$ as $(5,6)=1$ (See $\#12$ of property )

$(2)\implies x\equiv1\pmod2$ and $x\equiv1\pmod3\ \ \ \ (3)$

Apply CRT on $(1),(3)$