1
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ That... doesn't really answer the question. $\endgroup$ – 5xum Nov 26 '14 at 10:17
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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