Bunuel wrote:
What is the remainder when \(2^{99}\) is divided by 99?
A. 17
B. 15
C. 13
D. 11
E. 9
Are You Up For the Challenge: 700 Level Questions: 700 Level QuestionsRecall 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 _________________
★
★
★
★
★
350 REVIEWS
5-STAR RATED ONLINE GMAT QUANT SELF STUDY COURSE
NOW WITH GMAT VERBAL (Pre-Launch)
See why Target Test Prep is the top rated GMAT quant course on GMAT Club. Read Our Reviews