3
$\begingroup$

Is there a solution for the congruence $4x \equiv 2 \pmod 6$ ? And how can I find inverse element for $4$, when I can not use Extended Euclidean algorithm, because $6$ and $4$ are divisible by $2$.

Thanks for the answers!

$\endgroup$
1
$\begingroup$

You could start by rewriting the congruence in equation form as follows

$$ 4x\equiv 2 \pmod 6 \iff 4x=2+6\cdot k $$

now you are dealing with a usual equation, here you can divide by $2$ to get

$$ 2x=1+3\cdot k \iff 2x\equiv 1\pmod 3\iff \ 2\cdot2x\equiv 2\cdot 1\pmod 3 $$

which means

$$ x\equiv 2\pmod 3. $$

But remember we needed a solution modulo $6$, so we need to check which numbers in the set $\{0,1,2,3,4,5 \}$ satisfies the above congruence an we easily find that $2$ and $5$ is congruent to $2$ modulo $3$ and these are our solutions.

$\endgroup$
1
  • $\begingroup$ Yes, in fact if you have $a\equiv b\pmod{n}$ and $d=\gcd(a,b,n)$ you can divide $a,b,n$ by $d$ to get $a'\equiv b'\pmod{n'}$ and keep equivalence in the way. $\endgroup$
    – zwim
    Mar 5 '19 at 0:54
0
$\begingroup$

$ 4x \equiv 2 \bmod 6 $ implies

  • $ 4x \equiv 2 \bmod 2 $, which does not give any information

  • $ 4x \equiv 2 \bmod 3 $, which reduces to $ x \equiv 2 \bmod 3 $

Conversely, every number of the form $x=3k+2$ is a solution of $ 4x \equiv 2 \bmod 6 $.

Therefore, $ 4x \equiv 2 \bmod 6 $ iff $x \equiv 2,5 \bmod 6 $.

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