The previous articles in this series focused on straightforward questions you might get from the concept of division involving higher powers using Euler theorem and Fermat’s little theorem and the basic concepts of Euler’s totient function.
Now, we will be looking at a type that is commonly confused with the simpler ab and looks deceptively easy and straightforward. This is the type wherein you have to find the remainder when a number of the form
is divided by another number p.
What is the difference between this type and the previous ones?
As simple as the difference between 2^3^4 and (2^3)^4. If you understand this difference, you would be able to understand the method of solving such questions. If you see carefully, the only difference is the absence of brackets in the first case. But that makes a big difference to the outcome. The first case effectively gives us the number to be 281 while the second case gives us the number to be 212.
Once you understand the form of the question, it becomes extremely easy to do it using the normal methods. You have to follow the same drill of reducing the base and the power and you are sorted.
Let’s learn this through an example, probably the most popular one:
What is the remainder when
is divided by 7?
Wrong approach: Many reduce the base correctly but make a mistake in reducing the power part. They reduce the power by considering it either as 32*32 or simply 32 both of which would give wrong answers.
Right approach: We need to find out the form of 3232 in terms of E(divisor) which would be E(7)=6. So, essentially it becomes a separate question altogether. In the first part, you have to find the form of 3232 mod 6 and then you will get the new power as (6k+x) wherein x is the remainder obtained post the first part. Once you get this, you will have to solve for 32(6k+x) mod 7 which would be nothing but 32x mod 7 which would be 4x mod 7.
On solving, we get:
Step I: Calculate 3232 mod 6
3232 mod 6
232 mod 6
231 mod 3 (cancelling 2 from numerator and denominator)
(-1)31 mod 3
-1 will be the remainder which will be 2.
Multiplying it by the cancelled factor 2, we get the final remainder as 4 and the new power in the form of (6k+4)
Step II: Calculate 32(6k+4) mod 7
4(6k+4) mod 7
E(7) = 6
44 mod 7
256 mod 7
4 will be the answer.
Points to remember here are:
1) You have to proceed from top to bottom and not from bottom to top
2) The divisors in both the steps are different: In the first step, the divisor is the Euler’s totient function of the original divisor whereas, in the second step, the divisor is the original divisor
3) The quotient in the first step is not important and so, we can ignore the 6k part directly
Let’s take another example and do it in a quicker manner:
Find the remainder when
is divided by 17
E(17) = 16
2324 mod 16 = 724 mod 16
E(16) = 8
New power = 16k+1
22(16k+1) mod 17 = 5 mod 17
So, answer will be 5.
With a bit of practice, you can solve the questions using minimal calculations. Again, designing questions is very easy and so, you might get tangled solving mind-numbingly difficult questions which would lead you nowhere and so, it is important to understand the intent behind the question (in-depth knowledge of indices and ability to break down large numbers quickly) before trying to solve and feel disappointed being unable to crunch idiotic numbers in many cases.
You can read the first article on this series here: Division 1|Euler’s Function and the second article on Euler’s and Fermat’s little theorem here: Division 2|Euler theorem and Fermat’s little theorem
We will be covering the Chinese Remainder Theorem in the coming post in this series. In case you have some interesting problems that you would like us to solve, do let us know through the comments section or on our Facebook page.
Also, we hope you have taken the first mock CAT and are enrolled for the coming mock tests.