Difference between revisions of "2011 AMC 10B Problems/Problem 23"

Revision as of 21:35, 31 May 2020

Problem

What is the hundreds digit of $2011^{2011}?$

$\textbf{(A) } 1 \qquad \textbf{(B) } 4 \qquad \textbf{(C) }5 \qquad \textbf{(D) } 6 \qquad \textbf{(E) } 9$

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

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} &\equiv 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}$

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

Sidenote: By Euler's Totient Theorem, $a^{\phi (1000)} \equiv 1 \pmod{1000}$ for any $a$ , so $a^{400} \equiv a \pmod{1000}$ and $11^{2011} \equiv 11^{11} \pmod{1000}$ . We can then proceed using the clever application of the Binomial Theorem.

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

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

Solution 3

Notice that the hundreds digit of $2011^{2011}$ won't be affected by $2000$ . Essentially we could solve the problem by finding the hundreds digit of $11^{2011}$ . Powers of $11$ are special because they can be represented by the Pascal's Triangle. Drawing the triangle, there is a theorem that states the powers of $11$ can be found by reading rows of the triangle and adding extra numbers up. [add source] For example, the sixth row of the triangle is $1, 5, 10, 10, 5,$ and $1$ . Adding all numbers from right to left, we get $161051$ , which is also $11^5$ . In other words, each number is $10^n$ steps from the right side of the row. The hundreds digit is $0$ . We can do the same for $11^{2011}$ , but we only need to find the $3$ digits from the right. Observing, every $3$ number from the right is $1 + 2 + 3... + n$ . So to find the third number from the right on the row of $11^{2011}$ , $f(11^n) = 1 + 2 + 3... + (n-1)$ , or $\frac{(2010 * 2011)}{2}$ , or $2021055$ . The last digit is five, but we must remember to add the number on the right of it, which, by observing other rows is obviously $2011$ . We must carry the $1$ in $2011$ 's tens digit to the $5$ in $2021055$ 's unit digit to get $\boxed{\textbf{(D) } 6}$ . The one at the very end of the row doesn't affect anything, so we can leave it alone.

-jackshi2006

@@ Line 37: / Line 37: @@
 -jackshi2006
-== Solution 4 (Bashing ft. Euler ==
-<math>2011^{2011} \equiv 11^{2011} \pmod 1000</math>.
-By Euler's Totient Theorem, we also know that, since 11 and 1000 are coprime, <math>11^{400} \equiv 1 \pmod 1000</math>; note that the Euler Totient Function on <math>1000 gives </math>400<math>. We also know that raising </math>1<math> to any power on the right hand side of any modular congruence is "allowed", because </math>1<math> to any power is always </math>1<math>. Therefore, we also know that
-</math>(11^{400})^5 \equiv \pmod 1000<math> and thus </math>11^2000 \equiv \pmod 1000<math>.
-Going back to the original equation, the problem reduces to finding the following:
-</math>11^11 \pmod 1000<math>. Now comes the bashing. We need to find </math>121^{5} * 11<math> modulo </math>1000<math>, and then performing the arithmetic (all we need to find is </math>121^4<math> modulo </math>1000$, not actually that hard considering it's only 3-digit multiplication). The answer comes out to 6.
-The solution seems difficult, but it doesn't require much intricate thinking, rather the simple theorem and elementary arithmetic. The solutions above are much more elegant tho.
 ==See Also==
 {{AMC10 box|year=2011|ab=B|num-a=24|num-b=22}}
 {{MAA Notice}}

2011 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 22	Followed by Problem 24
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