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

[Kaldanis]

Homework Statement

Prove that for all natural numbers n, 6^n -1 is divisible by 5.

Homework Equations

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]

Homework Statement

Prove that for all natural numbers n, 6^n -1 is divisible by 5.

Homework Equations

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 6^k -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 6^k+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 6^k -1 is divisible by 5, I could declare that 6^k -1 = 5x, where x is some natural number.

Then I need to show that 5x + 6^k+1 -1 is all divisible by 5... is that anywhere near right?

 

[eumyang]

Then I need to show that 5x + 6^k+1 -1 is all divisible by 5... is that anywhere near right?

I think you only need to show that
6^k+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 n^th assertion (call it P_n) is that 6ⁿ-1 is divisible by 5.
• A base case for which you can prove the hypothesis to be true.
  Setting n to 1 yields P₁, that 6¹-1 is divisible by 5. It's not too hard to prove this base case.
• An induction step where you prove that if P_n is true then P_n+1 will also be true.
  In other words, you don't have to prove P_n. You assume it to be true. What you do have to do is prove that given this assumption then P_n+1 is necessarily true. In this case, you have to show that if 6ⁿ-1 is a multiple of 5 then so is 6ⁿ⁺¹-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 (6ⁿ⁺¹-1) - (6ⁿ-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 realized that for example, 6⁵ is just 6⁴*6, so how is this?

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

= (5+1)(6^k) -1
= 5(6^k)+6^k -1
= 5(6^k)+6(6^k-1) -1
= 5(6^k)+(5+1)(6^k-1) -1
= 5(6^k)+5(6^k-1)+6^k-1 -1
= ... +5(6²) +5(6¹) +6 -1

Basically, following the same rule that 6k = 6(6^k-1), you can continue back until you get to 6¹ 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 realized that for example, 6⁵ is just 6⁴*6, so how is this?

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

= (5+1)(6^k) -1
= 5(6^k)+6^k -1
= 5(6^k)+6(6^k-1) -1
= 5(6^k)+(5+1)(6^k-1) -1
= 5(6^k)+5(6^k-1)+6^k-1 -1
= ... +5(6²) +5(6¹) +6 -1

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

Basically, following the same rule that 6k = 6(6^k-1), you can continue back until you get to 6¹ 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:

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

= (5+1)(6^k) -1
= 5(6^k)+6^k -1
= 5(6^k)+6(6^k-1) -1
= 5(6^k)+(5+1)(6^k-1) -1
= 5(6^k)+5(6^k-1)+6^k-1 -1
= ... +5(6²) +5(6¹) +6 -1

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

6^k+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 6^k - 1 = 5m for some integer m.
If n = k + 1,
6^k+1 -1 = 6(6^k) -1
= 6(6^k - 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 realized that 6ⁿ - 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