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!

Prove that 7^n - 1 is divisible by 6

  1. Aug 3, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove that 7^n - 1 is divisible by 6

    2. Relevant equations


    3. The attempt at a solution

    I managed a solution were i use only the addition of 6^x were x is any postive integer. The solution i have workes until n = 3 but not after that.

    7^n - 1 = 6^n + n*6^(n-1) + n*6^(n-2)......

    7^1 - 1 = 6 = 6^1
    7^2 - 1 = 48 = 6^2 + 2*6^1
    7^3 - 1 = 342 = 6^3 + 3*6^2 + 3*6^1

    I tried different other possibilities on this. I also thought about rewriting 7^n - 1 such that division by six is obvious but i couldn't think of a possibility. I'm guessing i need a totally different approach bu i don't know what approach.

    Anyone got a clue on were to look? Proving has to go by mathematical induction but that for later.
     
  2. jcsd
  3. Aug 3, 2011 #2
    Can you find a pattern in the factorization of these

    a2 - b2
    a3 - b3
    ...

    to factor this?

    an - bn
     
  4. Aug 3, 2011 #3
    a^2 - b^2 = (a+b)*(a-b) but thats af far a i come. Writing it in anything like (a+b)^n*(a-b)^n returns large qeues of powers but i couldn't figure it out to get a^3 - b^3 for a starter.

    Can you give me some more information?

    grtz
    Ivar
     
  5. Aug 3, 2011 #4
    a3 - b3 = a3 - a2b + a2b - ab2 + ab2 - b3

    = a2(a - b) + ab(a - b) + b2(a - b)

    = (a - b)(a2 + ab + b2)

    The middle terms I added in the first line are just adding zero really, but they let me factor the cubes nicely. This can be extended to larger exponents, and for any positive integer n, really. When b = 1 as in your problem, it'll fortunately be a little easier to write out some of the terms.
     
  6. Aug 3, 2011 #5

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    For example: Multiply a5 + a4 b + a3 b2 + a2 b3 + a  b4 + b5 by (a - b).

    What do you get?
     
    Last edited: Aug 3, 2011
  7. Aug 3, 2011 #6

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Suggestion: Consider writing 7^n as (1+6)^n.
     
  8. Aug 3, 2011 #7
    What do you mean "that for later"? Induction is the way to go.
     
  9. Aug 3, 2011 #8

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Yes, this is a good idea.

    Use the binomial expansion to expand (6 + 1)n.
     
  10. Aug 4, 2011 #9
    I mean that i first want to figure out the pattern. Induction comes after that
     
  11. Aug 4, 2011 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Have you learned modular arithmetic? This exercise is rather trivial if you have....
     
  12. Aug 4, 2011 #11
    No i haven't had that but figuring out it's pattern is not the only thing. In it's context you have to apply mathematical induction and that's the main goal of this an the coming 4 excercises. Is a reviewing chapter at the end of chapter one wich has as main goal learing how to solve problems and wich stragegies there are like:
    * recognize something familiar
    * recognize patterns
    * use analogy
    * introduce somthing extra
    * take cases (splitting it up in several cases)
    * establisch subgoals
    * indirect reasoning
    * mathematical induction

    This one seems to be a combination of recognizing something familiar, recognize patterns, use analogy and mathematical induction.

    with the comments i am coming in the right direction but i'm not there yet.

    grtz
    Ivar
     
    Last edited: Aug 4, 2011
  13. Aug 4, 2011 #12
    Hi ivar. The clearest and formal proof to this is through binomial expansion. Only until you have developed an intuition to the proof, then you can make other conclusive statement to it. Even for modular arithmetic, the fundamental proof comes from the binomial theorem
     
  14. Aug 4, 2011 #13
    I've done some calculating:

    (6+1)[itex]^{1}[/itex] = 6[itex]^{1}[/itex] + 6[itex]^{0}[/itex] [itex]\rightarrow[/itex] 7[itex]^{1}[/itex] - 1 = 6[itex]^{1}[/itex]

    (6+1)[itex]^{2}[/itex] = 6[itex]^{2}[/itex] + 2*6[itex]^{1}[/itex] + 6[itex]^{0}[/itex] [itex]\rightarrow[/itex] 7[itex]^{2}[/itex] - 1 = 6[itex]^{2}[/itex] + 2*6[itex]^{1}[/itex]

    (6+1)[itex]^{3}[/itex] = 6[itex]^{3}[/itex] + 3*6[itex]^{2}[/itex] +3*6[itex]^{1}[/itex] + 6[itex]^{0}[/itex] [itex]\rightarrow[/itex] 7[itex]^{2}[/itex] - 1 = 6[itex]^{3}[/itex] + 3*6[itex]^{2}[/itex] + 3*6[itex]^{1}[/itex]

    (6+1)[itex]^{4}[/itex] = 6[itex]^{4}[/itex] + 4*6[itex]^{3}[/itex] + 6*6[itex]^{2}[/itex] + 4*6[itex]^{1}[/itex] + 6[itex]^{0}[/itex] [itex]\rightarrow[/itex] 7[itex]^{3}[/itex] - 1 = 6[itex]^{4}[/itex] + 4*6[itex]^{3}[/itex] + 6*6[itex]^{2}[/itex] + 4*6[itex]^{1}[/itex]

    (6+1)[itex]^{5}[/itex] = 6[itex]^{5}[/itex] + 5*6[itex]^{4}[/itex] + 10*6[itex]^{3}[/itex] + 10*6[itex]^{2}[/itex] + 5*6[itex]^{1}[/itex] + 6[itex]^{0}[/itex] [itex]\rightarrow[/itex] 7[itex]^{5}[/itex] - 1 = 6[itex]^{4}[/itex] + 5*6[itex]^{4}[/itex] + 10*6[itex]^{3}[/itex] + 10*6[itex]^{2}[/itex] + 5*6[itex]^{1}[/itex]

    Any following (6+1)[itex]^{n}[/itex] can be deduced according to what is known as pascals triangle. What i guess from the comments is that by factoring i get a pattern formula. But considering that at (6+1)[itex]^{n}[/itex] the resulting expansion has n+1 parts i don't see a general formula appear.

    Am i in the right direction?
     
    Last edited: Aug 4, 2011
  15. Aug 4, 2011 #14
    Otherwise, you can write in summative notation:

    [tex]\left( 6+1\right) ^{n}[/tex]

    [tex]=\sum_{r=0}^{n}\left( _{r}^{n}\right) 6^{r}[/tex]

    [tex]=\sum_{r=1}^{n}\left( _{r}^{n}\right) 6^{r}+6^{0}[/tex]

    [tex]=\sum_{r=1}^{n}\left( _{r}^{n}\right) 6^{r}+1[/tex]

    [tex]=6K+1[/tex]
     
  16. Aug 4, 2011 #15
    Sigma i'm not familiar enough with. I think i know what to do. I'm gonna do appendix E with is about sigma notation. I think i'll be much more able to solve this after having done this appendix. I've already done App A,C,D and they were all necesarry for chapter 1.

    I'm gonna let this one rest until i finished appendix E

    thanks ye all so far.

    grtz
    Ivar
     
  17. Aug 4, 2011 #16

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    If you don't know the binomial expansion for (a + b)n, (in this case a = 6, b = 1), then go back and try what Bohrok & I suggested earlier, particularly in posts #4 & #5.
     
    Last edited: Aug 4, 2011
  18. Aug 4, 2011 #17
    Hint. Use congruences:

    [tex]
    7 \equiv 1 \, (\mathrm{mod} \, 6)
    [/tex]
    [tex]
    7^2 \equiv 1 \times 1 = 1 \, (\mathrm{mod} \, 6)
    [/tex]
    and so on. Then, just subtract a one from both sides.
     
  19. Aug 4, 2011 #18

    Mark44

    Staff: Mentor

    I don't follow what you're trying to do here.
    (6 + 1)1 = 7 [itex]\neq[/itex] 71 - 1
    (6 + 1)2 = 72 = 49 [itex]\neq[/itex] 72 - 1 = 48


     
  20. Aug 4, 2011 #19
    Okay for instance if you expand (6+1)^2 you get 6[itex]^{2}[/itex] + 2*6[itex]^{1}[/itex] + 1 (equal to 6[itex]^{0}[/itex]). The question was to prove that 7[itex]^{n}[/itex] - 1 is devisable by six so if al components are a multiplification of six this is proven for the particular instance.

    Now if (6+1)[itex]^{2}[/itex] = 6[itex]^{2}[/itex] + 2*6[itex]^{1}[/itex] + 1 then 7[itex]^{2}[/itex] - 1 = 6[itex]^{2}[/itex] + 2*6[itex]^{1}[/itex] + 1 - 1 = 6[itex]^{2}[/itex] + 2*6[itex]^{1}[/itex]. Am I making sense to you now?

    Forgive me my somtimes poor english for i'm dutch.

    grtz
    Ivar
     
  21. Aug 4, 2011 #20
    Hint:
    If [itex]x = 6 k + 1[/itex] and [itex]y = 6 l + 1[/itex], then:

    [tex]
    x y = (6 k + 1)(6 l + 1) = 6^{2} k l + 6 k + 6 l + 1 = 6(6 k l + k + l) + 1 = 6 m + 1
    [/tex]

    Then, use mathematcal induction.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove that 7^n - 1 is divisible by 6
  1. Proving divisibility (Replies: 1)

  2. Prove x^n < n! (Replies: 4)

Loading...