1. Not finding help here? Sign up for a free 30min 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 (6^n -1) is always divisible by 5

  1. Oct 17, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove that for all natural numbers n, [tex]6^n -1[/tex] is divisible by 5.


    2. Relevant equations
    3. The attempt at a solution

    I'm not sure how to go about proving this. I know that 6 to the power of any natural number ends in 6, therefor subtracting 1 will always make it end in a 5. This proves that it is divisible by 5. I asked my maths tutor and his reply was "I'm not sure how to go about that", then after a while he said try induction. If I try to prove it by induction I can't get past the base case without being lost.

    Does anyone have any tips or advice?
     
  2. jcsd
  3. Oct 17, 2011 #2

    Mark44

    Staff: Mentor

    For your induction hypothesis, let n = k, and assume that assume that 6k -1 is divisible by 5. What's another way to say this?

    Now, let n = k + 1, and use the induction hypothesis to show that 6k+1 - 1 is also divisible by 5.
     
  4. Oct 17, 2011 #3
    Hi Mark, I'm thinking like crazy, how about this?

    Since n = k and we're assuming 6k -1 is divisible by 5, I could declare that 6k -1 = 5x, where x is some natural number.

    Then I need to show that 5x + 6k+1 -1 is all divisible by 5... is that anywhere near right?
     
  5. Oct 17, 2011 #4

    eumyang

    User Avatar
    Homework Helper

    I think you only need to show that
    6k+1 - 1 = 5y,
    for some other natural number y.
     
  6. Oct 17, 2011 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    To prove some hypothesis by induction you need three things:
    • A mapping from the assertion to the natural numbers.
      In a sense you aren't trying to prove just one assertion: You are trying to prove an infinite number of them. Here, the nth assertion (call it Pn) is that 6n-1 is divisible by 5.

    • A base case for which you can prove the hypothesis to be true.
      Setting n to 1 yields P1, that 61-1 is divisible by 5. It's not too hard to prove this base case.

    • An induction step where you prove that if Pn is true then Pn+1 will also be true.
      In other words, you don't have to prove Pn. You assume it to be true. What you do have to do is prove that given this assumption then Pn+1 is necessarily true. In this case, you have to show that if 6n-1 is a multiple of 5 then so is 6n+1-1.

    And that is all you have to do. Once you have proven both the base case and the induction step, you have proven the hypothesis to be true.

    Regarding this problem, the base case is trivial. The induction step is a bit tougher, but not too tough.
    Hint: What is (6n+1-1) - (6n-1) ?
     
  7. Oct 17, 2011 #6

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    My suggestion is to express 6 in terms of 5 and then use the binomial theorem.

    As I have given this away you should go on and formulate a general theorem because 6 and 5 are of quite limited interest.
     
  8. Oct 17, 2011 #7

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Look at [itex](a+1)(a^n-1)=a_{n+1}+a^n-a-1[/itex]
    [itex]=a_{n+1}-1+a^n-1-(a-1)[/itex]​
     
  9. Oct 17, 2011 #8
    I haven't read the last 2 posts yet because I felt like I was close and wanted to get the final part on my own. I realised that for example, 65 is just 64*6, so how is this?

    6k+1 -1 = 6(6k) -1

    = (5+1)(6k) -1
    = 5(6k)+6k -1
    = 5(6k)+6(6k-1) -1
    = 5(6k)+(5+1)(6k-1) -1
    = 5(6k)+5(6k-1)+6k-1 -1
    = ... +5(62) +5(61) +6 -1

    Basically, following the same rule that 6k = 6(6k-1), you can continue back until you get to 61 which is 6.

    I'm not sure how clear that is, but is it 'acceptable' as a proof? I'll go and read the last few posts now :)
     
  10. Oct 17, 2011 #9

    Mark44

    Staff: Mentor

    No, I don't think so. You aren't using the induction hypothesis; i.e., that 6k - 1 = 5m, for some integer m.
     
  11. Oct 17, 2011 #10

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    It looks good to me.

    Can be generalised.
     
  12. Oct 17, 2011 #11

    Mark44

    Staff: Mentor

    "..." doesn't fly in an induction proof.
     
  13. Oct 17, 2011 #12
    Taking what I had further and carrying on from above:

    6k+1 -1 = 6(6k) -1

    = (5+1)(6k) -1
    = 5(6k)+6k -1
    = 5(6k)+6(6k-1) -1
    = 5(6k)+(5+1)(6k-1) -1
    = 5(6k)+5(6k-1)+6k-1 -1
    = ... +5(62) +5(61) +6 -1

    So it can be simplified to 5(6k + 6k-1 + 6k-2 + 6k-3 + ... + 62 + 61) + 6 -1.
    Let everything in the brackets = X, then...

    6k+1 -1 = 5X + 5!
     
  14. Oct 17, 2011 #13

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    Not an induction proof, but a proof I thought.
     
  15. Oct 17, 2011 #14
    I was really happy when I got what I wrote in the last post, but if it's wrong then I'm not sure how to write it without the "..." in there
     
  16. Oct 17, 2011 #15

    Mark44

    Staff: Mentor

    The induction hypothesis is that 6k - 1 = 5m for some integer m.
    If n = k + 1,
    6k+1 -1 = 6(6k) -1
    = 6(6k - 1) +6 - 1
    = 6*5m + 5
    = 5(6m + 1), which is clearly divisible by 5.
     
  17. Oct 17, 2011 #16
    Okay, you win. I really like your way of showing it!

    But is my way 100% wrong?
     
  18. Oct 17, 2011 #17

    Mark44

    Staff: Mentor

    No, it's not 100% wrong, but if your instructor is asking for an induction proof, then your way would be marked wrong, or at least would not get full credit. Pretty much any time you write "..." there's some other induction proof lurking about.
     
  19. Oct 17, 2011 #18

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    Not at all wrong IMO.

    But maybe the more proofs you have the better you understand and familarise even if one is sufficient.

    Binomial theorem as I mentioned is another. But now I just realised that 6n - 1 is just an example of difference of two n-th powers for which there is a standard formula.
     
    Last edited: Oct 17, 2011
  20. Oct 17, 2011 #19
    Thanks to everyone who helped, I was struggling with proving things like this but the steps here apply to quite a few other problems I have. I'm trying to get as much experience with these as possible
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove that (6^n -1) is always divisible by 5
  1. Prove Divisibility (Replies: 7)

Loading...