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

## Homework Statement

I am to prove that $$3^{6n}-2^{6n}$$ is divisible by 35 for all n$$n\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 cant reduce it down to the assumption

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

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

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

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

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.

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?

Exactly so. Otherwise, there would be a contradiction.

Thank you!