I've thought about trying to prove this by induction, and by contradiction, but I can't seem to phrase this in a formal way. Any help would be appreciated.
How can I prove that a number n is either of the form 3k+1 or 3k+2, or 3k
-
0By descent: if $\rm\:n\:$ is not of that form, then so too is $\rm\ n-3\:,\ $ so iterating yields an infinite descending chain of naturals not of that form, a contradiction. – 2011-02-02
3 Answers
I wasn't going to say anything, but all these comments may be overly confusing. No need for Division Algorithm. If you're proving this fact it is probably leading up to the Div Alg and shouldn't be used to prove this.
No need for $\mathbb{Z}_3$. This probably hasn't been defined yet, or the eventual use of this fact you're proving will be related to that later.
No need for contradiction (though there isn't anything wrong with how Bill Dubuque says to prove it, I'm just suggesting sticking with your gut instinct of induction).
Go back to the induction idea like Alon Amit says. If $n=3k+l$ where $l$ is 0, 1, or 2, then $n+1=3k+l+1$. You now have two cases. If $l=0$ or 1, then $(l+1)$ is 1 or 2, so $n+1=3k+(l+1)$ which is the right form. If $l=2$, then $n+1=3k+3=3(k+1)$, which is of the right form. So if you have the base case you have the positive integers by induction.
Let $n$ be any negative number. Then $-n$ is positive, so $-n=3k+l$ where $l$ is 0,1, or 2. Thus $n=-(3k+l)=3(-k)-l=3(-k)-l+3-3=3(-k-1)+(3-l)$ and $3-l$ is 0,1, or 2.
-
0Thats a great answer. – 2011-02-02
HINT $\rm\ \ 3\:\mathbb N\cup\:(3\:\mathbb N+1)\cup (3\:\mathbb N+2)\ =\ \mathbb N\ $ since it contains $\:0\:$ and it is closed under $\rm\:n\to n+1\:$.
Try the Division Algorithm.
http://en.wikipedia.org/wiki/Division_algorithm
Maybe this is overpowered for your purposes though.