Prove that 7^n - 1 is divisible by 6

[ialink]

Homework Statement

Prove that 7^n - 1 is divisible by 6

Homework Equations

The Attempt at a Solution

I managed a solution were i use only the addition of 6^x were x is any positive integer. The solution i have workes until n = 3 but not after that.

7^n - 1 = 6^n + n*6^(n-1) + n*6^(n-2)...

7^1 - 1 = 6 = 6^1
7^2 - 1 = 48 = 6^2 + 2*6^1
7^3 - 1 = 342 = 6^3 + 3*6^2 + 3*6^1

I tried different other possibilities on this. I also thought about rewriting 7^n - 1 such that division by six is obvious but i couldn't think of a possibility. I'm guessing i need a totally different approach bu i don't know what approach.

Anyone got a clue on were to look? Proving has to go by mathematical induction but that for later.

 

[Bohrok]

Can you find a pattern in the factorization of these

a² - b²
a³ - b³
...

to factor this?

aⁿ - bⁿ

 

[ialink]

a^2 - b^2 = (a+b)*(a-b) but that's af far a i come. Writing it in anything like (a+b)^n*(a-b)^n returns large qeues of powers but i couldn't figure it out to get a^3 - b^3 for a starter.

Can you give me some more information?

grtz
Ivar

 

[Bohrok]

a³ - b³ = a³ - a²b + a²b - ab² + ab² - b³

= a²(a - b) + ab(a - b) + b²(a - b)

= (a - b)(a² + ab + b²)

The middle terms I added in the first line are just adding zero really, but they let me factor the cubes nicely. This can be extended to larger exponents, and for any positive integer n, really. When b = 1 as in your problem, it'll fortunately be a little easier to write out some of the terms.

 

[SammyS]

For example: Multiply a⁵ + a⁴ b + a³ b² + a² b³ + a  b⁴ + b⁵ by (a - b).

What do you get?

 

[jbunniii]

Suggestion: Consider writing 7^n as (1+6)^n.

 

[ArcanaNoir]

Anyone got a clue on were to look? Proving has to go by mathematical induction but that for later.

What do you mean "that for later"? Induction is the way to go.

 

[SammyS]

Suggestion: Consider writing 7^n as (1+6)^n.

Yes, this is a good idea.

Use the binomial expansion to expand (6 + 1)ⁿ.

 

[ialink]

What do you mean "that for later"? Induction is the way to go.

I mean that i first want to figure out the pattern. Induction comes after that

 

[Hurkyl]

Have you learned modular arithmetic? This exercise is rather trivial if you have...

 

[ialink]

Have you learned modular arithmetic? This exercise is rather trivial if you have...

No i haven't had that but figuring out it's pattern is not the only thing. In it's context you have to apply mathematical induction and that's the main goal of this an the coming 4 excercises. Is a reviewing chapter at the end of chapter one which has as main goal learing how to solve problems and which stragegies there are like:
* recognize something familiar
* recognize patterns
* use analogy
* introduce somthing extra
* take cases (splitting it up in several cases)
* establisch subgoals
* indirect reasoning
* mathematical induction

This one seems to be a combination of recognizing something familiar, recognize patterns, use analogy and mathematical induction.

with the comments i am coming in the right direction but I'm not there yet.

grtz
Ivar

 

[icystrike]

Hi ivar. The clearest and formal proof to this is through binomial expansion. Only until you have developed an intuition to the proof, then you can make other conclusive statement to it. Even for modular arithmetic, the fundamental proof comes from the binomial theorem

 

[ialink]

Hi ivar. The clearest and formal proof to this is through binomial expansion. Only until you have developed an intuition to the proof, then you can make other conclusive statement to it. Even for modular arithmetic, the fundamental proof comes from the binomial theorem

I've done some calculating:

(6+1)$^{1}$ = 6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{1}$ - 1 = 6$^{1}$

(6+1)$^{2}$ = 6$^{2}$ + 2*6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{2}$ - 1 = 6$^{2}$ + 2*6$^{1}$

(6+1)$^{3}$ = 6$^{3}$ + 3*6$^{2}$ +3*6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{2}$ - 1 = 6$^{3}$ + 3*6$^{2}$ + 3*6$^{1}$

(6+1)$^{4}$ = 6$^{4}$ + 4*6$^{3}$ + 6*6$^{2}$ + 4*6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{3}$ - 1 = 6$^{4}$ + 4*6$^{3}$ + 6*6$^{2}$ + 4*6$^{1}$

(6+1)$^{5}$ = 6$^{5}$ + 5*6$^{4}$ + 10*6$^{3}$ + 10*6$^{2}$ + 5*6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{5}$ - 1 = 6$^{4}$ + 5*6$^{4}$ + 10*6$^{3}$ + 10*6$^{2}$ + 5*6$^{1}$

Any following (6+1)$^{n}$ can be deduced according to what is known as pascals triangle. What i guess from the comments is that by factoring i get a pattern formula. But considering that at (6+1)$^{n}$ the resulting expansion has n+1 parts i don't see a general formula appear.

Am i in the right direction?

 

[icystrike]

Otherwise, you can write in summative notation:

$$\left( 6+1\right) ^{n}$$

$$=\sum_{r=0}^{n}\left( _{r}^{n}\right) 6^{r}$$

$$=\sum_{r=1}^{n}\left( _{r}^{n}\right) 6^{r}+6^{0}$$

$$=\sum_{r=1}^{n}\left( _{r}^{n}\right) 6^{r}+1$$

$$=6K+1$$

 

[ialink]

Sigma I'm not familiar enough with. I think i know what to do. I'm going to do appendix E with is about sigma notation. I think i'll be much more able to solve this after having done this appendix. I've already done App A,C,D and they were all necesarry for chapter 1.

I'm going to let this one rest until i finished appendix E

thanks ye all so far.

grtz
Ivar

 

[SammyS]

If you don't know the binomial expansion for (a + b)ⁿ, (in this case a = 6, b = 1), then go back and try what Bohrok & I suggested earlier, particularly in posts #4 & #5.

 

[Dickfore]

Hint. Use congruences:

$$7 \equiv 1 \, (\mathrm{mod} \, 6)$$
$$7^2 \equiv 1 \times 1 = 1 \, (\mathrm{mod} \, 6)$$
and so on. Then, just subtract a one from both sides.

 

[Mark44]

I've done some calculating:

(6+1)$^{1}$ = 6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{1}$ - 1 = 6$^{1}$

(6+1)$^{2}$ = 6$^{2}$ + 2*6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{2}$ - 1 = 6$^{2}$ + 2*6$^{1}$

I don't follow what you're trying to do here.
(6 + 1)¹ = 7 $\neq$ 7¹ - 1
(6 + 1)² = 7² = 49 $\neq$ 7² - 1 = 48

(6+1)$^{3}$ = 6$^{3}$ + 3*6$^{2}$ +3*6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{2}$ - 1 = 6$^{3}$ + 3*6$^{2}$ + 3*6$^{1}$

(6+1)$^{4}$ = 6$^{4}$ + 4*6$^{3}$ + 6*6$^{2}$ + 4*6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{3}$ - 1 = 6$^{4}$ + 4*6$^{3}$ + 6*6$^{2}$ + 4*6$^{1}$

(6+1)$^{5}$ = 6$^{4}$ + 5*6$^{4}$ + 10*6$^{3}$ + 10*6$^{2}$ + 5*6$^{1}$ + 6$^{0}$ $\rightarrow$ 7$^{5}$ - 1 = 6$^{4}$ + 5*6$^{4}$ + 10*6$^{3}$ + 10*6$^{2}$ + 5*6$^{1}$

Any following (6+1)$^{n}$ can be deduced according to what is known as pascals triangle. What i guess from the comments is that by factoring i get a pattern formula. But considering that at (6+1)$^{n}$ the resulting expansion has n+1 parts i don't see a general formula appear.

Am i in the right direction?

 

[ialink]

I don't follow what you're trying to do here.
(6 + 1)¹ = 7 $\neq$ 7¹ - 1
(6 + 1)² = 7² = 49 $\neq$ 7² - 1 = 48

Okay for instance if you expand (6+1)^2 you get 6$^{2}$ + 2*6$^{1}$ + 1 (equal to 6$^{0}$). The question was to prove that 7$^{n}$ - 1 is devisable by six so if al components are a multiplification of six this is proven for the particular instance.

Now if (6+1)$^{2}$ = 6$^{2}$ + 2*6$^{1}$ + 1 then 7$^{2}$ - 1 = 6$^{2}$ + 2*6$^{1}$ + 1 - 1 = 6$^{2}$ + 2*6$^{1}$. Am I making sense to you now?

Forgive me my somtimes poor english for I'm dutch.

grtz
Ivar

 

[Dickfore]

Hint:
If $x = 6 k + 1$ and $y = 6 l + 1$, then:

$$x y = (6 k + 1)(6 l + 1) = 6^{2} k l + 6 k + 6 l + 1 = 6(6 k l + k + l) + 1 = 6 m + 1$$

Then, use mathematcal induction.