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 $x \equiv y \pmod{1000} \Leftrightarrow x \equiv y \pmod{125}$ and $x \equiv y \pmod{8}$ . So we must find the first two integers $i$ and $j$ such that $2^i \equiv 2^j \pmod{125}$ and $2^i \equiv 2^j \pmod{8}$ and $i \neq j$ . Note that $i$ and $j$ will be greater than 2 since remainders of $1, 2, 4$ will not be possible after 2 (the numbers following will always be congruent to 0 modulo 8). Note that $2^{100}\equiv 1\pmod{125}$ (see Euler's theorem) and $2^0,2^1,2^2,\ldots,2^{99}$ are all distinct modulo 125 (proof below). Thus, $i = 3$ and $j =103$ are the first two integers such that $2^i \equiv 2^j \pmod{1000}$ . All that is left is to find $S$ in mod $1000$ . After some computation: $S = 2^0+2^1+2^2+2^3+2^4+...+2^{101}+ 2^{102} = 2^{103}-1 \equiv 8 - 1 \mod 1000 = \boxed{007}.$ To show that $2^0, 2^1,\ldots, 2^{99}$ are distinct modulo 125, suppose for the sake of contradiction that they are not. Then, we must have at least one of $2^{20}\equiv 1\pmod{125}$ or $2^{50}\equiv 1\pmod{125}$ . However, writing $2^{10}\equiv 25 - 1\pmod{125}$ , we can easily verify that $2^{20}\equiv -49\pmod{125}$ and $2^{50}\equiv -1\pmod{125}$ , giving us the needed contradiction.

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