Editors note: Our oracle on CAT Quantitative Aptitude Ravi Handa is back! But unlike last years article series which introduced rather advanced quant tricks, the series running starting now would take it a little easy and try to be useful to those who are preparing for CAT 2012 and want to strengthen their arsenal with some intermediate conceptual understanding and shortcuts. Feel free to suggest topics to him and he will try to respond with the right article on those topics. Meanwhile, you can also go through his last years article series here.
———
In this post I would like to discuss some of the really fundamental ideas that can be used to solve questions based on remainders. If you have just started your preparation for CAT 2012, you might find this article helpful. On the other hand, if you are looking for some advance stuff, I suggest that you check out some of my posts from last year on the same topic.
First of all,
Rem = 0 to d-1
What I am trying to say above is that if you divide an by d, the remainder can be any value from 0 to d-1.
Not only that, if you keep on increasing the value of n, you would notice that the remainders are cyclical in nature. The pattern of the remainders would repeat. See this example,
4^1 divided by 9, leaves a remainder of 4.
4^2 divided by 9, leaves a remainder of 7. {Rem(16/9) = 7}
4^3 divided by 9, leaves a remainder of 1. {Rem (64/9) = 1}
4^4 divided by 9, leaves a remainder of 4. {Rem (256/9) = 4}
4^5 divided by 9, leaves a remainder of 4. {Rem (1024/9) = 7}
4^6 divided by 9, leaves a remainder of 4. {Rem (4096/9) = 1}
4^(3k+1) leaves a remainder of 4
4^(3k+2) leaves a remainder of 7
4^3k leaves a remainder of 1
As you can see above, the remainder when 4n is divided by 9 is cyclical in nature. The remainders obtained are 4,7,1, 4,7,1, 4,7,1 and so on. They will always follow the same pattern.
Funda 1: an when divided by d, will always give remainders which will have a pattern and will move in cycles of r such that r is less than or equal to d.
With the help of the above idea, you can solve a large number of remainder questions. All you need to do is to figure out the cycle or pattern in which the remainders are moving, and it will lead you to the answer.
Example,
What will be the remainder when 4143 is divided by 9?
Based on the calculations that I did in the beginning of the post, I know that,
Remainders of 4n when divided by 9, move in a cycle of 3.
So, I need to express 143 = 3k + x and that would lead to the answer.
I know that 143 = 141 + 2
(since 141 is divisible by 3)
So, my answer would be the 2nd value in the list, which is 7.
In the questions where you have to find out the remainder of an by d, as a rule you can follow this process,
Step 1: Find out the cycle of remainders when an is divided by d and make a list of those values.
Step 2: Find out the cyclicity, say r
Step 3: Find out the remainder when the power is divided by the cyclicity, that is Rem = p
Step 4: The answer would be the pth value in the list. {If p = 0, it would be the last value in the list}
Funda 2: While trying to find the cycle or pattern of remainders when an is divided by d, just multiply the previous remainder with a to get the next value.
If you notice in the example mentioned in the beginning of this post, I have calculated 45 and 46 and then found out the remainder. As you might have realized by now that it is a long and tedious process. But the good part is, you can avoid that tedious process by just multiplying the previous remainder. In that example instead of calculating 45 and then dividing by 9, I could have just multiplied the previous remainder, which was 4 with 4 to get 16, which would have directly given me a remainder of 7.
Confused? Well, let us look at a new example.
Find out the cyclicity of remainders when 3n is divided by 11.
Solution,
Rem = 3
Rem = 3
Rem = Rem = 5
As you can see that till here there is no problem in calculating the remainders.
Rem = 5 * 3 = 15 = 4
{In this case instead of using 34 = 81, I took the previous remainder, which was 5 and multiplied it with 3 to get 15, which lead to my current remainder = 4}
Rem = 4 * 3 = 11 = 1
{In this case instead of using 35 = 243, I took the previous remainder, which was 4 and multiplied it with 3 to get 12, which lead to my current remainder = 1}
Rem = 1 * 3 = 3
{In this case instead of using 36 = 729, I took the previous remainder, which was 1 and multiplied it with 3 to get my current remainder = 3}
As you might have noticed, the remainder 3 repeated itself and so the cycle or pattern of remainders was -> 3, 9, 5, 4, 1 and the cyclicity was 5.
Let us try and solve a slightly more complicated problem with this idea.
Find out the remainder when 3232^32 is divided by 7.
Rem = Rem
Step 1: Find out the cycle / pattern of remainders when 4n is divided by 7.
Rem = 4
Rem = 2
Rem = 1
So, the cycle/pattern is 4, 2, 1.
Step 2:
The cyclicity is 3.
Step 3:
Rem = Rem = (-1)
32
= 1
Step 4:
The answer is the 1
st
value in the list, which is
4.
I hope you found this post useful. Suggestions for future posts are more than welcome.
Watch the video version of this article below.
Ravi Handa, an alumnus of IIT Kharagpur, has been teaching for CAT and various other competitive exams for around a decade. He currently runs an online CAT coaching and CAT Preparation course on his website http://www.handakafunda.com