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.

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|improve this question
1  
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
1  
Fix any $n$, consider its residue modulo $3$.. –  anon Sep 8 '11 at 9:36

1 Answer 1

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|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
1  
@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

 
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.