Difference between revisions of "2014 AMC 10B Problems/Problem 17"

Revision as of 17:26, 9 January 2021

Problem 17

What is the greatest power of $2$ that is a factor of $10^{1002} - 4^{501}$ ?

$\textbf{(A) } 2^{1002} \qquad\textbf{(B) } 2^{1003} \qquad\textbf{(C) } 2^{1004} \qquad\textbf{(D) } 2^{1005} \qquad\textbf{(E) }2^{1006}$

Solution 1

We begin by factoring the $2^{1002}$ out. This leaves us with $5^{1002} - 1$ .

We factor the difference of squares, leaving us with $(5^{501} - 1)(5^{501} + 1)$ . We note that all even powers of $5$ more than two end in ... $625$ . Also, all odd powers of five more than $2$ end in ... $125$ . Thus, $(5^{501} + 1)$ would end in ... $126$ and thus would contribute one power of two to the answer, but not more.

We can continue to factor $(5^{501} - 1)$ as a difference of cubes, leaving us with $(5^{167} - 1)$ times an odd number (Notice that the other number is $5^{334} + 5^{167} + 1$ . The powers of $5$ end in $5$ , so the two powers of $5$ will end with $0$ . Adding $1$ will make it end in $1$ . Thus, this is an odd number). $(5^{167} - 1)$ ends in ... $124$ , contributing two powers of two to the final result.

Or we can see that $(5^{501} - 1)$ ends in $124$ , and is divisible by $2$ only. Still that's $2$ powers of $2$ .

Adding these extra $3$ powers of two to the original $1002$ factored out, we obtain the final answer of $\textbf{(D) } 2^{1005}$ .

Solution 2

First, we can write the expression in a more primitive form which will allow us to start factoring. $10^{1002} - 4^{501} = 2^{1002} \cdot 5^{1002} - 2^{1002}$ Now, we can factor out $2^{1002}$ . This leaves us with $5^{1002} - 1$ . Call this number $N$ . Thus, our final answer will be $2^{1002+k}$ , where $k$ is the largest power of $2$ that divides $N$ . Now we can consider $N \pmod{16}$ , since $k \le 4$ by the answer choices.

Note that $\begin{align*} 5^1 &\equiv 5 \pmod{16} \\ 5^2 &\equiv 9 \pmod{16} \\ 5^3 &\equiv 13 \pmod{16} \\ 5^4 &\equiv 1 \pmod{16} \\ 5^5 &\equiv 5 \pmod{16} \\ &\: \: \qquad \vdots \end{align*}$ The powers of $5$ cycle in $\mod{16}$ with a period of $4$ . Thus, $5^{1002} \equiv 5^2 \equiv 9 \pmod{16} \implies 5^{1002} - 1 \equiv 8 \pmod{16}$ This means that $N$ is divisible by $8= 2^3$ but not $16 = 2^4$ , so $k = 3$ and our answer is $2^{1002 + 3} =\boxed{\textbf{(D)}\: 2^{1005}}$ .

Solution 3

Convert $4^{501}=2^{1002}$ . We can factor out $2^{1002}$ to get that $\nu_2(10^{1002}-2^{1002})=1002+\nu_2(5^{1002}-1)$ . Using the adjusted LTE lemma ( $\nu_2(a^n-b^n)=\nu_2(n)+\nu_2(a^2-b^2)-1$ for all even $n$ and odd $a,b$ ), we get that the answer is equal to $2^{1002+\nu_2(1002)+\nu_2(24)-1}=2^{1002+1+3-1}=\boxed{\textbf{(D)}2^{1005}}$ .

Video Solution

https://youtu.be/aCtvD8nitgg

~savannahsolver

@@ Line 27: / Line 27: @@
 This means that <math>N</math> is divisible by <math>8= 2^3</math> but not <math>16 = 2^4</math>, so <math>k = 3</math> and our answer is <math>2^{1002 + 3} =\boxed{\textbf{(D)}\: 2^{1005}}</math>.
+==Solution 3==
+Convert <math>4^{501}=2^{1002}</math>. We can factor out <math>2^{1002}</math> to get that <math>\nu_2(10^{1002}-2^{1002})=1002+\nu_2(5^{1002}-1)</math>. Using the adjusted LTE lemma (<math>\nu_2(a^n-b^n)=\nu_2(n)+\nu_2(a^2-b^2)-1</math> for all even <math>n</math> and odd <math>a,b</math>), we get that the answer is equal to <math>2^{1002+\nu_2(1002)+\nu_2(24)-1}=2^{1002+1+3-1}=\boxed{\textbf{(D)}2^{1005}}</math>.
 ==Video Solution==
 https://youtu.be/aCtvD8nitgg

2014 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 16	Followed by Problem 18
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

Page

Toolbox

Search