An integer $n > 7$ has form $r + 3k,\ r \in \{8,9,10\}\ $ [remainder systems] I want to prove the following statement, related to a coins problem.
All integers greater than 7 can be expressed as 8 + 3k or 9 + 3k or 10 + 3k for some non-negative integer k.
I believe it can be done by strong induction, but I'm not quite ready to tackle that yet and am looking for a more elementary proof. I'm not sure how to approach it. It is obvious from investigating the integer number line, but I want something more formal.
$(\forall n \in \mathbb{N}), n > 7 \implies (n = 8 + 3k  \lor n = 9 + 3k \lor n = 10 +3k) $ for some $k \in Z_{\ge 0}$
Did I get the statement of the proposition right?
What would be a good way to proceed? Contradiction? Cases?
 A: You got the statement right. Now, let $r$ be the remainder of the division of $n$ by $3$. Then $n=3k+r$ for some $k\in\mathbb Z_+$ and $r\in\{0,1,2\}$. Actually, since $n>7$, $k$ is at least $2$, with $k\geqslant3$ if $n\geqslant9$. But then:


*

*if $r=2$, $n=3(k-2)+6+2=3(k-2)+8$;

*otherwise, $n=3(k-3)+9+r$, and $9+r$ is either $9$ or $10$.

A: More generally suppose $\!\bmod 3\!:\,\ \overbrace{ r_0 \equiv 0,\ r_1\equiv 1,\ r_2\equiv 2}^{\large\rm\ complete\ residue\ system},\ $ e.g. $\ r_j = 9,10,8\,$ in the OP.
If $\,n\div 3\,$ has remainder $\,j\,$ then $\, \color{#c00}{n\equiv j \equiv r_j}\pmod{\!3}\,$ for some $\,j \in \{0,1,2\}$
Therefore we conclude that  $\, n = r_j + 3k\,$ for an integer $\,k,\,$ and $\, k\ge 0\,$ if $\, n\ge \max\{r_i\}$
Remark $ $ The proof boils down to $\rm\color{#c00}{transitivity}$ of congruence (being an equivalence relation). Similarly the  complete system of residues (remainders) $\ 0,1,2,\ldots,m\!-\!1\pmod{\!m}\,$ can be replaced by any other set that contains a complete congruent set of residues $\,r_j \equiv j,\,$ and these can instead be used as the canonical (normal-form) residues (remainders). A common convenient choice is the (balanced) least magnitude remainders $\, 0, \pm1,\pm2, \ldots,\,$ e.g. $\,0,\pm1,\pm2,3\pmod{\!6}$
A: The division algorithm says that for any integer $n$ there then there is a unique integer $m$ and an unique $b = 0, 1,2$ so that  $n = 3m + b$.
In other words this says exactly: Any integer can be expressed as $3m + 0$ or $3m + 1$ or $3m + 2$.
Case 1:  $n = 3m$ for some $m$.  And if $n > 7$ then $n \ge 9$ so $m \ge 3$.  Let $k = m-3 \ge 0$.  Then $n = 3m = 3(m-3) + 9 = 3k + 9$.
Case 2:  $n = 3m + 1$ for some $m$.  And if $n > 7$ then $3m > 6$ and $m > 2$.  So $m \ge 3$.  Let $k = m-3 \ge 0$.  Then $n = 3m + 1 = 3(m-3) + 9 + 1 = 3k +10$.
Case 3: $n = 3m +2$ for some $m$.  And if $n > 7$ then $n \ge 8$ and $3m + 2 \ge 8$ so $m \ge 2$. Let $k = m-2 \ge 0$.  Then $n =3m + 2 = 3(m-2) + 6 + 2 = 3k +8$.
And we are done.  If $n$ is an integer greater than $7$ it falls into exactly one of those three cases.
A: Every integer $n$ is one of three things
$$n \equiv 0\mod 3$$
$$n \equiv 1 \mod 3$$
$$n \equiv 2 \mod 3$$
Take an integer $k$. If $t$ is $0 \mod 3$, then $t$ can be expressed as $9+3k$, because $$9+3k = 3(3+k) \equiv 0 \mod{3}$$
and, similarly,
$$8+3k = 2+6+3k = 2+3(2+k) \equiv 2 \mod{3}$$
$$10+3k = 1+9+3k = 1+3(3+k) \equiv 1 \mod{3}$$
A: Let n be any integer
n can be either represented as 3m-1, 3m or 3m+1, where m is an positive integer.
Assuming m=3+k, where k is an positive integer
n = 3(3+k)-1=8+3k
n=3(3+k)=9+3k
n=3(3+k)+1=10+3k
Now as k is a positive integer, n>7
Hence the statement is proved.
