2
$\begingroup$

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?

  • 0
    $\phi(35)=24= gcd (1536, 4824)$2012-09-04

4 Answers 4

6

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

  • 0
    Your statement of little Fermat is incorrect - it requires $\, p\nmid a,\ $ (which is true here).2012-09-04
1

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

0

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.

  • 0
    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.2012-09-03
0

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