Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Are you familiar with Euler's theorem: en.wikipedia.org/wiki/Euler%27s_theorem ? –  Eric O. Korman Sep 3 '12 at 16:54
1  
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

4 Answers 4

up vote 6 down vote accepted

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

share|improve this answer
    
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
2  
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
    
Thank you. I amended. –  Jonathan Sep 4 '12 at 1:40

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

share|improve this answer

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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