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
    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
    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
    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
    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 by a moderator: 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