# How can I prove that a number n is either of the form 3k+1 or 3k+2, or 3k

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.

-
What went wrong when you tried induction? Say you know that n is of one of these forms. What, in each case, can you conclude regarding n+1? –  Alon Amit Feb 2 '11 at 4:08
Hint: What remainders can you get by dividing by three? –  Fredrik Meyer Feb 2 '11 at 4:17
Look at $\mathbb{Z}_3$. –  PEV Feb 2 '11 at 4:23
By 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. –  Bill Dubuque Feb 2 '11 at 4:38

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.

-
Yes definitely a better idea than summoning the Div alg. –  AnonymousCoward Feb 2 '11 at 4:59
Would you edit this answer to solve this for the negative answers as well. I finally solved this on my own with a similar approach, that I will post here. When you do that, I'll mark this as correct. –  Varun Madiath Feb 2 '11 at 5:00
Thats a great answer. –  Varun Madiath Feb 2 '11 at 14:14

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.

-