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!

7^n-1 is divisible by 6

  1. Jul 9, 2014 #1
    prove (induction) [tex]6|7^{n}-1; \forall n \ge 0[/tex]






    P(0)

    [tex]6|7^0 -1[/tex]

    6|0

    P(k)


    [tex]6|7^k-1[/tex]


    what I want to show: [tex]6|7^{k+1}-1[/tex]




    I know I'll kick myself but this one isn't jumping out at me.

    [tex]7 \cdot 7^k-1[/tex]

    maybe something with [tex](6+1)^k(6+1)-1[/tex]
     
  2. jcsd
  3. Jul 9, 2014 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    You undoubtly know the formulas ##x^2 - a^2 = (x-a)(x+a)## and ##x^3 - a^3 = (x-a)(a^2 + ax+ x^2)##. Do you know how it generalizes to ##x^n - a^n##?
     
  4. Jul 9, 2014 #3
    [tex]x^n−a^n=(x−a)(x^{n−1}+x^{n−2}a+x^{n−3}a^2+…+xa^{n−2}+a^{n−1})[/tex]

    so

    replace x with 7 and a with 1??
     
    Last edited: Jul 9, 2014
  5. Jul 9, 2014 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yep!
     
  6. Jul 9, 2014 #5
    [tex]7^{k+1}−1^{k+1}=(7−1)(x^{k}+7^{k−1}1+7^{k−2}1^2+…+(7)1^{k−1}+1^{k})[/tex]

    I had to alter it cause its k+1, correct?
     
  7. Jul 9, 2014 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Sure, this is correct. Notice that you don't really need induction for this!
     
  8. Jul 9, 2014 #7
  9. Jul 10, 2014 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    With induction you don't really need that long sum:
    If [itex]7^k- 1[/itex] is a multiple of 6 then [itex]7^k- 1= 6m[/itex] for some integer m so that [itex]7^k= 6m+ 1[/itex].

    [tex]7^{k+1}- 1= 7(7^k)- 1= 7(6m+1)- 1= 6(7m)+ 7- 1= 6(7m)+ 6= 6(7m+1)[/tex]
     
    Last edited: Jul 10, 2014
  10. Jul 10, 2014 #9
    Yes. If you were told to use induction this seems to be more like what they wanted you to do.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted