Still More Remainders

[dtweah]

What is the remainder when A= 2^0+2^1 +....+2^1000 is divided by 7

A. 0

B. 1

C. 2

D. 3

E. 4

[vitaly]

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).

[sureshbala]

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

[dtweah]

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).

Cool. But you could have shorten for time. The first few sums are

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.