multiplying and dividing in congruence

720 Views Asked by At

$$x\equiv2\ (\text{mod }6)$$

This one has solution x=2, 8, 14, ...

By multiplying 2 to both sides,

$$2x\equiv4\ (\text{mod }6)$$

By dividing by $2$, $x\equiv 2\ (\text{mod } 3)$ (because $\text{gcd}(2, 6)=2$)

And the solution for this congruence is x=2, 5, 8, ...

What's wrong with this calculation?

1

There are 1 best solutions below

5
On BEST ANSWER

Note that $$x \equiv y\ (\text{mod }m) \implies ax \equiv ay\ (\text{mod }m)$$ This means that any solution of $x \equiv y\ (\text{mod }m)$ is also a solution of $ax \equiv ay\ (\text{mod }m)$. But, the implication doesn't go both ways, i.e. a solution of $ax \equiv ay\ (\text{mod }m)$ isn't necessarily a solution of $x \equiv y\ (\text{mod }m)$ as well. That is why, in your approach, you got more solutions than the correct answer.