Prove that every natural number takes one of three forms I am attempting a proof in real analysis, and I need to prove a preliminary result that any (infinite) sequence $\{x_n\}$ is composed entirely, or "partitioned" by the three subsequences $\{x_{3k}\}, \{x_{3k-1}\}$ and $\{x_{3k-2}\},$ where $n\in \mathbb N^+$, $k \in \mathbb N^+.$
I think that's equivalent to proving that any natural number can be expressed as one of the three forms: $3k$, $3k-1$, or $3k-2$, where $k \in \mathbb N^+$.
I know it's obvious but how can I go about proving it formally?
 A: The so-called division algorithm (also called Euclidean division) shows that any natural number $a$ can be written as
$$a=3q+r$$
with $q\in\mathbb Z$, $r\in\mathbb Z$, and $0\le r<3$.
It is obvious that the only integers between zero and three, not including three, are $0$, $1$, and $2$. The proof of this depends on the axioms you are using for the natural numbers or integers. If you need a proof of this, let us know which axioms you are using and we can show or direct you to a proof.
Since there are three possibilities for $r$, there are three possible equations:
$$a=3q+0$$
$$a=3q+1$$
$$a=3q+2$$
again, with $q\in\mathbb Z$. We can change these to
$$a=3q$$
$$a=3(q+1)-2$$
$$a=3(q+1)-1$$
It is easy to show that if $a$ is positive then the $q$ or $q+1$ in each line is also positive. Letting $k=q$ for the first line or $k=q+1$ for the other two lines, swapping the last two lines, and remembering that $\mathbb N^+$ is the set of positive members of $\mathbb Z$ gives the statement you wanted.

After finishing this proof, I realized that there is an easier proof. Use the division algorithm/Euclidean division on $-a$ to get
$$-a=3q+r$$
and so get
$$a=3(-q)-r$$
with $q,\ r\in\mathbb Z$ and $0\le r<3$. We know that $r=0,1,$ or $2$, and if $a>0$ you can easily show that $-q>0$ and thus $-q\in\mathbb N^+$. Some additional details are in my first proof above.
A: These are good answers, and I hesitate to add my two cents' worth, but I will do so anyway. A partition of a set is essentially the same thing as an equivalence relation (given one, you can induce the other so that the partition corresponds to equivalence classes). In this case, this is the equivalence relation (on $\Bbb N^+$):
$a \sim b \iff a - b = 3k$ for some INTEGER $k$ (this allows us to side-step the issue of which is larger, $a$ or $b$).
This partitions $\Bbb N^+$ into 3 (equivalence) classes, as the other posted answers indicate. These are often labelled $[0],[1],[2]$, to remind you of "remainders", but given that we are dealing with "positive" natural numbers, might better be labelled $[1],[2],[3]$.
It shouldn't be hard to see we have exactly 3 equivalence classes: for example, if $a \sim 3$, then $a$ is a multiple of $3$ (since $a - 3 = 3k \implies a = 3(k-1)$), so:
$[a] = [3] = \{3,6,9,\dots\}$
$1$ is not a multiple of $3$, so $[1] \neq [3]$, and in fact, $[1] = \{1,4,7,10,\dots\}$ which are all natural numbers of the form $3k+1$ (or if you prefer, $3n-2$).
Finally, $2$ is neither a multiple of $3$, nor $1$ more than any multiple of $3$, so we gain a third equivalence class:
$[2] = \{2,5,8,11,\dots\}$ of numbers of the form $3k + 2$ (or $3n-1$).
Since for any $a$, we have $a \sim a+3$, it follows that:
$[3] = [6] = [9] = \dots$
$[1] = [4] = [7] = \dots$
$[2] = [5] = [8] = \dots$, every 3rd integer goes in the same equivalence class.
A: If $f : X \rightarrow Y$ is surjective, then the relation on $X$ defined by "being in the same fiber of $f$" is a equivalence relation. Apply this to the canonical surjective map $\mathbf{Z}\to \mathbf{Z}/3\mathbf{Z}$ sending $x\in\mathbf{Z}$ to $x \textrm{ mod } 3$, and describe its fibers.
To put it simple : if you take an $x\in\mathbf{N}$ and do the euclidian division of $x$ by $3$, the reminder will be either $0$, $1$ or $2$. Let $ i\in\{0,1,2\}$. If the reminder of $x$ modulo 3 is $i$, then $x = 3k + i$ for a $k\in\mathbf{N}$ (the quotient of the division), so that you can conclude easily from here.
A: Let $\;n\in\Bbb N\;$ . If it is a multiple of $\;3\;$ then clearly $\;n=3k\;$ , for some $\;k\in\Bbb N\;$ . Otherwise, divide $\;n\;$ by $\;3\;$ with residue, and you'll get
$$n=3k+1\;,\;\;or\;\;n=3k+2$$
On the other hand, it's easy to check that $\;\{1,4,7,10,\ldots\}\;$ are the set of numbers of the form $\;3k+1\;$ , and $\;\{2,5,8,11,\ldots\}\;$ are the ones of the form $\;3k+2\;$. This, together with the mulitples of three give us all the natural numbers.
Another way: show that $\;1,2,3\;$ are the corresponding first three elements of three corresponding arithmetic progressions each with common different $\;d=3\;$ .
