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?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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}$$
$\begingroup$
$\endgroup$
$$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)$
