CrackVerbalGMAT wrote:
This problem is not the most usual type of remainder questions, tested on the GMAT. What makes this question special is, that, although it appears difficult and intimidating at first look, it can actually be solved using some very fundamental concepts on Remainders.
In any remainder question, play smart by trying to express the dividend in the form of (divisor + 1) or (divisor – 1) (as far as you can) so that the remainder turns out to be 1. Apart from this, use the following shortcuts to find out remainders for large values:
Remainder \(\frac{( A+ B )}{K}\) = Remainder \(\frac{(A)}{K}\) + Remainder \(\frac{(B)}{K}\)
Remainder \(\frac{(A * B)}{K}\) = Remainder \(\frac{(A)}{K}\) * Remainder \(\frac{(B)}{K}\)
The above concepts can be extended to the sum or product of any number of values.
Also, when you write the dividend (which has a power) in the form of \((divisor + 1) ^{power}\), the remainder will always be 1. However, if you write the same dividend as \((divisor – 1) ^ {power}\), the remainder will be 1 if the power is even and will be -1 if the power is odd. Since the remainder cannot be negative, we add the divisor to the negative remainder to obtain the final remainder.
Let us now try and apply these concepts to the problem at hand.
By writing down the first few powers of 2, we observe that \(2^6\) i.e. 64 is the number we can write in the form of (13k -1).
Therefore, \(2^{1000}\) can be written as (\(2^{996}\)) * (\(2^4\)). So,
Remainder \(\frac{(2^{1000})}{13}\) = Remainder \(\frac{(2^{996})}{13}\) * Rem\(\frac{(2^4)}{13}\).
Let’s now calculate the individual remainders.
Remainder \(\frac{(2^{996})}{13}\):
\(2^{996}\) = \((2^6) ^{166}\) = \((13*5 – 1)^{166}\).
So, here, we have written the dividend, \(2^{996}\) in the form of \((13k – 1) ^{even power}\), where 13 is the divisor. As discussed earlier, since the power is even, the remainder here will be 1.
Remainder\(\frac{(2^4)}{13}\) = Remainder\(\frac{(16)}{13}\)= 3.
Therefore, final remainder = 1 * 3 = 3.
So, the correct answer option is C.
It’s important to not get flustered by the sheer magnitude of the dividend. Because, as we have demonstrated, if you know the concepts that we have discussed in this post, this question is actually very straight forward. The only effort you will have to put in is to find out the power of 2 which can be written in the form of (13k -1) or (13k + 1). Once that is established, the rest of the solution is simple.
Hope that helps!
But sir, If I divide
2^36 bye 13 I get 9 as remainder, It is not working according to the theory of getting 13k-1 as remainder at 2^6/13, If I divide 2^16 by 13 I get 3 as remainder. I don't get It can you please elaborate on it. Because 2^6 = 13k-1 or 13k+1 only seems to work on some powers and not on every even power. I will be very grateful of you to elaborate on the highlighted portion for clear understanding. Thank you very much in advance sir.