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$2 Answers
$\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$$ 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$
