https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Nshree24&feedformat=atom AoPS Wiki - User contributions [en] 2021-04-10T23:04:26Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2011_AMC_10B_Problems/Problem_23&diff=143024 2011 AMC 10B Problems/Problem 23 2021-01-23T23:22:28Z <p>Nshree24: /* Solution 4 (naive solution, EXTREMELY bashy) */</p> <hr /> <div>==Problem==<br /> <br /> What is the hundreds digit of &lt;math&gt;2011^{2011}?&lt;/math&gt;<br /> <br /> &lt;math&gt;\textbf{(A) } 1 \qquad \textbf{(B) } 4 \qquad \textbf{(C) }5 \qquad \textbf{(D) } 6 \qquad \textbf{(E) } 9&lt;/math&gt;<br /> <br /> ==Solution 1==<br /> <br /> Since &lt;math&gt;2011 \equiv 11 \pmod{1000},&lt;/math&gt; we know that &lt;math&gt;2011^{2011} \equiv 11^{2011} \pmod{1000}.&lt;/math&gt;<br /> <br /> To compute this, we use a clever application of the [[binomial theorem]].<br /> <br /> &lt;math&gt;\begin{aligned} 11^{2011} &amp;= (1+10)^{2011} \\ &amp;= 1 + \dbinom{2011}{1} \cdot 10 + \dbinom{2011}{2} \cdot 10^2 + \cdots \end{aligned}&lt;/math&gt;<br /> <br /> In all of the other terms, the power of &lt;math&gt;10&lt;/math&gt; is greater than &lt;math&gt;3&lt;/math&gt; and so is equivalent to &lt;math&gt;0&lt;/math&gt; modulo &lt;math&gt;1000,&lt;/math&gt; which means we can ignore it. We have:<br /> <br /> &lt;math&gt;\begin{aligned}11^{2011} &amp;\equiv 1 + 2011\cdot 10 + \dfrac{2011 \cdot 2010}{2} \cdot 100 \\ &amp;\equiv 1+20110 + \dfrac{11\cdot 10}{2} \cdot 100\\ &amp;= 1 + 20110 + 5500\\ &amp;\equiv 1 + 110 + 500\\&amp;=611 \pmod{1000} \end{aligned}&lt;/math&gt;<br /> <br /> Therefore, the hundreds digit is &lt;math&gt;\boxed{\textbf{(D) } 6}.&lt;/math&gt;<br /> <br /> Side note: By [[Euler's Totient Theorem]], &lt;math&gt;a^{\phi (1000)} \equiv 1 \pmod{1000}&lt;/math&gt; for any &lt;math&gt;a&lt;/math&gt; relatively prime with 1000, so &lt;math&gt;a^{400} \equiv 1 \pmod{1000}&lt;/math&gt; and &lt;math&gt;11^{2011} \equiv 11^{11} \pmod{1000}&lt;/math&gt;. We can then proceed using the clever application of the Binomial Theorem.<br /> <br /> == Solution 2 ==<br /> <br /> We need to compute &lt;math&gt;2011^{2011} \pmod{1000}.&lt;/math&gt; By the [[Chinese Remainder Theorem]], it suffices to compute &lt;math&gt;2011^{2011} \pmod{8}&lt;/math&gt; and &lt;math&gt;2011^{2011} \pmod{125}.&lt;/math&gt;<br /> <br /> In modulo &lt;math&gt;8,&lt;/math&gt; we have &lt;math&gt;2011^4 \equiv 1 \pmod{8}&lt;/math&gt; by Euler's Theorem, and also &lt;math&gt;2011 \equiv 3 \pmod{8},&lt;/math&gt; so we have &lt;cmath&gt;2011^{2011} = (2011^4)^{502} \cdot 2011^3 \equiv 1^{502} \cdot 3^3 \equiv 3 \pmod{8}.&lt;/cmath&gt;<br /> <br /> In modulo &lt;math&gt;125,&lt;/math&gt; we have &lt;math&gt;2011^{100} \equiv 1 \pmod{125}&lt;/math&gt; by Euler's Theorem, and also &lt;math&gt;2011 \equiv 11 \pmod{125}.&lt;/math&gt; Therefore, we have &lt;math&gt;\begin{aligned} 2011^{2011} &amp;= (2011^{100})^{20} \cdot 2011^{11} \\ &amp;\equiv 1^{20} \cdot 11^{11} \\ &amp;= 121^5 \cdot 11 \\ &amp;= (-4)^5 \cdot 11 = -1024 \cdot 11 \\ &amp;\equiv -24 \cdot 11 = -264 \\ &amp;\equiv 111 \pmod{125}. \end{aligned} &lt;/math&gt;<br /> <br /> After finding the solution &lt;math&gt;2011^{2011} \equiv 611 \pmod{1000},&lt;/math&gt; we conclude it is the only one by the Chinese Remainder Theorem. Thus, the hundreds digit is &lt;math&gt;\boxed{\textbf{(D) } 6}.&lt;/math&gt;<br /> <br /> == Solution 3 ==<br /> <br /> Notice that the hundreds digit of &lt;math&gt;2011^{2011}&lt;/math&gt; won't be affected by &lt;math&gt;2000&lt;/math&gt;. Essentially we could solve the problem by finding the hundreds digit of &lt;math&gt;11^{2011}&lt;/math&gt;. Powers of &lt;math&gt;11&lt;/math&gt; are special because they can be represented by the Pascal's Triangle. Drawing the triangle, there is a theorem that states the powers of &lt;math&gt;11&lt;/math&gt; 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 &lt;math&gt;1, 5, 10, 10, 5,&lt;/math&gt; and &lt;math&gt;1&lt;/math&gt;. Adding all numbers from right to left, we get &lt;math&gt;161051&lt;/math&gt;, which is also &lt;math&gt;11^5&lt;/math&gt;. In other words, each number is &lt;math&gt;10^n&lt;/math&gt; steps from the right side of the row. The hundreds digit is &lt;math&gt;0&lt;/math&gt;. We can do the same for &lt;math&gt;11^{2011}&lt;/math&gt;, but we only need to find the &lt;math&gt;3&lt;/math&gt; digits from the right. Observing, every &lt;math&gt;3&lt;/math&gt; number from the right is &lt;math&gt;1 + 2 + 3... + n&lt;/math&gt;. So to find the third number from the right on the row of &lt;math&gt;11^{2011}&lt;/math&gt;, &lt;cmath&gt;f(11^n) = 1 + 2 + 3... + (n-1),&lt;/cmath&gt; or &lt;math&gt;\frac{(2010 \cdot 2011)}{2}&lt;/math&gt;, or &lt;math&gt;2021055&lt;/math&gt;. 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 &lt;math&gt;2011&lt;/math&gt;. We must carry the &lt;math&gt;1&lt;/math&gt; in &lt;math&gt;2011&lt;/math&gt;'s tens digit to the &lt;math&gt;5&lt;/math&gt; in &lt;math&gt;2021055&lt;/math&gt;'s unit digit to get &lt;math&gt;\boxed{\textbf{(D) } 6}&lt;/math&gt;. The one at the very end of the row doesn't affect anything, so we can leave it alone.<br /> <br /> <br /> -jackshi2006<br /> <br /> ==Solution 4 (naive solution) ==<br /> <br /> Since we are only looking at the last 3 digits and &lt;math&gt;2011^2&lt;/math&gt; has the same last 3 digits as &lt;math&gt;11^2&lt;/math&gt;, we can find &lt;math&gt;11^{2011}&lt;/math&gt; instead.<br /> After this, we can repeatedly multiply the last 3 digits by 11 and take the last 3 digits of that product. We discover that &lt;math&gt;11^{51}&lt;/math&gt;'s last 2 digits are -11, the same as &lt;math&gt;11^1&lt;/math&gt;. <br /> <br /> From this information, we can figure out &lt;math&gt;11^{11}&lt;/math&gt; and &lt;math&gt;11^{61}&lt;/math&gt; end in 611. Adding various multiples of 50 to the exponent gives us the fact that &lt;math&gt;11^{2011}&lt;/math&gt;'s last digits are 611. We get &lt;math&gt;\boxed{\textbf{(D) } 6}&lt;/math&gt;.<br /> -ThisUsernameIsTaken<br /> <br /> ==See Also==<br /> {{AMC10 box|year=2011|ab=B|num-a=24|num-b=22}}<br /> {{MAA Notice}}</div> Nshree24