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$$
 A: Notice that it's divisible iff $5$ and $7$ divide it. Look that 
$$4^{1536}-9^{4824}\equiv_5 (-1)^{1536}-(-1)^{4824}= 1-1=0$$
then for the $7$, look that:
$$4^{1536}-9^{4824}\equiv_7 (16)^{768}-(2)^{4824}\equiv_7 (9)^{768}-(8)^{1608}\equiv (2)^{768}-(1)^{1608}$$
But $1^{1608}=1$, and $2^{768}=8^{256}$, so
$$(2)^{768}-(1)^{1608}\equiv 8^{256}-1\equiv 1^{256}-1=0$$
For the case of division by $7$, I reduced the modules dividing by $2$ and trying to find a number congruent to $1$. If you use the little Fermat theorem, you could reduce the operations.
A: Euler's theorem implies, since $\varphi(35)=24$, that
$$4^{24}\equiv 9^{24}\equiv 1\pmod {35}$$
Since $1536$ and $4824$ are multiples of $24$, the conclusion follows:
$$4^{1536}-9^{4824}=(4^{24})^{64}-(9^{24})^{201}\equiv1^{64}-1^{201}\equiv 0\pmod{35}$$
A: Since $35=7*5$ and $5,7$ are prime, it suffices to show that that is divisible by both $5$ and $7$. To do this, note that $4\equiv 9\equiv -1$ mod $5$, so 
$$
4^{1536}-9^{4824}\equiv (-1)^{1536}-(-1)^{4824}\equiv 1-1\equiv 0\mod 5.
$$
To show divisibility by $7$ requires a bit more work; try to show that successive powers of an element eventually cycle mod $7$, and then you will be able to get a nice form for them.
A: 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$.
A: Hint 
$4^{1536}-9^{4824} 
=64^{512}-729^{1608}
=(7*9+1)^{512}-(7*104+1)^{1608}≡ 0 \mod 7$
