Problem:
Let R be the set of all possible remainders when a number of the form 2n,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:
The numbers 20=1,21=2, and 22=4 are all elements of R. Because 2n is divisible by 8 for n≥3, all other elements of R are multiples of 8. Note that 210+1=1025≡0(mod25), so 250+1=(210+1)(240−230+220− 210+1)=(210+1)((240−1)−(230+1)+(220−1)−(210+1)+5)≡0 (mod125). Furthermore, 2n≡0(mod8) implies 2n(250+1)=2n+50+ 2n≡0(mod1000) for all n≥3. Because 500 is not in R, the multiples of 8 occur in pairs whose remainder modulo 1000 sum to 1000. Therefore the requested remainder is 1+2+4=7.
The problems on this page are the property of the MAA's American Mathematics Competitions