Can you please help me and tell, how should I move on? Can this be proved by induction?
Every natural number $n\geq 8$ can be represented as $n=3k + 5\ell$.
Thank you in advance
Can you please help me and tell, how should I move on? Can this be proved by induction?
Every natural number $n\geq 8$ can be represented as $n=3k + 5\ell$.
Thank you in advance
We can avoid an explicit appeal to induction by using the fact that every natural number $n$ has remainder $0$, $1$, or $2$ on division by $3$. Let $n \ge 8$.
If $n$ has remainder $2$ on division by $3$, then $n-8$ is divisible by $3$, say $n-8=3m$. Represent $8$ using $8=3\cdot 1+5\cdot 1$. Then add $m$ $3$'s.
If $n$ has remainder $0$ on division by $3$, then $n-9$ is divisible by $3$, say $n-9=3m$. Represent $9$ using $9=3\cdot 3 +5\cdot 0$. Then add $m$ $3$'s.
If $n$ has remainder $1$ on division by $3$, then $n-10$ is divisible by $3$, say $n-10=3m$. Represent $10$ using $10=3\cdot 0 +5\cdot 2$. Then add $m$ $3$'s.
The argument for remainder $0$ was a little silly, since if $n$ has remainder $0$ on division by $3$, we can clearly use a bunch of $3$'s to represent $n$. But we wanted the solutions for the three cases to use a single template.
Clearly, $8$ can be represented as $3k+5\ell$, by taking $k=1$ and $\ell=1$.
Likewise, $9=3(3) + 5(0)$; and $10=3(0) + 5(2)$. So we can represent $8$, $9$, and $10$.
Now, assume that for $m\gt 10$, and you can represent all numbers strictly smaller than $m$ that are $8$ or larger (the induction hypothesis). To show that you can represent $m$, consider $m-3$ first.
Hint $\rm\quad n\ =\ 3\:\bigg(\!\!\dfrac{n-5\:k}{3}\!\bigg)\: +\ 5\:k\ \ $ for $\rm\ \ k\: = \ {-}n\:\ mod\:\ 3,\ \ k \in \{0,1,2\}$
Note $\ $ For the underlying geometric intuition see this post on the Frobenius problem.
Per request in the comments, here are some examples with further detail.
$\qquad\ \ \begin{eqnarray} \rm n =\ 8,\ \ \ k &=& -8&\equiv\ 1,\ &\ \ 8\ &=\ 3\ (\ 8&-&5\cdot 1)/3 + 5\cdot 1\ =\ 3\cdot 1 + 5\cdot 1 \\ \rm n =\ 9,\ \ \ k &=& -9&\equiv\ 0,&\ \ 9 &=\ 3\ (\ 9&-&5\cdot 0)/3 + 5\cdot 0\ =\ 3\cdot 3 + 5\cdot 0 \\ \rm n = 10,\ \ k &=& -10&\equiv\ 2,& 10 &=\ 3\ (10&-&5\cdot 2)/3 + 5\cdot 2\ =\ 3\cdot 0 + 5\cdot 2 \\ \end{eqnarray}$
Thus $\rm\ \ 3\:m + \ \ 8\ =\ 3\:m + 3\cdot 1 + 5\cdot 1\ =\ 3\:(m+1) + 5\cdot 1$
and $\rm\ \ \ \ 3\:m + \ \ 9\ =\ 3\:m + 3\cdot 3 + 5\cdot 0\ =\ 3\:(m+3) + 5\cdot 0$
and $\rm\ \ \ \ 3\:m + 10\ =\ 3\:m + 3\cdot 0 + 5\cdot 2\ =\ 3\:(m+0) + 5\cdot 2$
yields the desired representations for all integers $\ge 8\:.$