General form of an integer

Question

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 1

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.

Answer 2

I think the question is to prove that any integer n can only exist in one of the form out of $3k, 3k+1$ and $3k+2$. On contrary we assume that an integer $n=3s=3t+1$ (where s, t are integers i.e. it is of both form $3k$ and $3k+1$) $\implies 3(s-t) = 1 \implies 3\mid 1$ which is not possible. Hence n cannot be of both form $3k$ and $3k+1$. Similarly $n=3s+1=3t+2 \implies 3\mid 1$ and $n=3s=3t+2 \implies 3\mid 2$ which are not possible. Hence every integer is of the form $3k$ or of the form $3k+1$ or of the form $3k+2$.

Answer 3

Let $k$ be the largest integer such that $3k\leq n.$ We know $k$ exists because $3(|n|+1)>n\geq 3(-|n|)$ so $k$ is the largest $j\in \Bbb Z$ that satisfies both $-|n|\leq j< (|n|+1)$ and $3j\leq n.$

So $3k\leq n<3(k+1).$ Therefore $$n\in \{z\in \Bbb Z: 3k\leq z<3(k+1)\}=$$ $$= \{3k,3k+1, 3k+2\}. $$

Answer 4

"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?"

By saying ""From the Division Algorithm, We know that if an integer is divided by 3 , it will leave remainder 0,1 or 2". ....

Formal proof: By the division algorithm, for any integer $n$ then are unique $q,r$ such that $n = 3q + r; 0\le r < 3$.

$r$ must equal either $0, 1$ are $2$ as these are the only possible integers between $0$ (inclusively) and $3$ (exclusively). And so $n = 3q$ or $3q+1$ or $3q+2$ and thus is of form either $3k$ or $3k+1$ or $3k+2$.

---

I really think this was meant to be an easy exercise solely for the purpose of getting the student used to intuitively understanding that division algorithm is there and that the these results are immediately and obvious.

Frankly, I'd accept. "This follows immediately from the division algorithm as applied to the positive integer $3$" as an acceptable "proof".

I'd even accept: "(This follows from/ this is equivalent to/This is just) the division algorithm" (even though those aren't technically true-- I'd add a note that "This statement only states a result about the positive integer $3$ whereas the division algorithm applies to any positive integer, so these are actually equivalent" but then I'd give full credit.)

....

So... as far as I am concerned you just did a proof.