Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
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$.

share|cite|improve this answer
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$.

share|cite|improve this answer
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\:.$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.