2011 AIME I Problems/Problem 11

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$

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

Page

Toolbox

Search

2011 AIME I Problems/Problem 11

Problem

Solution

See also