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?
 A: Use Fermat's little theorem, which says that, for prime $p$,
$$a^{p-1}\equiv 1\mod p$$
for $a\in\mathbb{Z}$, $a$ not a multiple of $p$. In particular, your combination is easily shown to be zero both mod $5$ (because $4\mid 1536$ and $4\mid 4824$) and mod $7$ (because $6\mid 1536$ and $6\mid 4824$), so it is divisible by both $5$ and $7$ and hence divisible by $35$.
A: Hint $\ $ It is a very special case of either of the following theorems.
Theorem $\rm\  lcm(m,n)\:|\: a^j - b^k\ $ if $\rm\,(ab,mn)=1\,$ and $\rm\ \phi(m),\phi(n)\:|\:j,k,\ $ with $\,\phi = $  Euler totient
Proof $\rm\ \ mod\ n\!:\ a^j-b^k = (a^{\phi(n)})^{\,j/\phi(n)}\!-(b^{\phi(n)})^{k/\phi(n)}\equiv 1^{j/\phi(n)}\!-1^{k/\phi(n)}\equiv 0;\ $ similarly mod $\rm\,m.\:$ Therefore $\rm\:m,n\:|\:a^j-b^k\:\Rightarrow\:lcm(m,n)\:|\:a^j-b^k\ \ $ QED
Theorem $\ \ \rm  35\ |\ a = (5j\!-\!1)^{6m} \!- (5k\!-\!1)^{6n}\ $ if $\rm\,\ j,k\not\equiv 3\pmod 7$
Proof $\rm\ \ mod\ 5\!:\ a \equiv (-1)^{6m} - (-1)^{6n} \equiv 1 - 1\equiv 0$  
$\rm mod\ 7\!:\ 5x\equiv 1\iff x\equiv \frac{1}5 \equiv \frac{-6}{-2}\equiv 3,\:$ so $\rm\:j,k\not\equiv 3\Rightarrow5j\!-\!1,\ 5k\!-\!1 \not\equiv 0,\:$ so by little Fermat
$$\rm\:x\not\equiv 0\:\Rightarrow\:x^6\equiv 1,\ \  so\ \ a = (5j\!-\!1)^{6m} \!- (5k\!-\!1)^{6n}\equiv  1^m\! - 1^n\equiv 0$$
Therefore $\rm\ 5,7\:|\:a\:\Rightarrow\: lcm(5,7)=35\:|\:a.\ \ $ QED
A: You can use binomial theorem to break up the individual bases into multiples of the divisor and then you can expand binomially to check divisibilty. This is in a general case of doing such a problem . There may be more methods of doing such a problem.
A: $$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.
