How can I show that $4^{1536} - 9^{4824}$ can be divided by $35$ without remainder? How can I show that $4^{1536} - 9^{4824}$ can be divided by $35$ without remainder?
I'm not even sure how to begin solving this, any hints are welcomed!
$$(4^{1536} - 9^{4824}) \pmod{35} = 0$$

Note that, for increasing integer values of $n $, the value of $4^n \mod 35$ (let us call it $r_1$) shows a cyclic behaviour. In particular, for any $n \equiv k\mod 6$,  we have 
$$ k=0\rightarrow r_1 =1$$
$$ k=1\rightarrow r_1 =4$$
$$ k=2\rightarrow r_1 =16$$
$$ k=3\rightarrow r_1 =29$$
$$ k=4\rightarrow r_1 =11$$
$$ k=5\rightarrow r_1 =9$$
Similarly, considering increasing integer values of $n $, the value of $9^n \mod 35$ (let us call it $r_2$)   shows the following cyclic behaviour for any $n \equiv k\mod 6$. We have 
$$ k=0\rightarrow r_2 =1$$
$$ k=1\rightarrow r_2 =9$$
$$ k=2\rightarrow r_2 =11$$
$$ k=3\rightarrow r_2 =29$$
$$ k=4\rightarrow r_2 =16$$
$$ k=5\rightarrow r_2 =4$$
Now both $1536$ and $4824$ are $\equiv 0\mod 6$, so that both $4^{1536} $ and $9^{4824} $ are $\equiv 1 \mod 35$.
