# Homework Help: K = 5m + 3n

1. Aug 30, 2007

### antiemptyv

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?

Last edited: Aug 30, 2007
2. Aug 30, 2007

### Dick

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?

Last edited: Aug 30, 2007
3. Aug 30, 2007

### NateTG

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

4. Aug 30, 2007

### NateTG

$$9=3 \times 3 + 5 \times 0$$
Zero is a non-negative integer.

5. Aug 30, 2007

### dextercioby

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.

Last edited: Aug 30, 2007
6. Aug 30, 2007

### Dick

Alternatively, the cases that fail your inductive step are k=3*n for n>=3. In this case k+1=3*(n-3)+3*3+1=3*(n-3)+2*5.

Last edited: Aug 30, 2007
7. Aug 30, 2007

### uiulic

My method isthe same as dextercioby. But I organize it in another way, which maybe look simpler.

1 n=8,obvious
So we can start from 9, let k=3n,3n+1,3n+2, n>=3
2 k=3n, obvious
3 k=3n+1=3(n-3)+10,obvious
4 k=3n+2=3(n-1)+5,obvious

From 1,2,3,4, the conclusion is obvious