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

(Solution 3)
(Solution 4 (naive solution))
(24 intermediate revisions by 14 users not shown)
Line 19: Line 19:
 
Therefore, the hundreds digit is <math>\boxed{\textbf{(D) } 6}.</math>
 
Therefore, the hundreds digit is <math>\boxed{\textbf{(D) } 6}.</math>
  
Sidenote: By [[Euler's Totient Theorem]], <math>a^{\phi (1000)} \equiv a \pmod{1000}</math> for any <math>a</math>, so <math>a^{400} \equiv a \pmod{1000}</math> and <math>11^{2011} \equiv 11^{11} \pmod{1000}</math>. We can then proceed using the clever application of the Binomial Theorem.
+
Side note: By [[Euler's Totient Theorem]], <math>a^{\phi (1000)} \equiv 1 \pmod{1000}</math> for any <math>a</math> relatively prime with 1000, so <math>a^{400} \equiv 1 \pmod{1000}</math> and <math>11^{2011} \equiv 11^{11} \pmod{1000}</math>. We can then proceed using the clever application of the Binomial Theorem.
  
 
== Solution 2 ==
 
== Solution 2 ==
  
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 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>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>
Line 33: Line 33:
 
== Solution 3 ==
 
== 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 (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 <math>\boxed{\textbf{(D) } 6}</math>. The one at the very end of the row doesn't affect anything, so we can leave it alone.
+
Notice that the hundreds digit of <math>2011^{2011}</math> won't be affected by <math>2000</math>. Essentially we could solve the problem by finding the hundreds digit of <math>11^{2011}</math>. Powers of <math>11</math> are special because they can be represented by the Pascal's Triangle. Drawing the triangle, there is a theorem that states the powers of <math>11</math> 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 <math>1, 5, 10, 10, 5,</math> and <math>1</math>. Adding all numbers from right to left, we get <math>161051</math>, which is also <math>11^5</math>. In other words, each number is <math>10^n</math> steps from the right side of the row. The hundreds digit is <math>0</math>. We can do the same for <math>11^{2011}</math>, but we only need to find the <math>3</math> digits from the right. Observing, every <math>3</math> number from the right is <math>1 + 2 + 3... + n</math>. So to find the third number from the right on the row of <math>11^{2011}</math>, <cmath>f(11^n) = 1 + 2 + 3... + (n-1),</cmath> or <math>\frac{(2010 \cdot 2011)}{2}</math>, or <math>2021055</math>. 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 <math>2011</math>. We must carry the <math>1</math> in <math>2011</math>'s tens digit to the <math>5</math> in <math>2021055</math>'s unit digit to get <math>\boxed{\textbf{(D) } 6}</math>. The one at the very end of the row doesn't affect anything, so we can leave it alone.
 +
 
 +
 
 +
-jackshi2006
 +
 
 +
==Solution 4 (naive solution) ==
 +
 
 +
Since we are only looking at the last 3 digits and <math>2011^2</math> has the same last 3 digits as <math>11^2</math>, we can find <math>11^{2011}</math> instead.
 +
After this, we can repeatedly multiply the last 3 digits by 11 and take the last 3 digits of that product. We discover that <math>11^{51}</math>'s last 2 digits are -11, the same as <math>11^1</math>.
 +
 
 +
From this information, we can figure out <math>11^{11}</math> and <math>11^{61}</math> end in 611. Adding various multiples of 50 to the exponent gives us the fact that <math>11^{2011}</math>'s last digits are 611. We get <math>\boxed{\textbf{(D) } 6}</math>.
 +
-ThisUsernameIsTaken
 +
 
 +
==Solution 5 (modular bash)==
 +
We are looking for <cmath>2011^{2011}\mod\left(1000\right)</cmath> Rewrite as <cmath>2011^{\left(1+2+8+16+64+128+256+512+1024\right)}=\left(2011^{1}\cdot2011^{2}\cdot2011^{8}\cdot...\cdot2011^{512}\cdot2011^{1024}\right)</cmath> and we are looking for the <math>\mod 1000</math> of this, which is <cmath>(2011\mod1000\cdot2011^{2}\mod1000\cdot...\cdot2011^{1024}\mod1000)\mod1000</cmath>
 +
Ignore the digits past the hundreds place and bash it out.
 +
<cmath>2011\mod1000 = 11</cmath>
 +
<cmath>2011^{2}\mod1000 =121</cmath>
 +
<cmath>2011^{4}\mod1000 =641</cmath>
 +
<cmath>2011^{8}\mod1000 =881</cmath>
 +
<cmath>2011^{16}\mod1000 =161</cmath>
 +
<cmath>2011^{32}\mod1000 =921</cmath>
 +
<cmath>2011^{64}\mod1000 =241</cmath>
 +
<cmath>2011^{128}\mod1000 =081</cmath>
 +
<cmath>2011^{256}\mod1000 =561</cmath>
 +
<cmath>2011^{512}\mod1000 =721</cmath>
 +
<cmath>2011^{1024}\mod1000 =841</cmath>
 +
We do this by substituting each result of the previous power of 2 and multiplying in <math>\mod 1000</math>. Next, we use the expression <cmath>(2011\mod1000\cdot2011^{2}\mod1000\cdot...\cdot2011^{1024}\mod1000)\mod1000</cmath> and substitute the values for the different powers in and simplify to <math>\mod1000</math> as we go (by ignoring the thousands digits and beyond during multiplication) to get <math>2011^{2011}\mod1000=611</math>, and the hundreds digit is <math>\boxed{\textbf{(D) } 6}</math>.
 +
 
 +
~JH. L
 +
 
 +
==Video Solution by TheBeautyofMath==
 +
https://youtu.be/7rosJnqLhs8?t=323
 +
 
 +
~IceMatrix
  
 
==See Also==
 
==See Also==
 
{{AMC10 box|year=2011|ab=B|num-a=24|num-b=22}}
 
{{AMC10 box|year=2011|ab=B|num-a=24|num-b=22}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 05:32, 25 June 2022

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

Side note: By Euler's Totient Theorem, $a^{\phi (1000)} \equiv 1 \pmod{1000}$ for any $a$ relatively prime with 1000, so $a^{400} \equiv 1 \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 \cdot 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 (naive solution)

Since we are only looking at the last 3 digits and $2011^2$ has the same last 3 digits as $11^2$, we can find $11^{2011}$ instead. After this, we can repeatedly multiply the last 3 digits by 11 and take the last 3 digits of that product. We discover that $11^{51}$'s last 2 digits are -11, the same as $11^1$.

From this information, we can figure out $11^{11}$ and $11^{61}$ end in 611. Adding various multiples of 50 to the exponent gives us the fact that $11^{2011}$'s last digits are 611. We get $\boxed{\textbf{(D) } 6}$. -ThisUsernameIsTaken

Solution 5 (modular bash)

We are looking for \[2011^{2011}\mod\left(1000\right)\] Rewrite as \[2011^{\left(1+2+8+16+64+128+256+512+1024\right)}=\left(2011^{1}\cdot2011^{2}\cdot2011^{8}\cdot...\cdot2011^{512}\cdot2011^{1024}\right)\] and we are looking for the $\mod 1000$ of this, which is \[(2011\mod1000\cdot2011^{2}\mod1000\cdot...\cdot2011^{1024}\mod1000)\mod1000\] Ignore the digits past the hundreds place and bash it out. \[2011\mod1000 = 11\] \[2011^{2}\mod1000 =121\] \[2011^{4}\mod1000 =641\] \[2011^{8}\mod1000 =881\] \[2011^{16}\mod1000 =161\] \[2011^{32}\mod1000 =921\] \[2011^{64}\mod1000 =241\] \[2011^{128}\mod1000 =081\] \[2011^{256}\mod1000 =561\] \[2011^{512}\mod1000 =721\] \[2011^{1024}\mod1000 =841\] We do this by substituting each result of the previous power of 2 and multiplying in $\mod 1000$. Next, we use the expression \[(2011\mod1000\cdot2011^{2}\mod1000\cdot...\cdot2011^{1024}\mod1000)\mod1000\] and substitute the values for the different powers in and simplify to $\mod1000$ as we go (by ignoring the thousands digits and beyond during multiplication) to get $2011^{2011}\mod1000=611$, and the hundreds digit is $\boxed{\textbf{(D) } 6}$.

~JH. L

Video Solution by TheBeautyofMath

https://youtu.be/7rosJnqLhs8?t=323

~IceMatrix

See Also

2011 AMC 10B (ProblemsAnswer KeyResources)
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

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