Difference between revisions of "2011 AIME I Problems/Problem 11"
(→Solution) |
(→Solution) |
||
Line 4: | Line 4: | ||
== Solution == | == Solution == | ||
Note that the cycle of remainders of <math>2^n</math> will start after <math>2^2</math> because remainders of <math>1, 2, 4</math> will not be possible after (the numbers following will always be congruent to 0 modulo 8). Now we have to find the order. Note that <math>2^{100}\equiv 1\mod 125</math>. The order is <math>100</math> starting with remainder <math>8</math>. All that is left is find <math>S</math> in mod <math>1000</math> after some computation. | Note that the cycle of remainders of <math>2^n</math> will start after <math>2^2</math> because remainders of <math>1, 2, 4</math> will not be possible after (the numbers following will always be congruent to 0 modulo 8). Now we have to find the order. Note that <math>2^{100}\equiv 1\mod 125</math>. The order is <math>100</math> starting with remainder <math>8</math>. All that is left is find <math>S</math> in mod <math>1000</math> after some computation. | ||
− | <cmath>S=2^0+2^1+2^2+2^3+2^4...+2^{ | + | <cmath>S=2^0+2^1+2^2+2^3+2^4...+2^{99}\equiv 2^{100}-1\equiv 8-1\equiv \boxed{007}\mod 1000</cmath> |
== See also == | == See also == | ||
{{AIME box|year=2011|n=I|num-b=10|num-a=12}} | {{AIME box|year=2011|n=I|num-b=10|num-a=12}} |
Revision as of 00:55, 1 May 2011
Problem
Let be the set of all possible remainders when a number of the form , a nonnegative integer, is divided by . Let be the sum of the elements in . Find the remainder when is divided by .
Solution
Note that the cycle of remainders of will start after because remainders of will not be possible after (the numbers following will always be congruent to 0 modulo 8). Now we have to find the order. Note that . The order is starting with remainder . All that is left is find in mod after some computation.
See also
2011 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 10 |
Followed by Problem 12 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |