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:
Attachment:
09th Apr 2020 - Reply 7 - 1.jpg [ 49.39 KiB | Viewed 2644 times ]
Attachment:
09th Apr 2020 - Reply 7 - 2.jpg [ 57.81 KiB | Viewed 2636 times ]
Attachment:
09th Apr 2020 - Reply 7 - 3.jpg [ 63.9 KiB | Viewed 2623 times ]
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!
_________________