What is the remainder when 2^256 is divided by 17

Question

What is the remainder when  2^{256}  is divided by 17

A. 1
B. 7
C. 11
D. 13
E. 15

Find the remainder of 2^256 divided by 17

a)1
b)7
c)11
d)13
e)15

BrushMyQuant · Accepted Answer

We need to find what is the remainder when  2^{256}  is divided by 17

2^{256}  =  2^{4*64}  =  (2^4)^{64}  =  16^{64}  =  (17 - 1)^{64}

using binomial theorem if we open this then all terms except the last term will be a multiple of 17 => Remainder of all the terms except the last term with 17 will be zero

=> Remainder will be same as the remainder of the last term =  (-1)^{64}  = Remainder of 1 by 17 = 1

So,  Answer will be A 
Hope it helps!

Playlist on Solved Problems on Remainders  here

Watch the following video to MASTER Remainders

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

yashikaaggarwal · Answer

Using Euler theorem,

When A^x is divided by N, where A and N are coprime.
Since N here has 17 as a prime factor (p)
Ø(n) = n(1-1/p)
Ø(17) = 17(1-1/17)
Ø(17) = 17*(16/17)
Ø(17) = 16

So A^Ø(n) mod n = 1 as the remainder
2^16 mod 17 = 1
(2^16)16 mod 17 = 1
1 mod 17
1 as remainder

Answer is A

TarunKumar1234 · Answer

To get remainder when 2^256 is divided by 17 we need to get close to 17, in +-1 range. /17 or, /17 or, (-1)^64/17, So remainder will (-1)^64 = 1, I think A.

HRX273 · Answer

Does this Euler theorem work in this type of questions please let me know .....

Krunaal · Answer

Please go through the thread, this problem has been solved using  Euler's theorem

sherlocked221B · Answer

An alternate approach that worked for me in these questions is Pattern Recognition:

2^1 = 2 --> Divided by 17,  Remainder = 2  ( 2^1) 
2^2 = 4 --> Divided by 17,  Remainder = 4  ( 2^2) 
2^3 = 8 --> Divided by 17,  Remainder = 8  ( 2^3) 
2^4 = 16 --> Divided by 17,  Remainder = 16  ( 2^4) 
2^5 = 32 --> Divided by 17,  Remainder = 15  ( 17-2^1 )
2^6 = 64 --> Divided by 17,  Remainder = 13  ( 17-2^2 )
2^7 = 128 --> Divided by 17,  Remainder = 9  ( 17-2^3 )
2^8 = 256 --> Divided by 17,  Remainder = 1  ( 17-2^4 )

2^9=512 --> Divided by 17, Remainder = 2, the pattern repeats! Cyclicity of 8.

256/8 = 0, therefore the 8th term in the cyclicity, that is Remainder = 1 is the answer.

What is the remainder when 2^256 is divided by 17

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

What is the remainder when 2^256 is divided by 17

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