Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

4 Answers

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|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
add comment

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|improve this answer
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. –  Jyrki Lahtonen Oct 18 '11 at 19:17
add comment

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.