# 7^n-1 is divisible by 6

1. Jul 9, 2014

### jonroberts74

prove (induction) $$6|7^{n}-1; \forall n \ge 0$$

P(0)

$$6|7^0 -1$$

6|0

P(k)

$$6|7^k-1$$

what I want to show: $$6|7^{k+1}-1$$

I know I'll kick myself but this one isn't jumping out at me.

$$7 \cdot 7^k-1$$

maybe something with $$(6+1)^k(6+1)-1$$

2. Jul 9, 2014

### micromass

Staff Emeritus
You undoubtly know the formulas $x^2 - a^2 = (x-a)(x+a)$ and $x^3 - a^3 = (x-a)(a^2 + ax+ x^2)$. Do you know how it generalizes to $x^n - a^n$?

3. Jul 9, 2014

### jonroberts74

$$x^n−a^n=(x−a)(x^{n−1}+x^{n−2}a+x^{n−3}a^2+…+xa^{n−2}+a^{n−1})$$

so

replace x with 7 and a with 1??

Last edited: Jul 9, 2014
4. Jul 9, 2014

### micromass

Staff Emeritus
Yep!

5. Jul 9, 2014

### jonroberts74

$$7^{k+1}−1^{k+1}=(7−1)(x^{k}+7^{k−1}1+7^{k−2}1^2+…+(7)1^{k−1}+1^{k})$$

I had to alter it cause its k+1, correct?

6. Jul 9, 2014

### micromass

Staff Emeritus
Sure, this is correct. Notice that you don't really need induction for this!

7. Jul 9, 2014

### jonroberts74

thanks!

8. Jul 10, 2014

### HallsofIvy

Staff Emeritus
With induction you don't really need that long sum:
If $7^k- 1$ is a multiple of 6 then $7^k- 1= 6m$ for some integer m so that $7^k= 6m+ 1$.

$$7^{k+1}- 1= 7(7^k)- 1= 7(6m+1)- 1= 6(7m)+ 7- 1= 6(7m)+ 6= 6(7m+1)$$

Last edited: Jul 10, 2014
9. Jul 10, 2014

### Quesadilla

Yes. If you were told to use induction this seems to be more like what they wanted you to do.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted