k = 5m + 3n

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?

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?

NateTG

You got to:
[tex]k+1=5(x-1)+3(y+2)[/tex]
but, as you point out, you can't be sure that [itex](x-1)\geq 0[/itex].

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

NateTG

[tex]9=3 \times 3 + 5 \times 0[/tex]
Zero is a non-negative integer.

dextercioby

My solution Any natural number greater or equal to 8 is a member of this set

[tex] \left\{8, 9, 10, 11, 12, ...\right\} [/tex]. All elements of this set can be written as

[tex] 8+3k, 9+3k, 10+3k, \ k\in\left\{0,1,2,3,...\right\} [/tex]

But

[tex] 8+3k= 5\cdot 1+3\cdot p \ , \ p\in\left\{1,2,3,...\right\} [/tex] when

[tex] k=0\longrightarrow p=1 , \ k=1\longrightarrow p=2, \ ,... [/tex]

[tex] 9+3k= 5\cdot 0+3\cdot p' \ , \ p'\in\left\{3,4,5,...\right\} [/tex] when

[tex] k=0\longrightarrow p'=3 , \ k=1\longrightarrow p'=4, \ ,... [/tex]

[tex] 10+3k= 5\cdot 2+3\cdot p'' \ , \ p''\in\left\{0,1,2,...\right\} [/tex] when

[tex] k=0\longrightarrow p''=0 , \ k=1\longrightarrow p''=1, \ ,... [/tex]

So the problem is solved. Any element [itex] x\in\left\{8, 9, 10, 11, 12, ...\right\} [/itex] can be written as x=5m+3n, with [itex] m\in\left\{0,1,2\right\} [/itex] and [itex] n\in\mathbb{N} [/itex].

BTM, this is neither calculus, nor beyond

EDIT: I deleted that erroneous post Nate quoted above.

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.

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