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

m
(Solution 4 (naive solution))
(14 intermediate revisions by 8 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 1 \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 <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>, <math>f(11^n) = 1 + 2 + 3... + (n-1)</math>, or <math>\frac{(2010 * 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.
+
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
 
-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