Find the remainder when the sum of 2^100 + 2^200 + 2^300+

Question

Find the remainder when the sum of  2^{100} + 2^ {200} + 2^ {300}+........+ 2^ {10000}  is divided by 7

A. 0 
B. 2 
C. 1 
D. 6 
E. 5

EvaJager · Accepted Answer

2^{100}=(2^3)^{33}\cdot{2}=(M7+1)\cdot{2}=M7+2  ( M7  denotes multiple of 7).  2^3=8 , which is a  M7+1 .

2^{200}=(2^{100})^2=(M7+2)^{2}=M7+4 .

2^{300}=(2^{100})^3=(M7+2)^{3}=M7+8=M7+1 .

Therefore,  2^{100}+2^{200}+2^{300}=M7+2+4+1=M7 .

The three remainders, 2, 4, and 1, repeat cyclically for the terms in the given sum.
We have 100 terms in the sum ( 10000=100\cdot{100} ), and the last term gives again a remainder of 2.

Answer B.

jns · Answer

2^0 = 1. 1/7 => R=1, R = remainder
2^1 = 2. 2/7 => R=2
2^2 = 4. 4/7 => R=4
2^3 = 8. 8/7 => R=1
2^4 = 16. 16/7 => R=2 .... and the cycle repeats.

We know that the cycle repeats after every 3rd term - 1,2,4,1,2,4.... So, divide the power by 3 to find the number of complete cycles and the remaining powers.
 2^100  = (2^99)*2 = R1*2 = 2. 2/7 => R= 2  -------  (99/3 complete cycles and one 2 left.) 
 2^200  = (2^198)*(2^2) = R1*4 = 4. /7 => R= 4  -------  (198/3 complete cycles and two 2 left.) 
 2^300  = R1. 1/7 => R= 1  -------  (100 complete cycles and no 2 left.) 
Similarly, 2^400 => R=2, 2^500 => R=4, 2^600 => R=1 and the cycle repeats. 2^10000 = (2^9999)*2 => R2.

So,  2^{100} + 2^ {200} + 2^ {300}+........+ 2^ {10000}  in terms of remainders is equal to 2 + 4 + 1 + 2 + 4 + 1 +....... 2
Number of terms in the sequence = 10000/100 = 100 = 99 + 1. Each remainder cycle consists of 3 digits - 2,4,1. There are 99/3 = 33 complete cycles and 1 left out 100th term
Therefore, 2 + 4 + 1 + 2 + 4 + 1 +....... 2 = (2+4+1)*33 + 2 = > 7*33 + 2. On dividing this result by 7,  the remainder is 2 .

LalaB · Answer

my answer is D. is it right?

the thing is 2^100 has 6 as the last digit. 
so, we have multiple 6.as we know 6^n always has 6 as the last digit (where n>0 and n is an integer)

so 6/7 will have the remainder 6

please let me know whether this answer is ok
thnx

EvaJager · Answer

Knowing the last digit of a number is not sufficient to determine what is the remainder when that number is divided by 7.
Compare 6 and 36. Both are divisible by 6, end in 6, but give different remainders when divided by 7.

WoundedTiger · Answer

Hello Bunuel, Karishma
 
Let me know what you think of this approach

Consider : 2^100+2^200+2^300 at first

What is the remainder when (2^100+2^200+2^300)/7

The expression can be written as (2* 2^99+2^2*2^198+2^3*2*297)/7--------> {2*(7+1)^33+ 2^2*(7+1)^66+2^3*(7+1)^99}/7

The remainder for the above expression will be (2*1^33+ 4*(1^66)+8*(1^99)/7 is 0

when you consider the next 3 terms ie. 2^400+2^500+2^600 and simplify the expression the Remainder is still 0 because the sum of the remainder of these terms will (2^4+2^5+2^6 )/7 OR 112/7 AND THUS REMAINDER IS 0

Notice that the remainder in each case is power of 2 and follow the pattern:  (2,4,8) , (16,32,64) ......

Since there are 100 terms in the Original expression therefore the sum of remainder from Term 1 i.e 2^100 to 2^9900 will be divisible by 7 and the remainder for the last term that 2^10000 will be 2^100-------> 2(2^99)-----> 2(7+1)^99/7

Ans is 2

Definitely not a Sub 600 level Q

KarishmaB · Answer

*Removed the solution

EvaJager · Answer

What is the relationship between  2^{100} + 2^{200} + 2^{300} + 2^{400} + ... + 2^{10000}  
and
  ^{100}  ?

Definitely, the two expressions are not equal. As in general,  a^n+b^n
eq{(a+b)}^n , and not for sums with more than two terms.
Are they giving the same remainder when divided by 7? Why? It isn't obvious to me.
So, what is that different method that you are mentioning?

In the above solution (WoundedTiger), in the second step, we can write  2^{400}+2^{500}+2^{600}=2^{300}(2^{100}+2^{200}+2^{300}) .
The expression in the parenthesis is divisible by 7 (was proven in the first step), so the remainder is 0.
The remainders cannot be greater than 7, therefore is not correct to say they are 16, 32, 64. In fact, they are 2, 4 and 1,
as  16 = 2 * 7 + 2 ,  32 = 4 * 7 + 4 ,  64 = 9 * 7 + 1 .
The process can be continued by grouping three terms each time and taking out an appropriate factor ( 2^{600},2^{900}...) 
We are left to determine the remainder given by the last term when divided by 7.

KarishmaParmar · Answer

Solved this in one minute. Just remember to use the concept explained @ quarter-wit-quarter-wisdom-a-remainders-post-for-the-geek-in-you and half of the remainder Qs become a piece of cake

All the terms in the expression (a+b)^z are divisible by a except b^z (8=7+1) Make the modifications in the expression so that it is in some relation with the given divisor (usually plus or minus 1) 2^100 = 2* 8^33 = 2* (7+1)^33 2^200 = 4* 8^66 = 4* (7+1)^66 2^300 = 1* 8^100 = 1* (7+1)^100 2^400 = 2* 8^133 = 2* (7+1)^133 2^500 = 4* 8^166 = 4* (7+1)^166 2^600 = 1* 8^200 = 1* (7+1)^200 Observer that this it is a repeat cycle of 2, 4 and 1 Make a note of total number of terms = 100 remainder from first term = 2*1 remainder from second term = 4*1 remainder from third term = 1*1 Sum of first three remainders = 7. Remainder =0 .Sum of first 99 remainders = 7*33 Remainder =0 . Remainder on the 100th term = 2 (from the cycle) Answer B Though I sound pretty confident I need someone to validate the method :oops:

Thanks!

vitaliyGMAT · Answer

Cyclicity is a good approach but modular arithmetic will help us to solve this question a little bit faster.

We have:

\frac{2^{100} + 2^{200} + 2^{300} + 2^{400} + … + 2^{10000}}{7}

2^3 = 1 (mod _7)

2^{100} = 2^{99}*2 = (2^3)^{33}*2 = 1^{33}*2 = 2

2^{100} + 2^{200} + 2^{300} + 2^{400} + … + 2^{10000} = (2^{100})^1 + (2^{100})^2 + (2^{100})^3 + … + (2^{100})^{100}

In mod 7 this is the same as:

\frac{2 + 2^2 + 2^3 + 2^4 + 2^5 + … + 2^{100}}{7}  where the nominator is the sum of geometric progression.

\frac{2*(2^{100}-1)}{(2-1)*7} = \frac{2*(2^{100}-1)}{7}

But we already know that  2^{100} = 2 (mod_7)

And our expression boils down to:

\frac{2*(2-1)}{7} = \frac{2}{7}

Our remainder is  2 .

Answer B.

JS1290 · Answer

chetan2u   Bunuel   niks18   VeritasPrepKarishma

Hi,
I was wondering if one of you experts could please check my work? I was able to get to the right answer in under 2 mins but I am not entirely positive if my way is correct. I simply took the first term and last term and added them together to get the final equation as:

(2^100+2^10000)/7 - (2^100(1*2^9900))/7 - 2^100/7= Remainder of 2 & 2^9900/7= Remainder of 1. I then multiplied the remainders together (2*1)/7 to finally get a remainder of 2.

Please let me know if my way was correct? Would greatly appreciate it!

niks18 · Answer

Hi  csaluja ,

At first I could not understand your logic for adding the two extremes. Also the highlighted portion is incorrect. if you take 2^100 out then the expression will be 2^100(1+something)

Note that this is a GP(geometric series) and formula to find sum of GP series  =\frac{a_1(r^n-1)}{(r-1)} , where  a_1= first term,  r=  common ration =\frac{a_2}{a_1}  and  n= number of terms

Also note that  \frac{2^{100}}{7}=\frac{(2^3)^{33}*2}{7}=\frac{8^{33}*2}{7} , Now 8 leaves a remainder of 1 when divided by 7 and 2 leaves a remainder of 2

=>remainder = 1^{33}*2=2

Similarly  2^{200}=(2^{100})^2 , remainder for this term will be  (2)^2

So we will have new G.P series of REMAINDERS
 
 2 + 2^2 + 2^3 +......+ 2^{100} 
 
Sum of the remainders:  S_n = \frac{a(r^n - 1)}{r-1} , where  a=2; r=2, n=100

S_{100}=\frac{2(2^{100} - 1)}{(2-1)} =>2(2^{100} - 1)=2^{101}-2

Hence  Remainder = \frac{(2^{101}-2)}{7}=\frac{ }{7}-\frac{2}{7}

or,  remainder= \frac{8^{33}*4}{7}-\frac{2}{7} =1^{33}*4-2=4-2=2

Find the remainder when the sum of 2^100 + 2^200 + 2^300+

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

Find the remainder when the sum of 2^100 + 2^200 + 2^300+

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards