Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Solution 1)
m (→‎Solution 1)
Line 8: Line 8:
 
We begin by factoring the <math>2^{1002}</math> out. This leaves us with <math>5^{1002} - 1</math>.  
 
We begin by factoring the <math>2^{1002}</math> out. This leaves us with <math>5^{1002} - 1</math>.  
  
−
We factor the difference of squares, leaving us with <math>(5^{501} - 1)(5^{501} + 1)</math>. We note that all even powers of <math>5</math> more than two end in ...<math>625</math>. Also, all odd powers of five more than 42<math> end in  ...</math>125<math>. Thus, </math>(5^{501} + 1)<math> would end in ...</math>126<math> and thus would contribute one power of two to the answer, but not more.  
+
We factor the difference of squares, leaving us with <math>(5^{501} - 1)(5^{501} + 1)</math>. We note that all even powers of <math>5</math> more than two end in ...<math>625</math>. Also, all odd powers of five more than <math>2</math> end in  ...<math>125</math>. Thus, <math>(5^{501} + 1)</math> would end in ...<math>126</math> and thus would contribute one power of two to the answer, but not more.  
  
−
We can continue to factor </math>(5^{501} - 1)<math> as a difference of cubes, leaving us with </math>(5^{167} - 1)<math> times an odd number (Notice that the other number is </math>5^{334} + 5^{167} + 1<math>. The powers of </math>5<math> end in </math>5<math>, so the two powers of </math>5<math> will end with </math>0<math>. Adding </math>1<math> will make it end in </math>1<math>. Thus, this is an odd number). </math>(5^{167} - 1)<math> ends in ...</math>124<math>, contributing two powers of two to the final result.
+
We can continue to factor <math>(5^{501} - 1)</math> as a difference of cubes, leaving us with <math>(5^{167} - 1)</math> times an odd number (Notice that the other number is <math>5^{334} + 5^{167} + 1</math>. The powers of <math>5</math> end in <math>5</math>, so the two powers of <math>5</math> will end with <math>0</math>. Adding <math>1</math> will make it end in <math>1</math>. Thus, this is an odd number). <math>(5^{167} - 1)</math> ends in ...<math>124</math>, contributing two powers of two to the final result.
  
−
Or we can see that </math>(5^{501} - 1)<math> ends in 124, and is divisible by </math>2<math> only. Still that's </math>2<math> powers of 2.
+
Or we can see that <math>(5^{501} - 1)</math> ends in 124, and is divisible by <math>2</math> only. Still that's <math>2</math> powers of 2.
 
   
 
   
−
Adding these extra </math>3<math> powers of two to the original </math>1002<math> factored out, we obtain the final answer of </math>\textbf{(D) } 2^{1005}$.
+
Adding these extra <math>3</math> powers of two to the original <math>1002</math> factored out, we obtain the final answer of <math>\textbf{(D) } 2^{1005}</math>.
  
 
==Solution 2==
 
==Solution 2==

Revision as of 18:54, 27 December 2019

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


See Also

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_AMC_10B_Problems/Problem_17&oldid=113571"