2014 AMC 10B Problem 17

We need to know exactly how many times $2$ goes into the number, so break it into pieces and count the $2$s in each piece.

1. Rewrite with base $2$. $4^{501} = (2^2)^{501} = 2^{1002}$, and $10^{1002} = 2^{1002} \times 5^{1002}$. So
$$10^{1002} - 4^{501} = 2^{1002} \times \left(5^{1002} - 1\right).$$
2. That gives $1002$ factors of $2$ so far. But $5^{1002}$ is odd, so $5^{1002} - 1$ is even and has more $2$s. We must count them.
3. Small cases first to see the pattern for $5^{\text{even}} - 1$:
- $5^2 - 1 = 24 = 8 \times 3$: three $2$s.
- $5^6 - 1 = 15624 = 8 \times 1953$: three $2$s.
This suggests the answer "three". Here is why it is always true for $5^{1002} - 1$.
4. Split it as a difference of squares:
$$5^{1002} - 1 = \left(5^{501} - 1\right)\left(5^{501} + 1\right).$$
5. The piece $5^{501} + 1$. Every power of $5$ is one more than a multiple of $4$ ($5, 25, 125, \ldots$ leave remainder $1$ when divided by $4$). So $5^{501} + 1$ leaves remainder $2$ when divided by $4$. It is even but not a multiple of $4$: exactly one $2$.
6. The piece $5^{501} - 1$. It equals $4 \times \left(5^{500} + 5^{499} + \cdots + 5 + 1\right)$. (Check with a small case: $5^2 - 1 = 24 = 4 \times (5 + 1)$.) The bracket is a sum of $501$ odd numbers, and an odd count of odd numbers adds up to an odd number. So this piece has exactly the two $2$s from the $4$.
7. Add up. $5^{1002} - 1$ has $1 + 2 = 3$ factors of $2$, and the whole number has $1002 + 3 = 1005$.

The answer is $\boxed{\textbf{(D)}\ 2^{1005}}$.

"Greatest power of $2$ that divides" means counting the $2$s exactly. Taking out the obvious common factor is only the first step; what is left over can still be even. Splitting $a^2 - 1$ into $(a - 1)(a + 1)$ and checking each piece's remainder when divided by $4$ is the standard way to finish this kind of count.

Look at remainders when dividing by $16$. $5^2 = 25$ leaves remainder $9$, and $9 \times 9 = 81$ leaves remainder $1$. So $5^4$ leaves remainder $1$, and $5^{1000}$ does too. Then $5^{1002} = 5^{1000} \times 25$ leaves remainder $9$, and $5^{1002} - 1$ leaves remainder $8$. It is a multiple of $8$ but not of $16$: exactly three extra $2$s, for $2^{1005}$ in total.

Write both terms with base $2$: $10^{1002} = 2^{1002} \cdot 5^{1002}$ and $4^{501} = 2^{1002}$. Hence
$$10^{1002} - 4^{501} = 2^{1002}\left(5^{1002} - 1\right).$$

Now count the factors of $2$ in $5^{1002} - 1$. By difference of squares,
$$5^{1002} - 1 = \left(5^{501} - 1\right)\left(5^{501} + 1\right).$$

• $5^{501} + 1$: since $5 \equiv 1 \pmod 4$, $5^{501} \equiv 1 \pmod 4$, so $5^{501} + 1 \equiv 2 \pmod 4$. It is divisible by $2$ but not by $4$: exactly one factor of $2$.
• $5^{501} - 1 = (5 - 1)\left(5^{500} + 5^{499} + \cdots + 5 + 1\right)$. The second factor is a sum of $501$ odd numbers, hence odd. So $5^{501} - 1$ has exactly the two factors of $2$ from $5 - 1 = 4$.

Therefore $5^{1002} - 1$ has exactly $2^{1 + 2} = 2^3$, and the whole expression has $2^{1002 + 3} = 2^{1005}$.

The answer is $\boxed{\textbf{(D)}\ 2^{1005}}$.