I wouldn’t say there is an easier way as such and may be you would get some more friendly terms than 99.

Having said that, you can ease it logically by seeing that all choices are 17 or less, so when you divide by 33 too, the remainder should be same.

Now \(2^{99}=(2^5)^{19}*2^4=32^{19}*2^4\)
Now 32 will leave -1 as remainder
So remainder = \((-1)^{19}*16=-1*16=-16\), or \(33-16=17\)

OR

What will be the remainder when 2^99 is divided by 9, a factor of 99
\(2^{99}=(2^3)^{33}=8^{33}\)
8 will leave a remainder 1, so \(R=(-1)^{33}=-1\) or \(9-1=8\)..
Since we are looking for remainder with 99, remainder can be anything in the form \(9k+8\)
So answer will be one of 8,17,23...
Only 17 is there so our answer must be 17


A point on one of the solution that since 99=3*3*11, so remainder =3+3+11 is WRONG.
As there are kudos given to solution, don’t take it as a correct method.
The solution doesn’t even talk of 2^99, so anything 2^3 or 2^13 or 5^1 and so on will give 17 as answer

I would find the remainders on division by 9 and 11 separately first.

\(2^{99} = 8^33 = (9 - 1)^33\)
On division by 9, it will leave remainder (-1) which is same as remainder 8.

\(2^{99} = 2^4 * 2^{95} = 16 * (32)^{19} = 16 * (33 - 1)^19\)
On division by 11, it will leave remainder -16 which is same as -5 which is same as 6.

So the number upon division by 9 leaves remainder 8 and upon division by 11 leaves remainder 6. This is now our remainders question.
The first such number will be 17. So upon division by 99, remainder will be 17.

Answer (A)
_________________

What is the remainder when \(2^{99}\) is divided by 99?

—> \(2^{99}= 2^{3*33}= 8^{33}\)

—> \(8^{33}= 8^{3*11}= 512^{11}\)

—> \(512^{11}= (5*99+ 17)^{11}\)

Now, we need to find out the remainder when \(17^{11}\) is divided by 99.

—> \(17*17^{10}= 17* 289^{5}\)

\(= 17(3*99 —8)^{5}\)

\(=17(297^{5}+....—8^{5})\)

\(=17( 99m —8^{5})\)

\(=17(99m—32768)\)

\(=17(99m —(99*331–1))\)

\(=(17*99m—99*331+ 17)/ 99\)

—> the remainder will be 17

The answer is A

Posted from my mobile device

giving a try
for 2^15 gives remainder of 1 when divided by 99
we can say 2^45 * 2^45 * 2^9 ; 1*1*2^9
2^9 divided by 99 gives remainder 17 ; IMO A;

Small correction mate 2^45/99 leads us to 98/99 =-1/99, so -1*-1*2^9/99 leaves remainder 17

Posted from my mobile device

[quote="Bunuel"]What is the remainder when \(2^{99}\) is divided by 99?

A. 17
B. 15
C. 13
D. 11
E. 9




since 99 can be written as 3*3*11, and none of the three prime factors can be cancelled with the numerator. we simply add the three primes. (3+3+11 = 17)
answer - A) 17

8=1*9-1

\(2^3=-1 mod 9\)
\((2^3)^{33}=(-1)^{33}\) mod 9

\(2^{99}\)= -1 mod 9= 8 mod 9

\(2^{99}=9m+8\).......(1)

32=3*11-1
\(2^5\)=-1 mod 11
\((2^5)^{19}\)=-1 mod 11
\(2^{95}*2^4\)=-1*5 mod 11
\(2^{99}\)= -5 mod 11= (11-5) mod 11
\(2^{99}\)= 6 mod 11

\(2^{99}=11n+6\).......(2)

So basically our question stem is "The remainder when N is divided by 9 is 8, and when divided by 11 is 6. What is the remainder when N is divided by 99"?

from 1 and 2

\(2^{99}= lcm(9,11)x+17\)
\(2^{99}= 99x+17\)

\(\frac{2^{99}}{99}\)
\(\frac{(2^{9})^{11}}{99}\)
\(\frac{512^{11}}{99}\)
\(\frac{(495 + 17)^{11}}{99}\)
\(\frac{(99*5 + 17)^{11}}{99}\)

Hence removing multiples of 99, we are left with -
\(\frac{(17)^{11}}{99}\)
\(\frac{(17)^{10} * 17}{99}\)
\(\frac{(17^{2})^{5} * 17}{99}\)
\(\frac{(289)^{5} * 17}{99}\)
\(\frac{(297 - 8)^{5} * 17}{99}\)
\(\frac{(99*3 - 8)^{5} * 17}{99}\)

Hence removing multiples of 99, we are left with -
\(\frac{(-8)^{3} * (-8)^{2} * 17}{99}\)
\(\frac{(-512) * (-8)^{2} * 17}{99}\)
\(\frac{(-495 - 17) * (-8)^{2} * 17}{99}\)
\(\frac{(-(99*5) - 17) * (-8)^{2} * 17}{99}\)

Hence removing multiples of 99, we are left with -
\(\frac{(-17) * (-8)^{2} * 17}{99}\)
\(\frac{(-289) * (-8)^{2}}{99}\)
\(\frac{(-297+8) * (-8)^{2}}{99}\)
\(\frac{(-(99*3)+8) * (-8)^{2}}{99}\)

Hence removing multiples of 99, we are left with -
\(\frac{8 * (-8)^{2}}{99}\)
\(\frac{8 * 64}{99}\)
\(\frac{512}{99}\)
\(\frac{(495 + 17)}{99}\)
\(\frac{(99*5 + 17)}{99}\)

Hence removing multiples of 99, we are left with -
\(\frac{17}{99}\)

Hence Remainder is 17 - (A)
_________________

Could you please elaborate on this "rule" further? I tried it with different numbers, and I was not able to obtain the same result.

\(2^{99} = (2^{15})^6*2^9\)
Remainder when 2^{99} is divided by 99 = 1^6*17 = 17

IMO A
_________________

Hi VeritasKarishma chetan2u

Any easier way to solve this ?
_________________

You have used 9 and 11 since 9*11 = 99 and you have also bifurcated the numerator i.e. 2^99 . Is that correct ?

Posted from my mobile device
_________________

Yup. i split 99 into 9 and 11 because 9 and 11 are co-prime; hence lcm(9,11)=99

M*N= x mod y

M= a mod y
N= b mod y

M*N= (a*b) mod y, where a*b<y

Then x= a*b

Yes, the solution here is a lot less intuitive and a lot more 'mathematical'. This happens when we try to practice for GMAT using non-GMAT sources. Tough GMAT questions are usually very interesting and fun in a way. I have made mistakes in a few of them even after so many years and that is what is challenging about them - you can never fully prepare for them because they have a punch. Of course, you will do well on most of them if you have your concepts sorted so scoring 51 will not be problem but still every now and then you will get something that will knock you off your feet. But I digress.
Coming back to this question, I could see that no power of 2 that I knew is very close to a multiple of 100. On the other hand, I notice that powers 8 and 32 are 1 less than multiples of 9 and 11. Then perhaps that is where the answer lies.

Using binomial theorem I discussed in this post (https://www.veritasprep.com/blog/2011/0 ... ek-in-you/), we know that
When 2^99 is divided by 9, it will leave remainder 8.
When 2^99 is divided by 11, it will leave remainder 6.

Now, isn't it similar to questions like this:
When n is divided by 9, it leaves remainder 8 and when it is divided by 11, it leaves remainder 6. What is the remainder when n is divided by 99?

The concept involved in how to solve this is discussed here: https://www.veritasprep.com/blog/2011/0 ... s-part-ii/

n = 9a + 8
n = 11b + 6
Try b = 1, n = 17. It is of the form 9a + 8 too so first such number is 17.

n = 99c + 17

Then, on division by 99, the remainder will be 17.
_________________

Wow. You were so quick with the response. Thank you very much for being so approachable even on holidays. That’s true commitment. Once again, wish you great holidays!
_________________

VeritasKarishma

One mechanism can be to check the remainder with 9 only and immediately check the options.

Here remainder of 2^99 with respect to 9 is 8.

The final remainder also has to give the same remainder with respect to 9.

Only 17 is a feasible number

Cheers

Posted from my mobile device

Absolutely Vinit800HBS, you can use the options in different ways to arrive at the answer as done in the solutions above too!
_________________

Just a quick way to solve, though i am getting answer 17 but still need to confirm if i am thinking right way

2^99/99 can be written as
(2^10)^10/2*99
(1024)^10/2*99

when 1024/99 leaves a remainder of 34, which is being when further divided by 2 leaves 17

A

Please let me know incase i am thinking correct.

Recall that a useful theorem in finding the remainder when a number is divided by another is:

If a and b have remainders r and s when divided by n, respectively, then ab and rs have the same remainder when divided by n.

For example, 8 and 9 have remainder 3 and 4 when divided by 5, respectively. We see that both 8 x 9 = 72 and 3 x 4 = 12 have the same remainder when divided by 5 (notice that 72/5 = 14 R 2 and 12/5 = 2 R 2).

We will use this theorem later, however, since this problem involves exponentiation, we will use the following theorem first:

If a has a remainder r when divided by n, then a^m and r^m have the same remainder when divided by n.

For example, 12 has a remainder of 5 when divided by 7. We see that 12^2 = 144 and 5^2 = 25 both have a remainder of 4 when divided by 7 (notice that 144/7 = 20 R 4 and 25/7 = 3 R 4).

Now let’s solve the problem:

Notice that 2^99 = (2^9)^11 and 2^9 = 512 and 512/99 = 5 R 17. So we can divide 17^11 by 99 since it has the same remainder when (2^9)^11 is divided by 99.

Notice that now 17^11 = (17^2)^5 x 17 and 17^2 = 289 and 289/99 = 2 R 91. We need to evaluate 91^5 divided by 99. However, we can use the following theorem:

Let 0 < r < n. If m is even, then r^m and (n - r)^m have the same remainder when divided by n. If m is odd, then the sum of the remainders is n.

For example, let r = 3 and n = 7, so n - r = 4. Let m = 2, we see that 3^2 = 9 and 4^2 = 16 both have a remainder of 2 when divided by 7. If m = 3, we see that 3^3 = 27 has a remainder of 6 when divided by 7 and 4^3 = 64 has a remainder of 1 when divided by 7 (notice that 6 + 1 = 7).

Therefore, since 5 is odd, let’s divide (99 - 91)^5 = 8^5 by 99 (which is easier than dividing 91^5 by 99). Notice that 8^5 = (2^3)^5 = 2^15 = 2^9 x 2^6. We know 2^9 has a remainder of 17 when divided by 99 and 2^6 = 64. Since 17 x 64 = 1088 and 1088/99 = 10 R 98. Since the sum of this remainder (98) and the one from dividing 91^5 by 99 should be 99, we see that the remainder when 91^5 is divided by 99 must be 1. Finally, recall that 17^11 = (17^2)^5 x 17 and (17^2)^5 has a remainder 1 when divided by 99, so the remainder when 17^11 is divided 99 is same as 1 x 17 = 17 divided by 99, which is 17.

Answer: A
_________________