# 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

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

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

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

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 by a moderator: Jul 10, 2014
9. Jul 10, 2014