# Prove that 7^n - 1 is divisible by 6

1. Aug 3, 2011

1. The problem statement, all variables and given/known data
Prove that 7^n - 1 is divisible by 6

2. Relevant equations

3. The attempt at a solution

I managed a solution were i use only the addition of 6^x were x is any postive 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.

2. Aug 3, 2011

### Bohrok

Can you find a pattern in the factorization of these

a2 - b2
a3 - b3
...

to factor this?

an - bn

3. Aug 3, 2011

a^2 - b^2 = (a+b)*(a-b) but thats 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.

grtz
Ivar

4. Aug 3, 2011

### Bohrok

a3 - b3 = a3 - a2b + a2b - ab2 + ab2 - b3

= a2(a - b) + ab(a - b) + b2(a - b)

= (a - b)(a2 + ab + b2)

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.

5. Aug 3, 2011

### SammyS

Staff Emeritus
For example: Multiply a5 + a4 b + a3 b2 + a2 b3 + a  b4 + b5 by (a - b).

What do you get?

Last edited: Aug 3, 2011
6. Aug 3, 2011

### jbunniii

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

7. Aug 3, 2011

### ArcanaNoir

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

8. Aug 3, 2011

### SammyS

Staff Emeritus
Yes, this is a good idea.

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

9. Aug 4, 2011

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

10. Aug 4, 2011

### Hurkyl

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

11. Aug 4, 2011

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 wich has as main goal learing how to solve problems and wich 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

Last edited: Aug 4, 2011
12. Aug 4, 2011

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

13. Aug 4, 2011

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?

Last edited: Aug 4, 2011
14. Aug 4, 2011

### 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$$

15. Aug 4, 2011

Sigma i'm not familiar enough with. I think i know what to do. I'm gonna 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 gonna let this one rest until i finished appendix E

thanks ye all so far.

grtz
Ivar

16. Aug 4, 2011

### SammyS

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

Last edited: Aug 4, 2011
17. Aug 4, 2011

### 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.

18. Aug 4, 2011

### Staff: Mentor

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

19. Aug 4, 2011

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

20. Aug 4, 2011

### 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.