Given 1 + 2 + 2^2 + 2^3 + …….. + 2^{40} = N, what is the remainder whe

Question

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

CareerGeek · Accepted Answer

N = sum of n terms of Geometric Progression = 1(2^41 - 1)/(2 - 1) = 2^41 - 1

Adjust 2^41 as 4*2^39
= 4*8^13
= 4*(9 - 1)^13
= 4*(9K - 1)
= 9L - 4, for some integer L

So, N = 2^41 - 1 = 9L - 5 = 9M + 4, for some integer M

Remainder when divided by 9 = 4

IMO Option B

Posted from my mobile device

Sithara286 · Answer

(1+2)+2^2(1+2)+2^4(1+2)+…2^38(1+2)+2^40
=(1+2) +2^40
=(1+2) +2^40
= 3×9×{k} +2^40
Since 9 is already a factor of the first part, we need to figure out the remainder when 2^40 is divided by 9.
With the help of cyclicity, units place of 2^40 is 6 . Hence the answer is D.

Posted from my mobile device

firas92 · Answer

Dillesh4096 
Can you please explain the highlighted part?

CareerGeek · Answer

firas92

So, (x - 1)^n will always end in +1 or -1.

+1 —> if n is even (eg: (x - 1)^2 = x^2 - 2x + 1 = x(x-2) + 1 = xK + 1, for some integer K)

-1 —> if n is odd (eg: (x - 1)^3 = x^3 - 3x^2 + 3x - 1 = x(x^2 - 3x + 3) - 1 = xK- 1, for some integer K.

This is applicable for any higher powers of even and odd.

Hope it’s clear.

ArtyomYom · Answer

My approach based on grouping of terms:
1 + 2 + 2^2 + 2^3 + 2^4 + 2^5 = 63 
63/9 = 7

2^6*(1 + 2 + 2^2 + 2^3 + 2^4 + 2^5) = 2^6*63 - also divisible by 9

The last possible group that is devided by 9 without remainder is:

2^29*(1 + 2 + 2^2 + 2^3 + 2^4 + 2^5 ) = 2^32*63

So, we have:
 2^36 + 2^37 + 2^38 + 2^39 + 2^40 
When we need to divide this on 9 to get the answer
2^36*(1 + 2 + 4 + 8 + 16) = 2^36*31

31/9 = 3  4 /9

Answ 4

vinayakvaish · Answer

My approach in these kind of questions is to modify the stem so I may apply remainder theorem efficiently.

realize that the given sum is nothing but 2^41-1
N=2^41-1
N+1=2^41
N+1= 2^39. 2^2
(N+1)= (2^3)^13. 4

Applying remainder theorem: 
(N+1)/9= {(8^13)*4}/9
(-1)^13*4
=-4

Since remainders cant be negative, -4+9=5

For N+1 remainder is 5 so for N, the remainder must be 5-1=4

SPatel1992 · Answer

Can you explain the last piece in depth?

Shrey9 · Answer

Guys I used a different approach.
 experts let me know, if it can be true..

1 + 2 + 2^2 + 2^3 + …….. + 2^{40}  = N
add the terms one before the first multiple of 9..
1+2+4+8+16 .... = 31 .. now divide it by 9 i.e. 31/9 ; Remainder = 4

NOTE - if you add the next term 2^5 = 32 to 31, the answer will be 63, the first multiple of 9 in the list..
so we stop at 31.. and hence B is the answer..

Fdambro294 · Answer

Concept 1: you can Split the Terms and Add the Remainders, removing the Excess Remainders at the end by Dividing by 9 again.
(1/9) Remainder + (2/9) Remainder + (4/9) Remainder ..... + (2^40 / 9) Remainder = Total Excess Remainder

1st) Need to find the Remainder Pattern when Consecutive Powers of 2 are Divided by 9

1/9 ----- Rem = 1
2/9 ----- Rem = 2
4/9 ----- Rem = 4
8/9 ----- Rem = 8 
16/9 ----- Rem = 7
32/9 ----- Rem = 5
64/9 ----- Rem = 1
128/9 ---- Rem = 2
 pattern keeps repeating for every 6

Remainder Pattern   = 27

There are 41 Terms from 1 up thru 2^40

This Remainder Pattern will repeat 6 Times (6 * 6 = 36). And there will be 5 more Remainders that must be added from the Pattern.

Total Added Excess Remainders = 6 * (27) +

Remove the Total Excess Remainder by Dividing by 9 until you get to a Remainder < the Divisor of 9.

(6 * 27) / 9 ---- Remainder = 0

= 22

22/9 --- Remainder = 4

Answer B

IanStewart · Answer

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.

hiranmay · Answer

Given  1 + 2 + 2^2 + 2^3 + …….. + 2^{40}  = N, what is the remainder when N is divided by 9?

A. 3
B. 4 -->    correct   
C. 5
D. 6
E. 7

Solution :
 1 + 2 + 2^2 + 2^3 + …….. + 2^{40} = N = (2^{41}-1)/(2-1)=2^{41}-1 
 
(2^1-1)%9=1%9=1
(2^2-1)%9=3%9=3
(2^3-1)%9=7%9=7
(2^4-1)%9=15%9=6
(2^5-1)%9=31%9=4 <-- 
(2^ 6 -1)%9=63%9=0
(2^7-1)%9=127%9=1
(2^8-1)%9=255%9=3
(2^9-1)%9=511%9=7
....
....
 
cyclicality of 6 i.e. the pattern repeat after 6
 (2^{41}-1)%9=(2^{6*6+5}-1)%9 --> 5th one from the cycle is 4 
So the remainder when N is divided by 9 is 4
 Answer: B

Posted from my mobile device

danbrown9445 · Answer

Another simple way:
The given series is Geometric progression with a = 1,r = 2,n = 41
Sum of terms of GP is given by:
 S = \frac{a(r^n-1)}{(r-1)} 
 S = \frac{1(2^{41}-1)}{(2-1)} 
 S = 2^{41} - 1

Now 2^6 will given remainder of 1 when divided by 9.Rewriting 2^41 in the form 2^6m
 S = 2^{36}*2^5 - 1 
 S = 64^6*32 - 1

64^6 will leave remainder of 1^6 when divided by 9"
 1^6*32 - 1 
 31  divided by 9 gives remainder 4

BrushMyQuant · Answer

1 + 2 + 2^2 + 2^3 + ......... + 2^{40} = N

This is a Geometric Series with First term, a = 1 and common ratio ,r as 2 and number of terms n as 41.  2^0  to  2^{40}  ] 
 Watch this video to learn about Geometric Series  ]

Using Sum formula for Geometric Series

S_{n} = a*\frac{((𝒓^𝒏 − 𝟏)}{(𝐫−𝟏))}

N =  1*\frac{((2^{41} − 𝟏)}{(2−𝟏))}  =  2^{41}  - 1

Now, we need to find remainder of  2^{41}  - 1 by 9

We can do this by  finding out the cycle of remainder of power of 2 by 9   Watch this video to learn this trick  ]
 2^1  by 9 remainder is 2
 2^2  by 9 remainder is 4
 2^3  by 9 remainder is 8
 2^4  by 9 remainder is 7
 2^5  by 9 remainder is 5
 2^6  by 9 remainder is 1  
 2^7  by 9 remainder is 2

So, we need to divide the power of 2 by 6 (the cycle) and check the remainder
 41/6  remainder is 5
=>  2^{41}  will give the same remainder by 9 as  2^5 
=> Remainder of  2^{41}  by 9 is 5
Remainder of -1 by 9 will be 8

So, total remainder of  2^{41}  - 1 by 9 = 5 + 8 =13. This cannot be more than 9 so need to divide again by 9 to get final remainder as
 13/9  = 4

Hence,  Answer will be B 
Hope it helps!

Video on Sequences

https://www.youtube.com/watch?v=EfNT2JoE5CM

rvgmat12 · Answer

The sum of 1+2 + ... + 2^n = 2^(n+1) - 1

1+2 = 3 = 2^2 - 1
1+2+ 2^2 = 2^3 - 1

Need to find remainder when 2^41 - 1 is divided by 9

(2^3)^13.2^2 - 1 = (-1)^13*4 mod 9 -1 = 4

JyotiChauhan · Answer

Could you please help me with the theorem?

hellothere88 · Answer

So, N = 2^41 - 1 = 9L - 5 = 9M + 4, for some integer M

how does it become N = 9M + 4 from N = 9L - 5?

hadimadi · Answer

Hi,

according to the finite geometric series formula we get:

2^41-1

We also know that (x+y)^n is always divisible by x with the remainder being the remainder of y^n/x -> (9-1)^n is divisible by 9 with remainder 8 for an odd n, and remainder 1 for an even n. This is can be proven by the binomial expansion theorem, in which each term in the expansion contains the 9 (or in the more general form, the x-term). We simplify to reach something with an 8 to the power of something in order to apply the above:

2^41-1
=4*2^39-1
=4*8^13-1
=4*(9-1)^13-1
=4*(M9-1)-1
=M'9-4-1
=M'9-5, where M' denotes a multiple of 9

Since we deduct 5 from the multiple of 9, the remainder must be 4, hence (B)

No gurantees

As always, a very cool question Nick!

bumpbot · Answer

Automated notice from GMAT Club BumpBot:

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

This post was generated automatically.

Given 1 + 2 + 2^2 + 2^3 + …….. + 2^{40} = N, what is the remainder whe

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

Given 1 + 2 + 2^2 + 2^3 + …….. + 2^{40} = N, what is the remainder whe

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