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

\(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 [Since, 44B + 40 = 11(4B + 3) + 7]

IMO Option D

Pls Hit Kudos if you like the solution

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

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?

\(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

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.

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 -_- )

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

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.
_________________