# Homework Help: Proving that 3^(6n)-2^(6n) is divisible by 8 using induction

1. Jun 13, 2010

### rg2004

1. The problem statement, all variables and given/known data

I am to prove that $$3^{6n}-2^{6n}$$ is divisible by 35 for all n$$n\in\aleph$$ using induction.

2. Relevant equations

$$3^{6n}-2^{6n}=35x$$ where $$x\in\aleph$$ for all $$n\in\aleph$$ and

3. The attempt at a solution
Base:
$$3^{6(1)}-2^{6(1)}=35*x$$
$$665=35x$$
x=19
thus since 19 is an element of natural numbers the base case is true

Then I make this assumption
Assume:
$$3^{6k}-2^{6k}=35x$$

Inductive step:
$$3^{6(k+1)}-2^{6(k+1)}=35x$$
$$3^{6}3^{6k}-2^{6}2^{6k}=35x$$

and i don't know where to go from here, i've tried lots of things, but i cant reduce it down to the assumption

2. Jun 13, 2010

### Tedjn

Do you know this fact: a (mod n) × b (mod n) = ab (mod n)?

3. Jun 13, 2010

### rg2004

No i didn't know about that, and we haven't looked at modulus yet, so i'm not sure how to use it in this proof

4. Jun 13, 2010

### Tedjn

Ok. Then, suppose 36k = 35a+y. Then, 26k = 35b+y. (Why?) Substitute.

5. Jun 13, 2010

### rg2004

im assuming it looks like this:

$$3^{6}3^{6k}-2^{6}2^{6k}=35x$$

$$(3^{6} mod 35) (3^{6k} mod 35) - (2^{6} mod 35) (2^{6k} mod 35)=0$$

$$((29\cdot3^{6k}) mod 35) - ((29\cdot2^{6k}) mod 35)=0$$

$$29(3^{6k} mod 35 - 2^{6k} mod 35)=0$$

$$(3^{6k} mod 35 - 2^{6k} mod 35)=0$$

6. Jun 13, 2010

### Tedjn

That's right. You have to be careful when dividing both sides by the same thing in modular arithmetic, but it works out correctly this time. If you want to pursue this problem without explicitly using modular arithmetic, see my second post.

7. Jun 13, 2010

### rg2004

Regarding post #4:

i see that
36k = 35a+y
26k = 35b+y
since any number can be expressed as a linear combination like you showed, but what allows us to assume that the remainder , y, are equivalent? Is it because we assume
36k - 26k =35x that we must conclude from this that the remainders are the same in order for them to subtract to zero?

8. Jun 13, 2010

### Tedjn

Exactly so. Otherwise, there would be a contradiction.

9. Jun 13, 2010

Thank you!