Difference between revisions of "2011 AMC 10B Problems/Problem 23"
| Line 1: | Line 1: | ||
| + | ==Problem== | ||
| + | |||
| + | What is the hundreds digit of <math>2011^{2011}?</math> | ||
| + | |||
| + | <math>\textbf{(A) } 1 \qquad \textbf{(B) } 4 \qquad \textbf{(C) }5 \qquad \textbf{(D) } 6 \qquad \textbf{(E) } 9</math> | ||
| + | |||
==Solution== | ==Solution== | ||
| Line 20: | Line 26: | ||
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> | 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> | ||
| − | In modulo <math>8,</math> we have <math>2011^4 \equiv 1 \pmod{8}</math> by | + | In modulo <math>8,</math> we have <math>2011^4 \equiv 1 \pmod{8}</math> by 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> |
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> | 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> | ||
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> | 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> | ||
Revision as of 14:53, 17 August 2013
Problem
What is the hundreds digit of 
Solution
Solution 1:
Since 
we know that 
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 
is greater than 
and so is equivalent to 
modulo 
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 
Solution 2:
We need to compute 
By the Chinese Remainder Theorem, it suffices to compute 
and 
In modulo 
we have 
by Euler's Theorem, and also 
so we have ![\[2011^{2011} = (2011^4)^{502} \cdot 2011^3 \equiv 1^{502} \cdot 3^3 \equiv 3 \pmod{8}.\]](http://latex.artofproblemsolving.com/0/0/0/0005cb6d3a60d8bfe27bc0ad83d3686a04cb0ff2.png)
In modulo 
we have 
by Euler's Theorem, and also 
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 
we conclude it is the only one by the Chinese Remainder Theorem. Thus, the hundreds digit is
