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

share|cite|improve this question
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
up vote 7 down vote accepted

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.

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

share|cite|improve this answer

Try the Division Algorithm.

Maybe this is overpowered for your purposes though.

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.