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

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

(1+2)+2^2(1+2)+2^4(1+2)+…2^38(1+2)+2^40
=(1+2)[1+2^2+2^4+2^6+..+2^38]+2^40
=(1+2)[(1+2)^2{1+2^2+2^6+..+2^36}]+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

Dillesh4096
Can you please explain the highlighted part?
_________________

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.

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

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

Can you explain the last piece in depth?

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

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 [1 + 2 + 4 + 8 + 7 + 5] = 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) + [1 + 2 + 4 + 8 + 7]

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

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

[1 + 2 + 4 + 8 + 7] = 22

22/9 --- Remainder = 4

Answer B

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

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

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

\(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 [ Since we got 1 so it will repeat from next one ]
\(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 [-1 +9 = 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


_________________

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

Could you please help me with the theorem?

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

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

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!