Just see what are the remainders
1+2+4 - 0
1+...+8 - 1
1+...+16 - 3
1+...+32 - 0
1+...+64 - 1
1+...+128 - 3
etc. can be proved by by induction
it's 0 for sum up to 2^2, 2^5, 2^8, ...
it's 1 for sum up to 2^3, 2^6, 2^9, ...
it's 3 for sum up to 2^4, 2^7, 2^10, ...
So, we need to find a reminder of 1000-2 on 3 and get the result.
Now since 1000-2 = 998 and 998/3 = 3*332+2, then answer is 3 (D).
Still More Remainders
This topic has expert replies
Source: Beat The GMAT — Problem Solving |
-
sureshbala
- Master | Next Rank: 500 Posts
- Posts: 319
- Joined: Wed Feb 04, 2009 10:32 am
- Location: Delhi
- Thanked: 84 times
- Followed by:9 members
Given number is
2^0+2^1+2^2+....+2^1000. This is a GP with 1001 terms.
So the above sum = 2^0(2^1001 - 1)/(2 - 1) = 2^1001 - 1
Hence we need the remainder when 2^1001 - 1 is divided by 7.
2^1001 - 1 = (2^3)^333 X 2^2 - 1
Since 2^3 leaves a remainder 1 when divided by 7, the remainder of the above number when divided by 7 will be 4 - 1 = 3
2^0+2^1+2^2+....+2^1000. This is a GP with 1001 terms.
So the above sum = 2^0(2^1001 - 1)/(2 - 1) = 2^1001 - 1
Hence we need the remainder when 2^1001 - 1 is divided by 7.
2^1001 - 1 = (2^3)^333 X 2^2 - 1
Since 2^3 leaves a remainder 1 when divided by 7, the remainder of the above number when divided by 7 will be 4 - 1 = 3
Cool. But you could have shorten for time. The first few sums arevitaly wrote:Just see what are the remainders
1+2+4 - 0
1+...+8 - 1
1+...+16 - 3
1+...+32 - 0
1+...+64 - 1
1+...+128 - 3
etc. can be proved by by induction
it's 0 for sum up to 2^2, 2^5, 2^8, ...
it's 1 for sum up to 2^3, 2^6, 2^9, ...
it's 3 for sum up to 2^4, 2^7, 2^10, ...
So, we need to find a reminder of 1000-2 on 3 and get the result.
Now since 1000-2 = 998 and 998/3 = 3*332+2, then answer is 3 (D).
1 +2 + 4+ 8 +.....
1/7 Remaider is 1
3/7 remainder is 3
7/7 Remainder is 0, Go one more to test induction
15/7 remainder is 1 Stop.
For every 3 numbers the pattern repeats. There are 1001 numbers
1001/3=333 remainder 2.
You are at the 333th number. This ends in 0 according to induction. your next move has remainder 1 and the final has remainder 3. Choose D.
Alternatively. Every three consecutive terms are of the form.
2^j +2^(j+1) +2^(j+2)
2^j(1+2+4)
2^j (7)
So 7 is a factor of every 3 consecutive terms. There are 333 of such terms, beginning with 2^2, totalling 999. We are left with 2^0+ 2^1, and this has to be the remainder.
