Why does the division algo imply any integer is of the form 3k, 3k+1, 3k+2?

Question

Know of this fact but not sure if I'm right in reasoning why it's true. Wondering why the division algo implies any integer is of the form $3k, 3k+1, 3k+2$ and likewise for $4k, 4k+1, 4k+2, 4k+3$.

The division algo says, let $a, b \in \mathbb{Z}$, then $\exists$ unique $q, r \in \mathbb{Z}$, s.t $a = bq+r, 0 \leq r < b$.

From what I understand we can conclude these two things because take an integer $n$. Either it is divisible by $3$ putting us in the first case, or it is congruent to $1\mod 3$, so we're in the second case with a remainder of $1$, or $2\mod 3$ giving us the last case.

And analogously for $4k, 4k+1, 4k+2, 4k+3$.

Is this correct?

Answer 1

To apply the division algorithm, for the case in your question, set $b=3$. Then for any integer $a$, there are unique integers $q,r$ such that $a=3q+r$ and $0\le r<3$. What are the possible values for $r$?

Answer 2

Because those are the only choices.

Let $n$ be an number. If you divide it by $3$ it will have a remainder. That remainder is either $0$, $1$ or $2$. That means $\frac n3 = q + \frac r3$ where $r = 0, 1$ or $2$.

So multiply both sides by $3$ and you get:

$3*\frac n3 = 3*(q + \frac r3)$ so

$n = 3q + r$ where $r = 0, 1$ or $2$.

======

Another way to think of it:

Either $n = 0$ or $n > 0$ or $n < 0$.

If $n = 0$ then $n = 3k$ where $k = 0$ and we are done.

If $n > 0$ then add $3$ and we have either $n > 3$ $n = 3$ or $n < 3$.

If $n = 3$ then $n = 3k$ where $k = 1$. If $n < 3$ then we have $0 < n < 3$ so $n = 1$ or $n = 2$ and so $n = 3k +1$ or $n =3k+2$ where $k = 0$.

If $n > 3$ then add another thre so that we have either $n > 6$ $n=6$ or $n < 6$.

We keep doing this until finally we come to $n > 3k$ but $n \le 3k + 3$.

If $n = 3k + 3 $ then $n = 3(k+1) + 0$.

If $n < 3k + 3$ then either $n = 3k +1$ or $n = 3k + 2$.

....

We do the same thing if $n < 0$ but we subtract $3$ until we get $n < 3(-k)$ but $n \ge 3(-k) - 3$.