3
$\begingroup$

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

  • 0
    Welcome to math.SE. Please note that [linear algebra] is a particular discipline that deals with vectors, vector spaces, linear transformations, and matrices; it is an inappropriate tag for both questions you have asked so far.2011-10-14
  • 0
    Are $k$ and $l$ natural numbers?And have you tried to see if this is true for $n=9$?2011-10-14
  • 2
    @smanoos: Remember that "naturals" often include $0$.2011-10-14
  • 1
    We need to be slightly more specific. The assertion should be that every natural number $n \ge 8$ can be represented as $n=3k+5l$, where $k$ and $l$ are non-negative integers. Check for $8$, $9$, $10$. Now is it clear? Yes, we can use induction, but you can do it without mentioning induction explicitly.2011-10-14
  • 3
    This is one case of the Frobenius coin problem. A discussion is at http://en.wikipedia.org/wiki/Coin_problem2011-10-14
  • 0
    Is this not [an exact duplicate?](http://math.stackexchange.com/q/69961/11619)2011-10-15
  • 0
    Same: http://math.stackexchange.com/questions/11812222015-04-12

3 Answers 3

3

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.

  • 0
    More explicitly, see my answer, which unifies the cases.2011-10-14
  • 3
    @Bill Dubuque: We have opposite tendencies. I use $100$ words when $50$ will do.2011-10-14
  • 0
    But "Words" describing separate cases often obscure the general structure exhibited by a *universal* formula.2011-10-14
  • 0
    @André Nicolas, thank you for detailed answer - exactly the way, I need :) Please, can you tell, what are we doing here in general words? The principle?2011-10-15
  • 0
    We are finding non-negative solutions of linear diophantine equations. In general, if $a$ and $b$ are relatively prime positive integers, for any $n > ab-a-b$ there are non-negative integers $x$, $y$ such that $ax+by=n$.2011-10-15
8

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.

  • 0
    I think you mean $3(3)$ and not $3(2)$.2011-10-14
  • 0
    @smanoos: why, yes, I did! Thank you. (-:2011-10-14
  • 0
    Thank you for response! I have some questions. By k>10 you mean some n'>10? What do you mean "To show that you can represent k, consider k−3 first"? IS looks like: n'+1 = 3k+5l, but I cannot move from this point.2011-10-14
  • 0
    @Lissa: What you call the number on which you are doing induction does not matter. I like to call it "$k$"; if you want to call it "$n'$", I don't think the number is likely to object. Note that I am **not** doing regular induction ("assume it's true for $k$, show it is true for $k+1$"), I am using so-called **strong** induction ("assume it is true for every number strictly smaller than $k$, show it is true for $k$").(cont)2011-10-14
  • 0
    @Lissa: (cont) See [here](http://math.stackexchange.com/questions/25914/proof-by-strong-induction/25919#25919), and [here](http://math.stackexchange.com/questions/14984/what-is-the-second-principle-of-finite-induction/14987#14987). The induction hypothesis, which I stated explicitly, is that every number less than $k$ (and greater than or equal to $8$) can be represented. We need to prove that $k$ can be represented. Now, if $k\gt 10$, then $k-3$ is a number that is smaller than $k$; and greater than or equal to $8$. So our induction hypothesis says that we can represent $k+3$. Go from there?2011-10-14
  • 0
    @Arturo I think the issue here was that $k$ already has a meaning in the context of this problem.2011-10-14
  • 0
    @MartianInvader: Oh, sigh. Quite right.2011-10-14
5

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

  • 0
    Thank you for the response! I'm really beginner in "real" math,that's why I have to ask you some more questions. Could you please explain, what does the last part mean: k∈{0,1,2}, k≡−n(mod3). I've just read about congruence relation in wikipedia, but didn't understand, why -8 and 7 are congruent mod 5 (-8/5 rest -3; 7/5 rest 2 O_o). And in your hint k and -n are congruent mod 3. Could you please give me some more explanation.2011-10-14
  • 0
    @Lissa I've added some examples in the answer.2011-10-17