An integer $n > 7$ has form $r + 3k,\ r \in \{8,9,10\}\ $ [remainder systems]

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.