# Proof: $2x \bmod 3 \neq 0$ if $x \bmod 3 \neq 0$

I'm not very fluent in mathematical proofs. High School has, sadly, not taught me any kind of proof-theory. That's why I would like your help with my proof of

$$2x \bmod 3 \neq 0$$

given that $$x \bmod 3 \neq 0$$

Actually it seems absolutely logical for me, but I have no idea how to tackle the modulo for proofing. $x \in \mathbb{Z}$, if that helps.

-

This might be more comprehensive: $x \mod 3 \neq 0 \Rightarrow x = 3k +q$ $(0 < q < 3)$ so we know $2x = 2(3k+q) = 6k+2q$. If we can show that 3 does not divide $2q$, then $2x \mod 3 \neq 0$. We know that $q$ equals $1$ or $2$ from our previous statement of $x$. If it equaled $1$ then $2q$ equals $2$. If it equaled $2$ then $2q$ equals $4$.

-
Might I ask why the answer isn't accepted anymore? Anything unclear? – user12205 Oct 18 '11 at 21:18
No idea, sorry. Accepted it again, thanks a lot! – scro Oct 19 '11 at 18:17

It suffices to show the contrapositive, that if $$2x \equiv 0 \pmod 3$$ then $$x \equiv 0 \pmod 3.$$ This is a special case of the fact that for any prime $p$, if $ab \equiv 0 \pmod p$ then either $a \equiv 0 \pmod p$ or $b \equiv 0 \pmod p$. (Which is another way of saying that if $p | ab$ then either $p | a$ or $p |b$.

-
I took the liberty to edit the TeX in your answer. Congruence (in elementary number theory) is gotten with '\equiv'. The symbol you used '\cong' means congruence in geometry. – Jyrki Lahtonen Oct 18 '11 at 19:17

If $x=1\mod 3$, then $2x=2\mod 3$.

If $x=2\mod 3$, then $2x=4=1\mod 3$.

In both cases, this is not equal to $0\mod 3$.

-
Thank you @Rasmus. What I still don't get is why this proves it. Is there a like a rule in module calculation I am not aware of? – scro Oct 18 '11 at 17:57
@scro: This proves the statement since any integer must be congruent to either $0, 1$, or $2\bmod{3}$. – JavaMan Oct 18 '11 at 19:19

HINT $\rm\ \ mod\ 3\!:\ \ 0\: \equiv\: 2\:x\ \Rightarrow\ 0\: \equiv\: 2\:(2\:x)\: \equiv\: x\:.\:$ Alternatively, $\rm\ 0\: \equiv\: 2\:x\:\equiv\: -x\ \Rightarrow\ x\:\equiv\:0\:.$

More generally, if $\rm\ ab = 1\$ then $\rm\ b\:x = 0\ \iff\ x = 0\$ follows by scaling both sides by $\rm\:a\:,\:$ i.e. scaling an equation by a unit (invertible) element yields an equivalent equation. In the above case note that $\rm\:2\:$ is a unit (invertible) since $\rm\: mod\ 3\!:\ 2\cdot 2 \equiv 1,\ \ or\ \ 2\:\equiv -1\:.$

-