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

[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?

[Mark44]

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?

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.

[Kaldanis]

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?

[eumyang]

Then I need to show that 5x + 6k+1 -1 is all divisible by 5... is that anywhere near right?
I think you only need to show that
6k+1 - 1 = 5y,
for some other natural number y.

[D H]

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.
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) ?

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

[SammyS]

Look at (a+1)(a^n-1)=a_{n+1}+a^n-a-1=a_{n+1}-1+a^n-1-(a-1)

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

[Mark44]

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
No, I don't think so. You aren't using the induction hypothesis; i.e., that 6k - 1 = 5m, for some integer m.


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

[epenguin]

It looks good to me.

Can be generalised.

[Mark44]

It looks good to me.

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

[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!

[epenguin]

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

Not an induction proof, but a proof I thought.

[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

[Mark44]

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.

[Kaldanis]

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

But is my way 100% wrong?

[Mark44]

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.

[epenguin]

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

But is my way 100% wrong?

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.

[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