Divisibility problem cant use module just induction

  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. matt grime

    matt grime 9,395
    Science Advisor
    Homework Helper

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

    HallsofIvy 40,689
    Staff Emeritus
    Science Advisor

    The fact that 8= 5+ 3 is very useful here!
     
  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
     
    Last edited: Mar 18, 2007
  7. 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. 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. HallsofIvy

    HallsofIvy 40,689
    Staff Emeritus
    Science Advisor

    By George, I think he's got it!
     
  10. Thanks guys, I really appreciate it!!
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Divisibility problem cant use module just induction
Loading...