1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?