# 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 $k < 100$ is the order of 2 modulo 125. Since $k|100$, 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.