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

(Solution)
(Solution 2)
Line 18: Line 18:
 
First, we can write the expression in a more primitive form which will allow us to start factoring.
 
First, we can write the expression in a more primitive form which will allow us to start factoring.
 
<cmath>10^{1002} - 4^{501} = 2^{1002} \cdot 5^{1002} - 2^{1002}</cmath>
 
<cmath>10^{1002} - 4^{501} = 2^{1002} \cdot 5^{1002} - 2^{1002}</cmath>
Now, we can factor out <math>2^{1002}</math>. This leaves us with <math>5^{1002} - 1</math>. Call this number <math>N</math> Thus, our final answer will be <math>2^{1002+k}</math>, where <math>k</math> is the largest power of <math>2</math> that divides <math>N</math>. Now we can consider <math>N \pmod{16}</math>, since <math>k \le 4</math> by the answer choices.  
+
Now, we can factor out <math>2^{1002}</math>. This leaves us with <math>5^{1002} - 1</math>. Call this number <math>N</math>. Thus, our final answer will be <math>2^{1002+k}</math>, where <math>k</math> is the largest power of <math>2</math> that divides <math>N</math>. Now we can consider <math>N \pmod{16}</math>, since <math>k \le 4</math> by the answer choices.  
  
 
Note that
 
Note that
 
<cmath>515(mod16)529(mod16)5313(mod16)541(mod16)555(mod16)</cmath>
 
<cmath>515(mod16)529(mod16)5313(mod16)541(mod16)555(mod16)</cmath>
 +
The powers of <math>5</math> cycle in <math>\mod{16}</math> with a period of <math>4</math>. Thus, <cmath>5^{1002} \equiv 5^2 \equiv 9 \pmod{16} \implies 5^1002 - 1 \equiv 8 \pmod{16}</cmath>
 +
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>.
  
 
==See Also==
 
==See Also==
 
{{AMC10 box|year=2014|ab=B|num-b=16|num-a=18}}
 
{{AMC10 box|year=2014|ab=B|num-b=16|num-a=18}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 02:09, 23 February 2014

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. $(5^{167} - 1)$ ends in ...$124$, contributing two powers of two to the final result.

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

See Also

2014 AMC 10B (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png