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

[rg2004]

Homework Statement

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

Homework Equations

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

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 can't reduce it down to the assumption

 

[Tedjn]

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

 

[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

 

[Tedjn]

Ok. Then, suppose 3^6k = 35a+y. Then, 2^6k = 35b+y. (Why?) Substitute.

 

[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

 

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

 

[rg2004]

Regarding post #4:

i see that
3^6k = 35a+y
2^6k = 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
3^6k - 2^6k =35x that we must conclude from this that the remainders are the same in order for them to subtract to zero?

 

[Tedjn]

Exactly so. Otherwise, there would be a contradiction.

 

[rg2004]

Thank you!