What is the remainder when 2^1344452457 is divided by 11?

Question

What is the remainder when  2^{1344452457}  is divided by 11?

A. 2
B. 4
C. 5
D. 7
E. 9

CareerGeek · Accepted Answer

2^{1344452457}

We can write 1344452457 = 5k + 2, for some odd integer k
-->  2^{1344452457}  
-->  2^{5k + 2} 
--> 4* 2^{5k} 
--> 4* 32^k 
--> 4* (33 - 1)^k

Since, k is an odd integer  (33 - 1)^k  will be of the form 11A - 1 or 11B + 10, for some positive integers A or B
-> 4* (33 - 1)^k  = 4*(11B + 10) = 44B + 40

Remainder when 44B + 40 is divided by 11 is 7

IMO Option D

TestPrepUnlimited · Answer

We would like to use the theorem  x^n  % 11 =  (x - 11i)^n  % 11 where  i  is any integer and make  x - 11i  either 1 or -1 to evaluate the remainder (x % 11 means the remainder of x/11). To do that we must change the base of the exponent close to a multiple of 11. The closest one, for now, is  2^5 = 32 . So let us try to change the base to 32 and subtract 33.

2^{1344452457} = 2^2 * 2^{1344452455} = 2^2 * 2^{5 * n} = 2^2 * 32^n . Here n represent the result of 1344452455/5 which is trivial.

One thing to note here is that n must be odd since the original exponent ends in 5. Then we can do the following:

2^2 * \frac{{32^n}}{11} = 4 * \frac{{32^n}}{11}

If we focus on  \frac{{32^n}}{11}  we have:

32^n  % 11 =  (-1)^n  % 11 = -1 % 11 (since n is odd) = -1.

Finally we multiply that by 4 to get -4 is the remainder, or -4 + 11 = 7 is the remainder. The answer is D.

gvij2017 · Answer

I wrote 1344452457= 4K+1
 So it becomes 2*2^(4*k)= 2*16^k
Reminder(16^K/11) = 5
And reminder of 2/11= 2
Therefore, 5*2= 10

Where I am wrong?

nick1816 · Answer

2^5 = -1 mod 11
 (2^5)^{odd} =  (-1)^{odd}  mod 11

(2^5)^{odd} * 2^2 = -1*4 mod 11

1344452457= 5*odd+2
 2^{1344452457} =-4 mod 11=7 mod 11

mandy0rhtdm · Answer

2^1 % 11 = 2
2^2 % 11 = 4 
-
-
-
-
2^10 = 1024 % 11 = 1

make power a multiple of 10 so we have 2^(10K + 7 )

Remainder from 2^10K = 1
remainder from 2^7 = 7
Hence answer.

EncounterGMAT · Answer

The easiest and quickest way to solve this question is by pattern by using the formula=> dividend = divisor x quotient + remainder 2^1= 11(0) + 2 =>r=2 2^2= 11(0) + 4 =>r=4 2^3= 11(0) + 8 =>r=8 2^4= 11(1) + 5 =>r=5 2^5= 11(2) + 10 =>r=10 2^6= 11(5) + 9 =>r=9 2^7= 11(11) + 7 =>r=7 2^8= 11(23) + 3=>r=3 2^9= 11(46)+6=>r=6 2^10= 11(93)+1=>r=1 2^11= 11(186)+2=>r=2 2^12= 11(372)+4=>r=4 .... .... .... Notice the cyclicity of 10 starts at 2^11.....which means remainder for 2^(any number ending with 7) will be 7. Hence, option D P.S: This method might seem lengthy. I am aware of the values till 2^10 which made my calculations easier. If you are quick at calculations (calculation with 2 is very quick and simple) and approximation, then this method will be the best choice (at a point I was really pissed off while calculating cyclicity....if this happened in exam, I would have chosen an remainder of 2^7 and moved on

-_- )

MDUsman · Answer

Quick way is the use of Totient formula for finding out the remainder.

Vibhatu · Answer

We can use farmats little theorem.

2 is prime number and 11 is also prime we can use this theorem. 
no of co prime of 11= 10
we have to divide 1344452457 by 10 and getting reminder 7
then we cann say 2^k*2^7
applying binomial 2^k/11= 1
2^/11= reminder is 7
answer: D

vineet6316 · Answer

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

Adit_ · Answer

This problem is equivalent to 2^7 mod 11 = 128 mod 11 = 7.
Answer:  Option D

egmat · Answer

The key idea here is that powers of  2 , when divided by  11 , follow a  repeating pattern . Let's find that pattern.

Step 1:  Find the cycle of remainders when powers of  2  are divided by  11 .

2 ^ 1  =  2  → remainder  2 
 2 ^ 2  =  4  → remainder  4 
 2 ^ 3  =  8  → remainder  8 
 2 ^ 4  =  16  → remainder  5 
 2 ^ 5  =  32  → remainder  10 
 2 ^ 6  =  64  → remainder  9 
 2 ^ 7  =  128  → remainder  7 
 2 ^ 8  =  256  → remainder  3 
 2 ^ 9  =  512  → remainder  6 
 2 ^ 10  =  1024  → remainder  1

At  2 ^ 10 , the remainder is  1 . This means the pattern repeats every  10  powers. (Because  2 ^ 11  =  2 ^ 10  ×  2 , and since  2 ^ 10  gives remainder  1 , multiplying by  2  gives remainder  2  again — right back to the start.)

Step 2:  Figure out where  1344452457  falls in the cycle.

Since the cycle repeats every  10 , we just need the remainder when  1344452457  is divided by  10 . That's simply the last digit of the number, which is  7 .

So  2 ^ 1344452457  has the same remainder as  2 ^ 7 .

Step 3:  From our table above,  2 ^ 7  =  128 , and  128  ÷  11  =  11  ×  11  +  7 .

The remainder is  7 .

Answer: D

General principle:  When asked for remainders of huge powers, always find the  repeating cycle of remainders  first. Then reduce the exponent using that cycle length. For any prime p, the cycle of remainders when dividing powers of a number by p will repeat within at most p -  1  steps.

What is the remainder when 2^1344452457 is divided by 11?

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^1344452457 is divided by 11?

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