Difference between revisions of "2011 AMC 10B Problems/Problem 23"
m (→Solution 3) |
m (→Solution 2) |
||
| Line 23: | Line 23: | ||
== 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> | ||
Revision as of 13:23, 11 August 2020
Problem
What is the hundreds digit of 
Solution 1
Since 
we know that 
To compute this, we use a clever application of the binomial theorem.
In all of the other terms, the power of 
is greater than 
and so is equivalent to 
modulo 
which means we can ignore it. We have:
Therefore, the hundreds digit is 
Sidenote: By Euler's Totient Theorem, 
for any 
, so 
and 
. We can then proceed using the clever application of the Binomial Theorem.
Solution 2
We need to compute 
By the Chinese Remainder Theorem, it suffices to compute 
and 
In modulo 
we have 
by Euler's Theorem, and also 
so we have ![\[2011^{2011} = (2011^4)^{502} \cdot 2011^3 \equiv 1^{502} \cdot 3^3 \equiv 3 \pmod{8}.\]](http://latex.artofproblemsolving.com/0/0/0/0005cb6d3a60d8bfe27bc0ad83d3686a04cb0ff2.png)
In modulo 
we have 
by Euler's Theorem, and also 
Therefore, we have 
After finding the solution 
we conclude it is the only one by the Chinese Remainder Theorem. Thus, the hundreds digit is
Solution 3
Notice that the hundreds digit of 
won't be affected by 
. Essentially we could solve the problem by finding the hundreds digit of 
. Powers of 
are special because they can be represented by the Pascal's Triangle. Drawing the triangle, there is a theorem that states the powers of 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 
and 
. Adding all numbers from right to left, we get 
, which is also 
. In other words, each number is 
steps from the right side of the row. The hundreds digit is . We can do the same for , but we only need to find the digits from the right. Observing, every number from the right is 
. So to find the third number from the right on the row of , ![\[f(11^n) = 1 + 2 + 3... + (n-1),\]](http://latex.artofproblemsolving.com/1/c/0/1c090e87561137083ac8bedce48c9e982251de82.png)
or 
, or 
. 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 
. We must carry the in 's tens digit to the 
in 's unit digit to get 
. The one at the very end of the row doesn't affect anything, so we can leave it alone.
-jackshi2006
See Also
| 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 | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
