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?

$\endgroup$
4
  • 3
    $\begingroup$ Are you familiar with Euler's theorem: en.wikipedia.org/wiki/Euler%27s_theorem ? $\endgroup$ – Eric O. Korman Sep 3 '12 at 16:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Sep 3 '12 at 16:59
  • $\begingroup$ Edited title to reflect that. $\endgroup$ – Takkun Sep 3 '12 at 17:02
  • $\begingroup$ $\phi(35)=24= gcd (1536, 4824)$ $\endgroup$ – N. S. Sep 4 '12 at 2:28
6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – Takkun Sep 3 '12 at 17:14
  • 2
    $\begingroup$ If $a^4 \equiv 1\pmod 5$ then $a^{1536} = a^{4\cdot 384} = (a^4)^{384}\equiv 1^{384} = 1$. $\endgroup$ – Hagen von Eitzen Sep 3 '12 at 17:18
  • $\begingroup$ For instance, $4^{1536}=(4^4)^{384}\equiv 1^{384}\mod 5$ $\endgroup$ – Jonathan Sep 3 '12 at 17:18
  • $\begingroup$ Your statement of little Fermat is incorrect - it requires $\, p\nmid a,\ $ (which is true here). $\endgroup$ – Bill Dubuque Sep 4 '12 at 1:29
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How does the binomial theorem apply in a case of unequal powers? $\endgroup$ – Steven Stadnicki Sep 3 '12 at 17:00
  • $\begingroup$ 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. $\endgroup$ – SN77 Sep 3 '12 at 17:03
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.