What is the remainder when 2^99 is divided by 99?

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

[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

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

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.gmatclub.com/forum/veritas-prep-resource-links-no-longer-available-399979.html#/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.gmatclub.com/forum/veritas-prep-resource-links-no-longer-available-399979.html#/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.

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;

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

Answer: Option A

Please check the video for the step-by-step solution.

GMATinsight's Solution

Subscribe to my YouTube Channel for FREE resource (1000+ Videos)

Subscribe Topic-wise UN-bundled Video course. CHECK FREE Sample Videos

Check course on Number Properties and watch some free Sample Videos

Similar to the Unit digit cycle, we can develop something known as a Remainder cycle in every remainder question. Unlike the Unit digit cycle, the cycle will be different in each case and will have different cyclicities depending on the dividend and the divisor.

The only difficulty of using the remainder cycle is the fact that the cyclicity can go up to even 20 in rare cases because of which it may not be the most optimal method in such cases. However, two things work in favor of the remainder cycle:
1) In most remainder questions, you will obtain a cycle with a cyclicity between 1 to 6 which is definitely manageable.
2) Even if the cyclicity is higher, you can manage it by taking the help of the Remainder theorem.

The remainder theorem says this: R(A x B ) = R(A) x R(B). Of course, this is just indicative and can be extended to include more terms.

The different methods of dealing with remainder questions have been dealt in one of our posts on this topic. Here’s the link for the same

https://gmatclub.com/forum/remainders-tips-and-hints-175000.html

Back to the question at hand. Let’s first develop a remainder cycle for the given dividend and divisor. The remainder cycle will look like the one shown in the images below:







Observe that, even when we were developing the cycle, we took the help of the remainder theorem. For example, you can see from the diagram that \(2^7\) yields a remainder of 29 when divided by 99. If I now want to find the remainder of \(2^8\), which is \(2^7 * 2^1\), I’ll just multiply the respective remainders to obtain 58 as the remainder.

Point to note is that if you divide \(2^8\) i.e. 256 by 99, the remainder is of course 58. But the more important point is that you don’t have to do this from now on.

SO, what will be the remainder when \(2^9\) is divided by 99? Since \(2^9\) =\( 2^8 * 2^1\), we multiply the respective remainders, 58 and 2, to obtain 116; since 116 is more than 99, we divide again and find that the final remainder is 17.
Hope this method is clear.

From the diagram, we observe that the remainder when \(2^{15}\) is divided by 99 is 98; a remainder of 98 is equivalent to a negative remainder of -1. Therefore, \(2^{30}\) will yield a remainder of -1 * -1 = 1, since \(2^{30}\) = \(2^{15} * 2^{15}\).

Therefore, \(2^{30}\) when divided by 99 yields a remainder of 1. Knowing this, we can break up \(2^{99}\) as \(2^{30} * 2^{30} * 2^{30} * 2^9\). The first three parts will give a remainder of 1 whereas the last part gives a remainder of 17. So, the final remainder is 17.

The remainder cycle when coupled with the remainder theorem can be a potent tool to solve remainder questions like these which involve large powers and fairly large divisors.

Hope that helps!

\(2^{99}\) = \(\frac{(2^3)^{33} }{ (3^2 * 11)}\)

First divide by 9:

=> Remainder when \(2^3\) is divided by \(3^2\) is (-1)

=> \((-1)^{33}\) = \(\frac{-1 }{ 9}\) = Remainder: -1 + 9 = 8

Now divide by 11:

\(2^{99}\) = \((2^5)^{19}\) * \(2^4\)

=> Remainder when \(2^5\) is divided by 11 is (-1) and when \(2^4\) is divided by 11 is 5.

=> \((-1)^{19}\) = -1

=> \(\frac{(-1 * 5) }{ 11}\) = \(\frac{-5}{11}\) = Remainder = -5 + 11 = 6

We need a common number which when divided by 9 gives '8' as a remainder and when divided by 11 gives '6' as remainder.

Number is 17 => 9(1) + 8 and 11(1) + 6

Answer A

Hi VeritasKarishma chetan2u

Any easier way to solve this ?

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

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

Hi ArvindCrackVerbal,
How can we solve this question using cyclicity?
I reached at remainder 9 for 2^99 using the rule.
But as the denominator is 99, I'm unable to move ahead.
Can you please guide me?

A method which can be used in such a case is using cyclicity of remainders. In this we see how many cycles are required to get a remainder of 1.

Interestingly, if you get a remainder of -1, then the double of the cycles gives a remainder of 1.

We get a remainder of -1, if the remainder is 1 less than the divisor (eg, 31 divided by 8 gives a remainder of 7 which is also -1)

Here since we have powers of 2, it is a pretty simple multiplication. We stop the cycle, when we get a remainder of 1 or 98. If we get a remainder of 98, then double that cycle will give a remainder of 1.


(1) \(R[\frac{2}{99}] = 2\)

(2) \(R[\frac{2 * 2}{99}] = R[\frac{4}{99}] = 4\)

(3) \(R[\frac{4 * 2}{99}] = R[\frac{8}{99}] = 8\)

(4) \(R[\frac{8 * 2}{99}] = R[\frac{16}{99}] = 16\)

(5) \(R[\frac{16 * 2}{99}] = R[\frac{32}{99}] = 32\)

(6) \(R[\frac{32 * 2}{99}] = R[\frac{64}{99}] = 64\)

(7) \(R[\frac{64 * 2}{99}] = R[\frac{128}{99}] = 29\)

(8) \(R[\frac{29 * 2}{99}] = R[\frac{58}{99}] = 58\)

(9) \(R[\frac{58 * 2}{99}] = R[\frac{116}{99}] = 17\)

(10) \(R[\frac{17 * 2}{99}] = R[\frac{34}{99}] = 34\)

(11) \(R[\frac{34 * 2}{99}] = R[\frac{68}{99}] = 68\)

(12) \(R[\frac{68 * 2}{99}] = R[\frac{136}{99}] = 37\)

(13) \(R[\frac{37 * 2}{99}] = R[\frac{74}{99}] = 74\)

(14) \(R[\frac{74 * 2}{99}] = R[\frac{148}{99}] = 49\)

(15) \(R[\frac{49 * 2}{99}] = R[\frac{98}{99}] = 98 \space or \space -1\)


This means that on the 30th cycle, we will get a remainder of 1.

\(R[\frac{2^{99}}{99}] = (R[\frac{(2^{30})^3}{99}] * R[\frac{2^9}{99}]) = 1 * R[\frac{512}{99}] = 17\)



Option A

Arun Kumar

This is not correct. Think about it: What if you were to divide 34 by 99? What would be the remainder?
Can you say it will be the same as remainder of 34/33 * 1/3 i.e. remainder will be 1? No. Remainder will be 34

The method used by chetan2u uses some ingenuity. He observed that the remainders in the options were all less then 33.
When you divide n by 99 and if the remainder is less than 33, the remainder will be the same when you divided n by 33 because 33 is a factor of 99.

If this is not clear, think in terms of the grouping method. When you divide n into groups of 99 balls each, say r balls are leftover so remainder is r.
Now if r is less than 33, then even if you divided n into groups of 33 balls, the remainder will be the same i.e. r. All groups of 99 balls will just get split into 3 groups of 33 balls each.

2^3 wil give 9-1 therefore when divided by 9 will give (-1)^33 = 8 therefore of the form 9k+8

2^5 similarly will give 11k+6

when looked for a similar foem 17 satisfies

THerefore IMO A

Re(2^99 /99)
99=9*11 ; 9 and 11 are co prime

Separately find out remainders with 9 and 11 as the divisor.

Re (2^99 /9)
2^3 i.e. 8 mod 9 gives -1 as the remainder
Re [2^3)^33 /9]=-1=8

Now,

Re (2^99 /11)
Since 2 and 11 are co prime, Euler Method can be easily applied.
E(11)=10
Re (2^99 /11)= ?

Had the power been 100 we would had got 1 as the remainder.
Re[(2^99) * 2 /11]=1
2 mod 11 =2
2^100 mod 11 =1
So,
(2^99) * (2) mod 11 =1
(..) * 2 =1
If we put 6 in place of (..) we would get 12
Now 12 mod 11=1 (This is kind of reverse Euler).
Concluding
2^99 mod 9= 8,17,26,35,43......
2^99 mod 11=6,17,23,.....

Converging no is 17 which is the remainder.