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: Proof by induction

  1. May 9, 2010 #1
    Use the method of induction to prove that if a ∈ Z is a prime
    integer and if a/b1b2...br then a/bi for some 1 ≤ i ≤ r

    I could prove this in other ways but how do you do this by induction?

    I'm only use to induction of the form 'assume true for n show (n+1) also holds true'

    Could someone start me of? Thanks
     
  2. jcsd
  3. May 9, 2010 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Firepanda! :smile:

    Start "assume it's true for r ≤ n", and then try to prove it for r = n+1. :wink:
     
  4. May 9, 2010 #3
    ok so..

    a/b1b2...br then a/bi for some 1 ≤ i ≤ r

    assume true for r ≤ n

    a/b1b2...bn then a/bi for some 1 ≤ i ≤ n

    if r = n+1

    a/b1b2...bnbn+1 then a/bi for some 1 ≤ i ≤ n+1

    but since we already had 1 ≤ i ≤ n then surely this is true?

    Probably wrong
     
  5. May 9, 2010 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    No, if a divides a product of n+1 numbers, how can a theorem about products of n numbers be applied? :confused:
     
  6. May 9, 2010 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Work backwards. There are three cases:
    • a|b1 and a|b2b3...br (game over), or
    • a|b1 (game over), or
    • a|b2b3...br.
    In the last case, recurse.

    I don't think tiny-tim's idea will work because there is no base case to make the stack of dominos fall.
     
  7. May 9, 2010 #6
    if a|bc and gcd(a,b) = 1 since a is prime and b certainly isn't as its a product

    then a|c, so since a|c then a|bn+1, and 1 ≤ i ≤ n+1 so this holds true?

    ^ sorry this is wrong gcd(a,b) isnt 1 its bi

    im stumped
     
  8. May 9, 2010 #7

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Conceptually, there are four cases:
    1. a divides b1 and b2b3...br.
    2. a divides b1 but not b2b3...br.
    3. a divides b2b3...br but not b1
    4. a divides neither b1 nor b2b3...br.
    You need to show that these are the only four cases, and that case (4) does not apply.
     
  9. May 9, 2010 #8

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    I was thinking of saying a|bbn+1 where b = b1…bn :wink:
     
  10. May 9, 2010 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    So what is the base case? You do not know that a|b1.

    You have proved that if a|b2b3...br then a|b2b3...brbr+1. The OP needs to prove the converse (assuming a does not divide br+1; it's game over if a|br+1).
     
  11. May 9, 2010 #10

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    No, if a|bbn+1, then … :wink:
     
  12. May 9, 2010 #11
    go on... wanna see how you've done it!
     
  13. May 9, 2010 #12

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Apply the induction … a divides the product of two numbers, so … ?
     
  14. May 9, 2010 #13
    a|b or a|bn+1?
     
  15. May 9, 2010 #14

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    That's right. :smile:

    Now carry on … ​
     
  16. May 9, 2010 #15
    dont we just conclude that i is certainly contained between 1 and n+1 inclusive so the induction hypothesis is true?
     
  17. May 9, 2010 #16

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    "i is certainly contained …"

    That's meaningless!

    What are you talking about? What is i?

    (You're trying to find an i ≤ 1+1 such that a|bi, you haven't been given an i)
     
  18. May 9, 2010 #17
    but we assumed it was true?

    ok then but we've shown a must divide one of the terms so a can divide at least one of the i ≤ n+1
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook