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

Divisibility problem cant use module just induction

  1. Mar 18, 2007 #1
    Hi all,

    Great forum, I have been reading some cool stuff here for about a month.

    Heres my question:
    Using induction prove that 5 divides 8^n - 3^n, n Natural Number.

    I know its true for n = 1, but I get stuck on the n = k+1. I dont know how to proceed from here: 8(8^k) - 3(3^k)

    Also, I KNOW this is very easy using mod 5 but I can't do it here, I HAVE to prove it using only induction.

    Any hints?

    Thanks,

    -William
     
  2. jcsd
  3. Mar 18, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If 5 divides X and you show that 5 divides Y-X, does 5 divide Y?
     
  4. Mar 18, 2007 #3
    I think so, but how can I use that in my problem?
     
  5. Mar 18, 2007 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The fact that 8= 5+ 3 is very useful here!
     
  6. Mar 18, 2007 #5
    I think I've got it.

    Suppose that 5 divides 8^k - 3^k ---> 8^k - 3^k = 5x, for some integer x.

    case n = k +1
    = 8^k+1 - 3^k+1
    = 8(8^k) - 3(3^k)
    = 8(8^k) - (3^k)(8) + (3^k)(8) - (3)(3^k)
    = 8(8^k - 3^k) + 3^k(8 - 3)
    (1) (2)

    (1) by hypotesis 5 divides the expresion.
    (2) 5 = 8 - 3, 5 divides 5.

    = 8(5x) + 3^k(5)
    = 5(8x + 3^k)

    5 divides the expresion

    Please tell me its that way, if not, point the errors and some hints.

    Thanks, really.

    -William
     
    Last edited: Mar 18, 2007
  7. Mar 18, 2007 #6
    I think I've got it.

    Suppose that 5 divides 8^k - 3^k ---> 8^k - 3^k = 5x, for some integer x.

    case n = k +1
    = 8^k+1 - 3^k+1
    = 8(8^k) - 3(3^k)
    = 8(8^k) - (3^k)(8) + (3^k)(8) - (3)(3^k)
    = 8(8^k - 3^k) + 3^k(8 - 3)
    (1) (2)

    (1) by hypotesis 5 divides the expresion.
    (2) 5 = 8 - 3, 5 divides 5.

    = 8(5x) + 3^k(5)
    = 5(8x + 3^k)

    5 divides the expresion

    Please tell me its that way, if not, point the errors and some hints.

    Thanks, really.

    -William
     
  8. Mar 18, 2007 #7
    sorry for the double post.

    (1) = (8^k - 3^k)
    (2) = (8 - 3)

    (1) by hypotesis 5 divides the expresion.
    (2) 5 = 8 - 3, 5 divides 5.

    = 8(5x) + 3^k(5)
    = 5(8x + 3^k)

    5 divides the expresion
     
  9. Mar 19, 2007 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    By George, I think he's got it!
     
  10. Mar 19, 2007 #9
    Thanks guys, I really appreciate it!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Divisibility problem cant use module just induction
  1. Induction problem (Replies: 7)

  2. A module problem (Replies: 2)

  3. Divisibility problem (Replies: 1)

Loading...