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

| cite | improve this answer | |
$\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$ ...

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\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'$.

| cite | improve this answer | |
$\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} $$

| cite | improve this answer | |
$\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.

| cite | improve this 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.