Is 7^n-1 Divisible by 6 for All Non-Negative Integers n? Prove with Induction

[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

 

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

 

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

 

[micromass]

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

Yep!

 

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

 

[micromass]

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?

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

 

[jonroberts74]

thanks!

 

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

 

[Quesadilla]

With induction you don't really need that long sum:
Is 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)

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