nick1816 wrote:
Given \(1 + 2 + 2^2 + 2^3 + …….. + 2^{40}\) = N, what is the remainder when N is divided by 9?
A. 3
B. 4
C. 5
D. 6
E. 7
There are several good ways to answer the question, many of them posted above, so I'll just post an alternative method that I don't see earlier in this thread: notice that 1 + 2^3 = 9. So if we take any two terms in our list that are three apart and add them, we'll always get a multiple of 9 -- for example, 2^40 + 2^37 = 2^37(2^3 + 1) = (9)(2^37). So if you rewrite the last six terms of the sum this way:
(2^35 + 2^38) + (2^36 + 2^39) + (2^37 + 2^40)
we're just adding multiples of 9, and thus getting a multiple of 9. But that happens in any string of six consecutive terms. So the sum of the terms from 2^35 through 2^40 is a multiple of 9, as is the sum from 2^29 through 2^34, and so on. Working backwards, we discover that the sum of the terms from 2^5 up to 2^40 is a multiple of 9 (since we have six complete 'blocks' of six terms from 2^5 through 2^40 inclusive, and each 'block' adds to a multiple of 9).
That leaves us just with the sum 1 + 2 + 2^2 + 2^3 + 2^4, and since 1+2^3 and 2+2^4 are multiples of 9, the only term left is 2^2 = 4, and the sum of all the terms is thus 4 greater than a multiple of 9, which means the remainder is 4 when we divide by 9.
_________________
GMAT Tutor in Montreal
If you are looking for online GMAT math tutoring, or if you are interested in buying my advanced Quant books and problem sets, please contact me at ianstewartgmat at gmail.com