1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: What's going on in this proof about integers?

  1. Jul 6, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove that for every integer n>=8, there exists nonnegative integers a and b, such that n =3a+5b

    2. Relevant equations

    3. The attempt at a solution
    I'm trying to understand the proof of this. It goes as follows:

    I am having a hard time figuring out what is going on in any of the three cases.

    Firstly, why did they pick 3q, 3q+1, and 3q+2?
    They could do this proof using n = 5q, 5q+1, 5q+2, 5q+3, 5q+4 also correct? It would just have more cases, and therefor, be more work?

    Then, about the cases.

    Case I: n = 3q
    I see what they did here. Since they picked to represent their integer as 3q, they supposed that b = 0, and then it's easy to show there exists an a, since a = q at that point. And a >=3 because n = 3q needs to be greater than 8.

    Case II: n = 3q+1
    Here is where I am troubled.
    How do they make the jump to claim that n = 3(q − 3) + 10 ??
    What is the thought process behind this?

    I would appreciate any explanation that you could provide. Thanks!
  2. jcsd
  3. Jul 6, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper

    n=3q+1, 3(q-3)+10=3q-9+10=3q+1=n. It's not as big a jump as you think.
  4. Jul 6, 2013 #3
    Ah I see. So they are still playing the make one side look like the other game. Thanks again!
  5. Jul 6, 2013 #4


    User Avatar
    Science Advisor
    Homework Helper

    That's a good way to phrase it. They are just splitting up into something divisible by 3 plus something divisible by 5.
  6. Jul 6, 2013 #5

    That "add 0 to an equation by adding some quantity x and then subtracting x again" thing always catches me off guard. I'm very familiar with that trick from various calc II integrals,

    but it still always hits me like a truck.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted