# Prove that (6^n -1) is always divisible by 5

1. Oct 17, 2011

### Kaldanis

1. The problem statement, all variables and given/known data
Prove that for all natural numbers n, $$6^n -1$$ 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. Oct 17, 2011

### 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.

3. Oct 17, 2011

### Kaldanis

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?

4. Oct 17, 2011

### eumyang

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

5. Oct 17, 2011

### D H

Staff Emeritus
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) ?

6. Oct 17, 2011

### epenguin

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.

7. Oct 17, 2011

### SammyS

Staff Emeritus
Look at $(a+1)(a^n-1)=a_{n+1}+a^n-a-1$
$=a_{n+1}-1+a^n-1-(a-1)$​

8. Oct 17, 2011

### Kaldanis

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 :)

9. Oct 17, 2011

### 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.

10. Oct 17, 2011

### epenguin

It looks good to me.

Can be generalised.

11. Oct 17, 2011

### Staff: Mentor

"..." doesn't fly in an induction proof.

12. Oct 17, 2011

### Kaldanis

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!

13. Oct 17, 2011

### epenguin

Not an induction proof, but a proof I thought.

14. Oct 17, 2011

### Kaldanis

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

15. Oct 17, 2011

### 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.

16. Oct 17, 2011

### Kaldanis

Okay, you win. I really like your way of showing it!

But is my way 100% wrong?

17. Oct 17, 2011

### 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.

18. Oct 17, 2011

### epenguin

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
19. Oct 17, 2011

### Kaldanis

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