k = 5m + 3n

1. The problem statement, all variables and given/known data

Prove that for all integers x >= 8, x can be written in the form 3m + 5n, where m and n are non-negative integers.

2. Relevant equations

3. The attempt at a solution

Proof by induction on n that every integer n >= 8 can be expressed as n = 5x + 3y, with some integers x and y.

Let n = 8. Then n = 8 = 5(1) + 3(1), so the proposition is true for the base case.
Suppose the proposition is true for some number integer n = k > 8, i.e. k = 5x + 3y, for integers x and y. Consider the case when n = k + 1.

Then we have

k + 1 = 5x + 3y + 1
= 5x + 3y + 1 + 5 - 5
= 5x - 5 + 3y + 6
= 5(x - 1) + 3(y + 2).

Since the proposition is true for the base case and it being true for n = k implies
that it is true for n = k + 1, then n = 5x + 3y for some integers x and y.

I think that's almost it, but what about showing that m and n will never have to be negative?
 PhysOrg.com science news on PhysOrg.com >> King Richard III found in 'untidy lozenge-shaped grave'>> Google Drive sports new view and scan enhancements>> Researcher admits mistakes in stem cell study
 Recognitions: Homework Help Science Advisor 9 is 0*5+3*3. 0 and 3 are non-negative. But your induction step is flawed. It would say 10=(-1)*5+5*3, which is true enough, but -1 is not non-negative. Luckily your induction can only fail for numbers k that are divisible by 3. Can you think of an alternative argument for these cases?

Recognitions:
Homework Help
 Quote by antiemptyv I think that's almost it, but what about showing that m and n will never have to be negative?
You got to:
$$k+1=5(x-1)+3(y+2)$$
but, as you point out, you can't be sure that $(x-1)\geq 0$.

One way might be to split this into two cases - one where $x>0$ and one where $x=0$ (you'll have to take advantage of $k+1 \geq 9$ in this case).

Recognitions:
Homework Help
$$9=3 \times 3 + 5 \times 0$$
 Blog Entries: 9 Recognitions: Homework Help Science Advisor My solution Any natural number greater or equal to 8 is a member of this set $$\left\{8, 9, 10, 11, 12, ...\right\}$$. All elements of this set can be written as $$8+3k, 9+3k, 10+3k, \ k\in\left\{0,1,2,3,...\right\}$$ But $$8+3k= 5\cdot 1+3\cdot p \ , \ p\in\left\{1,2,3,...\right\}$$ when $$k=0\longrightarrow p=1 , \ k=1\longrightarrow p=2, \ ,...$$ $$9+3k= 5\cdot 0+3\cdot p' \ , \ p'\in\left\{3,4,5,...\right\}$$ when $$k=0\longrightarrow p'=3 , \ k=1\longrightarrow p'=4, \ ,...$$ $$10+3k= 5\cdot 2+3\cdot p'' \ , \ p''\in\left\{0,1,2,...\right\}$$ when $$k=0\longrightarrow p''=0 , \ k=1\longrightarrow p''=1, \ ,...$$ So the problem is solved. Any element $x\in\left\{8, 9, 10, 11, 12, ...\right\}$ can be written as x=5m+3n, with $m\in\left\{0,1,2\right\}$ and $n\in\mathbb{N}$. BTM, this is neither calculus, nor beyond EDIT: I deleted that erroneous post Nate quoted above.