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 "2011 AMC 10B Problems/Problem 23"
Line 1: Line 1:
−
==Problem==  
+
==Solution==
 +
 
 +
'''Solution 1:'''
 +
 
 +
Since <math>2011 \equiv 11  \pmod{1000},</math> we know that <math>2011^{2011} \equiv 11^{2011}  \pmod{1000}.</math>
  
−
What is the hundreds digit of <math>2011^{2011}</math>?
+
To compute this, we use a clever application of the [[binomial theorem]].
  
−
<math>\textbf{(A)}\ 1 \qquad \textbf{(B)}\ 3 \qquad \textbf{(C)}\ 5 \qquad \textbf{(D)}\ 6 \qquad \textbf{(E)}\ 9</math>
+
<cmath>\begin{aligned} 11^{2011} &= (1+10)^{2011} \\ &= 1 + \dbinom{2011}{1} \cdot 10 + \dbinom{2011}{2} \cdot 10^2 + \cdots \end{aligned}</cmath>
 +
 
 +
In all of the other terms, the power of <math>10</math> is greater than <math>3</math> and so is equivalent to <math>0</math> modulo <math>1000,</math> which means we can ignore it. We have:
 +
 
 +
<cmath>\begin{aligned}11^{2011} &= 1 + 2011\cdot 10 + \dfrac{2011 \cdot 2010}{2} \cdot 100 \\ &\equiv 1+20110 + \dfrac{11\cdot 10}{2} \cdot 100\\ &= 1 + 20110 + 5500\\ &\equiv 1 + 110 + 500\\&=611 \pmod{1000} \end{aligned}</cmath>
 +
 
 +
Therefore, the hundreds digit is <math>\boxed{\textbf{(D) } 6}.</math>
  
−
==Solution==
 
−
Since <math>2011 \equiv 11  (\text{mod }1000),</math> we know <math>2011^{2011} \equiv 11^{2011}  (\text{mod }1000).</math>
 
  
−
To compute this, write it as <math>(1+10)^{2011}</math> and use the [[binomial theorem]].
+
'''Solution 2:'''
  
−
<cmath>1^{2011} + 2011 \cdot 1^{2010}10^1 + \frac{2011 \cdot 2010}{2} 1^{2009}10^{2} + \cdots</cmath>
+
We need to compute <math>2011^{2011} \pmod{1000}.</math> By the Chinese Remainder Theorem, it suffices to compute <math>2011^{2011} \pmod{8}</math> and <math>2011^{2011} \pmod{125}.</math>
−
From then on the power of <math>10</math> is greater than <math>3</math> and cancel out with <math>\text{mod }1000.</math>
 
−
<cmath>\begin{align*}
 
−
11^{2011} &\equiv 1 + 20110 + 100\frac{11 \cdot 10}{2}\\
 
−
&= 1 + 20110 + 5500\\
 
−
&\equiv 1 + 110 + 500\\
 
−
&=611
 
−
\end{align*}</cmath>
 
  
−
Therefore, the hundreds digit is <math>\boxed{\textbf{(D) } 6}</math>
+
In modulo <math>8,</math> we have <math>2011^4 \equiv 1 \pmod{8}</math> by [[Euler's_Totient_Theorem| Euler's Theorem]], and also <math>2011 \equiv 3 \pmod{8},</math> so we have <cmath>2011^{2011} = (2011^4)^{502} \cdot 2011^3 \equiv 1^{502} \cdot 3^3 \equiv 3 \pmod{8}.</cmath>
  
−
== See Also==
+
In modulo <math>125,</math> we have <math>2011^{100} \equiv 1 \pmod{125}</math> by Euler's Theorem, and also <math>2011 \equiv 11 \pmod{125}.</math> Therefore, we have <cmath>\begin{aligned} 2011^{2011} &= (2011^{100})^{20} \cdot 2011^{11} \\ &\equiv 1^{20} \cdot 11^{11} \\ &= 121^5 \cdot 11 \\ &= (-4)^5 \cdot 11 = -1024 \cdot 11 \\ &\equiv -24 \cdot 11 = -264 \\ &\equiv 111 \pmod{125}. \end{aligned} </cmath>
  
−
{{AMC10 box|year=2011|ab=B|num-b=22|num-a=24}}
+
After finding the solution <math>2011^{2011} \equiv 611 \pmod{1000},</math> we conclude it is the only one by the Chinese Remainder Theorem. Thus, the hundreds digit is <math>\boxed{\textbf{(D) } 6}.</math>
−
{{MAA Notice}}
 

Revision as of 14:50, 17 August 2013

Solution

Solution 1:

Since $2011 \equiv 11 \pmod{1000},$ we know that $2011^{2011} \equiv 11^{2011} \pmod{1000}.$

To compute this, we use a clever application of the binomial theorem. 

\begin{aligned} 11^{2011} &= (1+10)^{2011} \\ &= 1 + \dbinom{2011}{1} \cdot 10 + \dbinom{2011}{2} \cdot 10^2 + \cdots \end{aligned} (Error compiling LaTeX. Unknown error_msg)

In all of the other terms, the power of $10$ is greater than $3$ and so is equivalent to $0$ modulo $1000,$ which means we can ignore it. We have: 

\begin{aligned}11^{2011} &= 1 + 2011\cdot 10 + \dfrac{2011 \cdot 2010}{2} \cdot 100 \\ &\equiv 1+20110 + \dfrac{11\cdot 10}{2} \cdot 100\\ &= 1 + 20110 + 5500\\ &\equiv 1 + 110 + 500\\&=611 \pmod{1000} \end{aligned} (Error compiling LaTeX. Unknown error_msg)

Therefore, the hundreds digit is $\boxed{\textbf{(D) } 6}.$


Solution 2:

We need to compute $2011^{2011} \pmod{1000}.$ By the Chinese Remainder Theorem, it suffices to compute $2011^{2011} \pmod{8}$ and $2011^{2011} \pmod{125}.$

In modulo $8,$ we have $2011^4 \equiv 1 \pmod{8}$ by Euler's Theorem, and also $2011 \equiv 3 \pmod{8},$ so we have \[2011^{2011} = (2011^4)^{502} \cdot 2011^3 \equiv 1^{502} \cdot 3^3 \equiv 3 \pmod{8}.\]

In modulo $125,$ we have $2011^{100} \equiv 1 \pmod{125}$ by Euler's Theorem, and also $2011 \equiv 11 \pmod{125}.$ Therefore, we have 

\begin{aligned} 2011^{2011} &= (2011^{100})^{20} \cdot 2011^{11} \\ &\equiv 1^{20} \cdot 11^{11} \\ &= 121^5 \cdot 11 \\ &= (-4)^5 \cdot 11 = -1024 \cdot 11 \\ &\equiv -24 \cdot 11 = -264 \\ &\equiv 111 \pmod{125}. \end{aligned} (Error compiling LaTeX. Unknown error_msg)

After finding the solution $2011^{2011} \equiv 611 \pmod{1000},$ we conclude it is the only one by the Chinese Remainder Theorem. Thus, the hundreds digit is $\boxed{\textbf{(D) } 6}.$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_10B_Problems/Problem_23&oldid=56940"