What's wrong with my modular arithmetic?

Question

$$x \equiv 3 \pmod{4}$$

Hence we know that $2x \equiv 6 \pmod{4}$. This implies that $2x \equiv 4l + 6$ for some $l$. Hence we can reduce that to $x = 2l + 3$ or $x \equiv 3 \pmod{2}$ Which doesn't make sense. Where's my mistake?

Answer 1

$6\pmod{2}\equiv 0$ not $3$.

And also $2*x\equiv 4*l\equiv 2*l\equiv 0\pmod{2}$. So your entire line reads $0\equiv 0\pmod {2}$, which is consistent.

It seems you have some misconception about $6\pmod{2}$ being more like division than modulo arithmetic.

Backing up, and skipping the step where you multiply everything by $2$, $x\equiv 3\pmod{4}$ would also imply $x\equiv 3\equiv 1\pmod{2}$.

Re: your comment

Where did the 6 (mod 2) congruent 0 come from?

$6=2*3$ is divisible by $2$, ergo it is $0\pmod 2$. That's what the modular equivalence relation says: $a\equiv b$ iff $2|a-b$, and when $b=0$ it's just divisibility.

Answer 2

The following theorem holds:

Let $m\in \mathbb N \ \backslash \ \{0\}$, for all $a\in \mathbb Z \ \backslash \{0\}$, $b_1,b_2\in \mathbb Z$ we have: $$ ab_1 \equiv ab_2 \pmod m \Longleftrightarrow b_1\equiv b_2 \pmod{\frac{m}{\text{gcd}(a,m)}} $$

So your first operation is legal but is not an equivalence.

In particular, if you multiply both sides of the congruence without multiply the module, then you lose information.

Hence you have: $$ x\equiv 3 \pmod 4 \Longrightarrow 2x\equiv 6 \pmod 4 $$

But the converse is not true according to the theorem.

Hence, not all $x\equiv 3\pmod 2$ satisfy the first congruence.

To multiply correctly by $2$ we have to write this equivalence (is the theorem in this specific case):

$$ 2 x \equiv 2 \cdot 3 \pmod 8 \Longleftrightarrow x\equiv 3 \pmod{\frac{8}{\text{gcd}(2,8)}} $$

In this way you don't lose infomation and you will not find "strange" things.

Thanks to Sil for the suggestion to point out the problem of my first answer.

Answer 3

If $ ax\equiv ay\; \text{(mod m)}$ and $ gcd(a,m)=1$, then $ x\equiv y\; \text{(mod m)} $.
If $ gcd(a,m)=d$ then $ ax\equiv ay\; \text{(mod m)}\iff x\equiv y\; (mod\;\dfrac md)$