Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: K = 5m + 3n

  1. Aug 30, 2007 #1
    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. jcsd
  3. Aug 30, 2007 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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
  4. Aug 30, 2007 #3

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  5. Aug 30, 2007 #4

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    [tex]9=3 \times 3 + 5 \times 0[/tex]
    Zero is a non-negative integer.
     
  6. Aug 30, 2007 #5

    dextercioby

    User Avatar
    Science Advisor
    Homework Helper

    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 :wink:

    EDIT: I deleted that erroneous post Nate quoted above.
     
    Last edited: Aug 30, 2007
  7. Aug 30, 2007 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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
  8. Aug 30, 2007 #7
    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
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook