Difference between revisions of "2011 AIME I Problems/Problem 11"
AlphaMath1 (talk | contribs) (→Solution 1) |
AlphaMath1 (talk | contribs) m (→Solution 1) |
||
| Line 2: | Line 2: | ||
Let <math>R</math> be the set of all possible remainders when a number of the form <math>2^n</math>, <math>n</math> a nonnegative integer, is divided by <math>1000</math>. Let <math>S</math> be the sum of the elements in <math>R</math>. Find the remainder when <math>S</math> is divided by <math>1000</math>. | Let <math>R</math> be the set of all possible remainders when a number of the form <math>2^n</math>, <math>n</math> a nonnegative integer, is divided by <math>1000</math>. Let <math>S</math> be the sum of the elements in <math>R</math>. Find the remainder when <math>S</math> is divided by <math>1000</math>. | ||
| − | == 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^{102}\equiv 2^{103}-1\equiv 8-1\equiv \boxed{007}\mod 1000</cmath> | <cmath>S=2^0+2^1+2^2+2^3+2^4...+2^{102}\equiv 2^{103}-1\equiv 8-1\equiv \boxed{007}\mod 1000</cmath> | ||
Revision as of 12:51, 19 March 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.
![\[S=2^0+2^1+2^2+2^3+2^4...+2^{102}\equiv 2^{103}-1\equiv 8-1\equiv \boxed{007}\mod 1000\]](http://latex.artofproblemsolving.com/f/a/7/fa77af8fb28095751a3d98274f92096eb114bf8c.png)
