# 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?

• Are you familiar with Euler's theorem: en.wikipedia.org/wiki/Euler%27s_theorem ? – Eric O. Korman Sep 3 '12 at 16:54
• Note that the question in the title is different (and much easier!) than the question in the text; the former only involves a power of a single number, whereas the latter involves a difference of numbers, which can complicate things. – Steven Stadnicki Sep 3 '12 at 16:59
• Edited title to reflect that. – Takkun Sep 3 '12 at 17:02
• $\phi(35)=24= gcd (1536, 4824)$ – N. S. Sep 4 '12 at 2:28

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

• How do the exponents 1536 and 4824 work with fermat's theorem? $a^{5-1} = 1$ mod $5$ and $a^{7-1} = 1$ mod $7$? I understand your second point, but how do you incorporate fermat's into that? – Takkun Sep 3 '12 at 17:14
• If $a^4 \equiv 1\pmod 5$ then $a^{1536} = a^{4\cdot 384} = (a^4)^{384}\equiv 1^{384} = 1$. – Hagen von Eitzen Sep 3 '12 at 17:18
• For instance, $4^{1536}=(4^4)^{384}\equiv 1^{384}\mod 5$ – Jonathan Sep 3 '12 at 17:18
• Your statement of little Fermat is incorrect - it requires $\, p\nmid a,\$ (which is true here). – Bill Dubuque Sep 4 '12 at 1:29

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

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.

• How does the binomial theorem apply in a case of unequal powers? – Steven Stadnicki Sep 3 '12 at 17:00
• No i meant to convert say 4^3 as (63-1). say you have 4^9 you can break this as (63-1)^3 and then expand binomially if you want to check divisibilty, say by 7. – SN77 Sep 3 '12 at 17:03

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