From the Division Algorithm, We know that if an integer is divided by $3$ , it will leave remainder $0,1$ or $2$. Now, how is one supposed to write a proper proof for the given question?
P.S. This is a problem from An Introduction to the Theory OF Numbers by Ivan Niven and H.S. Zuckerman.
Answer
You can rewrite any number (for instance $n$) in the format of $3k$, $3k+1$ or $3k+2$ if the division is by 3 and remainders are 0, 1 and 2.
Hint: We know from mathematical induction that if we prove $n+1$ is also in this format, for all numbers we have proven this to be true as n is an arbitrary number.
Assume: $n=3k$, then $n+1=3k+1$ and therefore the remainder is 1.
Assume: $n=3k+1$, then $n+1=3k+1+1=3k+2$ and therefore the remainder is 2.
Assume: $n=3k+2$, then $n+1=3k+2+1=3k+3=3(k+1)=3k'$ and therefore the remainder is 0.
No comments:
Post a Comment