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

Let n,k be such positive integers that $n\geq5$ and $k\geq2$ . How to prove next conjecture: $\forall n$ $\exists k$ ,such that n=3k-1 $\vee$ n=3k $\vee$ n=3k+1 .It is easy to see that for k=2 we get set {5,6,7} and for k=3,set {8,9,10} etc......

share|cite|improve this question
You don't really need constraints on n or k. It is true that for all integers $n$ there exists such an integer $k$; just let $k$ be the closest integer to $n/3$. – ShreevatsaR Sep 8 '11 at 9:33
Fix any $n$, consider its residue modulo $3$.. – anon Sep 8 '11 at 9:36
up vote 1 down vote accepted

What you want is the following claim on the integers: for every $n\ge 0 ,a\ge 1$ there are $k$ and $0\le r<a$ such that $n=ak+r$. This is called "the division algorithm" (or "division with remainder"). For $a=3$ you get what you want with the slight correction that if $n=3k+2$ you can also write $n=3(k+1)-1$.

So your question might be how that claim is proved. Fix $a$ and prove by induction on $n$: For $n=0,\dots,a-1$ you have $n=a\cdot 0 + n$; for general $n$ use the induction hypothesis on $n-a$ and write $n-a = ak+r$, so $n = a(k+1)+r$.

share|cite|improve this answer
you are right, but what to do with equation n=3k-1,here is r less then 0 and by the statement of division theorem must be bigger or equal to 0 – pedja Sep 8 '11 at 11:21
@pedja: Gadi has already answered your question. To rephrase his answer: you seem to know that given any $n$, it can be written as $n = 3q+r$ where $r$ is $0$, $1$, or $2$. If $r=0$ or $r=1$, you have your answer: just take $k=q$. Else, if $r=2$, then take $k=q+1$, so that $n = 3q+2 = 3(q+1)-1 = 3k-1$. – ShreevatsaR Sep 8 '11 at 11:31

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.