What is the greatest power of 2 that is a factor of $10^{1002}-4^{501}$? (2014 AMC10B #17) So I've been stuck on a problem for the whole day:
What is the greatest power of 2 that is a factor of $10^{1002}-4^{501}$?
Immediately, I set out to attempt it via some tried & tested methods:

*

*Difference of Squares:
$({ 10 }^{ 501 }-{ 4 }^{ \frac { 501 }{ 2 }  })({ 10 }^{ 501 }+{ 4 }^{ \frac { 501 }{ 2 }  })$ got me nowhere.


*Factoring
Neither does ${ (2*5) }^{ 1002 }-{ ({ 2 }^{ 2 }) }^{ 501 }\\ { 2 }^{ 1002 }({ 5 }^{ 1002 }-1)$ apparently


*Smaller Numbers
I tried think of smaller cases, such as ${ 2 }^{ 13 }|{ 10 }^{ 10 }-{ 4 }^{ 5 }\\ $ or ${ 2 }^{ 17 }|{ 10 }^{ 14 }-{ 4 }^{ 7 }\\ $, but I could not sense any pattern. Perhaps Euclid's Extended Algorithm could be used via some method. Any hints on this problem would be greatly appreciated.
 A: As you noticed it suffices to find $\nu_2(5^{1002} -1)$. 
We will use a very useful lemma, namely lifting the exponent.
Which says for $p=2$, when $p\nmid x,p\nmid y $ then the following identity holds:
$$\nu_2(x^n-y^n) =\nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1 $$
Applying this we obtain
$$ \nu_2(5^{1002} -1)=2+1+1-1=3  $$
A: Hints:


*

*$\;10^{1002}=(2 \cdot 5)^{1002}= 2^{2 \cdot 501} \cdot 5^{1002}=\cdots$

*$5^{1002}-1=(4+1)^{1002}-1 = 4 \cdot\left(4^{1001}+ \cdots + \binom{1002}{2} \cdot 4 + 1002\right)$
A: $$10^{1002}-4^{501} = 5^{1002}\cdot 2^{1002}-2^{1002} = 2^{1002}\cdot\left(5^{1002}-1\right)$$
so $\nu_2(\text{LHS})=1002+\nu_2\left(5^{1002}-1\right)$. Of course $5^{1002}-1$ is a multiple of $4$, since $5\equiv 1\pmod{4}$, and it is enough to consider the remainders of $5^{1002}-1$ $\pmod{8}$ and $\pmod{16}$.
Spoiler alert:

 By Euler's theorem
 $$ 5^{1002}-1 \equiv 5^{2}-1 \equiv 0\pmod{8}, $$
 but
 $$ 5^{1002}-1 \equiv 5^{2}-1 \not\equiv 0\pmod{16}, $$
 so $\nu_2\left(5^{1002}-1\right)=3$ and the answer to the given question is  $1002+3=\color{red}{1005}$.

A: You were on the right track when you considered some smaller cases. But even the simplest pattern might not become apparent after you look at just two cases. If you'd looked at a few more, then perhaps you'd have seen a pattern which would suggest the answer which others have already provided.
