4
$\begingroup$

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.

4 Answers 4

3

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

  • 0
    No idea, sorry. Accepted it again, thanks a lot!2011-10-19
2

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

  • 2
    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.2011-10-18
1

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

  • 0
    @scro: This proves the statement since any integer must be congruent to either $0, 1$, or $2\bmod{3}$.2019-01-02
0

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