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......
Can this be proved?
0
$\begingroup$
elementary-number-theory
-
1Fix any $n$, consider its residue modulo $3$.. – 2011-09-08
1 Answers
1
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 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$.
-
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$. – 2011-09-08