General form of an integer

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.

• I think we need to keep in mind that this text (I have it right here in front of me) is meant to be an elementary and the very first text a student is ever supposed to have seen. I think having the student even remember that they learned the division algorithm and recognizing that it can apply IS the proof. You are done and you really don't actually need to do any more. – fleablood Feb 2 '18 at 20:35

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.

• This is very good. But in this particular text book, the division algorithm has already been proven and is available. And, by the way, the way the book proved the division algorithm is nowhere as good (nor as correct or formal) as you just did. – fleablood Feb 2 '18 at 20:32
• FWIW, the proof in the text is simply to list $.., b-3a, b-2a, b-a, b, b + a...$ (by assuming without question it exists and is exhaustive) and the "take the smallest non-negative value" (assuming without question such a unique smallest element exists) and assigning it to $r$.... So this is a very elementary text. We shouldn't really worry too hard about a proof. The text expects one to refer to The divisional algorithm and slowly and methodically state "If we let $a=3>0$ and $q$ be $k$, the $r$ must be either $0, 1,2$ so writing it out...$b = 3k + r$ and ..." It's very introductory. – fleablood Feb 2 '18 at 20:41

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$.

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

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\}.$$

• The reason for mentioning that $n\geq 3(-|n|)$ is that $S= \{ j\in \Bbb Z : -|n|\leq j<(|n|+1)\}$ is a finite set and $T= \{j\in S: 3j\leq n\}$ is a non-empty subset of $S.$ So $T$ is finite and non-empty so $T$ has a largest member, which is $k.$ – DanielWainfleet Feb 2 '18 at 20:30
• Very nice! But as far as the expectation of the student in this particular text, this is overkill and far too advanced. The text has already proven the division algorithm so the student merely needs to reference it and no more. The text's actual proof of the division algorithm, meanwhile, is far simpler and very naive compared to your excellent and sophisticated proof. – fleablood Feb 2 '18 at 20:47