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

Revision as of 20:00, 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

Solution 4 (Bashing ft. Euler

$2011^{2011} \equiv 11^{2011} \pmod 1000$ . By Euler's Totient Theorem, we also know that, since 11 and 1000 are coprime, $11^{400} \equiv 1 \pmod 1000$ ; note that the Euler Totient Function on $1000 gives$ 400 $. We also know that raising$ 1 $to any power on the right hand side of any modular congruence is "allowed", because$ 1 $to any power is always$ 1 $. Therefore, we also know that$ (11^{400})^5 \equiv \pmod 1000 $and thus$ 11^2000 \equiv \pmod 1000 $. Going back to the original equation, the problem reduces to finding the following:$ 11^11 \pmod 1000 $. Now comes the bashing. We need to find$ 121^{5} * 11 $modulo$ 1000 $, and then performing the arithmetic (all we need to find is$ 121^4 $modulo$ 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.

@@ 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