# How to solve this equation if we can't use Chinese remainder theorem.

Let consider: $$\begin{cases}6x \equiv 2 \mod 8\\ 5x \equiv 5\mod 6 \end{cases}$$ We can't use Chinese remainder theorem because $\gcd(8,6) = 2 > 1$ Help me.

• You can still use CRT even if $\gcd(6,8) > 1$ – Frank Vel Nov 26 '14 at 10:23

The system is equivalent to

$$6x \equiv 2 \pmod 8\iff3x\equiv 1\pmod4\iff x\equiv 3\pmod4$$ $$5x\equiv 5\pmod6\iff x\equiv 1\pmod6$$

$x=4n+3$ (from $1^{rst}$ equation)

Putting in second

$$4n+3\equiv 1\pmod6$$ $$4n\equiv 4\pmod6$$ $$2n\equiv 2\pmod3$$ $$n\equiv1 \pmod3$$

So $n=3m+1$

$x=4(3m+1)+3=12m+7$

So any integer of the form $12m+7$ is a solution where $m\in\mathbb{Z}$

$6x \equiv 2 \mod 8$ means that $6x=2+8k$, with $k \in \mathbb{Z}$

It means also that $3x = 1 +4k$, or $3x \equiv 1 \mod 4$ ...

Hint: If $$5x\equiv 5\pmod{6}\implies x\equiv1 \pmod{6}\implies x=6k+1$$

• That... doesn't really answer the question. – 5xum Nov 26 '14 at 10:17

Hint: write explicately $x = 24k + x'$ with $0\le x' < 24$ and solve for $x'$.

$$\begin{array}{l} \left\{ \begin{array}{l} 6x \equiv 2\left[ 8 \right] \\ 5x \equiv 5\left[ 6 \right] \\ \end{array} \right. \Leftrightarrow \left\{ \begin{array}{l} 3x \equiv 1\left[ 4 \right] \\ x \equiv 1\left[ 6 \right] \\ \end{array} \right. \\ \Rightarrow \left\{ \begin{array}{l} x \equiv - 1\left[ 4 \right] \\ x \equiv 1\left[ 6 \right] \\ \end{array} \right. \Rightarrow \left\{ \begin{array}{l} x \equiv 3\left[ 4 \right] \\ x \equiv 1\left[ 6 \right] \\ \end{array} \right. \\ 4k + 3 = 6m + 1 \Leftrightarrow 1 = 3m - 2k \\ \end{array}$$

We have

$3x\equiv1\mod 4$
$x\equiv1\mod 6$

Write $3x=4k+1$ and $x=6m+1$

hence we get

$2k-9m=1$

Solve this diophantine equation and you will get answer.