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^{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^{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 $R$ be the set of all possible remainders when a number of the form $2^n$, $n$ a nonnegative integer, is divided by $1000$. Let $S$ be the sum of the elements in $R$. Find the remainder when $S$ is divided by $1000$.

Solution

Note that the cycle of remainders of $2^n$ will start after $2^2$ because remainders of $1, 2, 4$ 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 $2^{100}\equiv 1\mod 125$. The order is $100$ starting with remainder $8$. All that is left is find $S$ in mod $1000$ after some computation. \[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\]

See also

2011 AIME I (ProblemsAnswer KeyResources)
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
Invalid username
Login to AoPS