Is $x^y$ - $a^b$ divisible by $z$, where $y$ is large? The exact problem I'm looking at is:
Is $4^{1536} - 9^{4824}$ divisible by $35$?
But in general, how do you determine divisibility if the exponents are large?

$$4^{1536} \equiv 256^{389} \equiv 11^{389} \equiv 11*{14641}^{97}
\equiv 11*11^{97} \equiv 121^{49} \equiv 121* 14641^{24} \equiv 16* 11^{12}
\equiv 16*14641^3 = 16*11^3 \equiv 16*1331 \equiv 16.  $$
I use $\equiv$ to denote equivalence mod 35.  Just keep tossing out 35s.  YOu can do this on the other piece too and compare.
