In the last article we saw the basics of the Euler’s number/totient function and how to find the same. Now, I will be covering two different question types in this article that deals with finding remainders involving dividends of the type ab using Euler’s theorem.
We know that Dividend = (Divisor * Quotient) + Remainder
Now, as we are interested in only the remainder part, and we already know the dividend and the divisor (from the question), we can ignore the quotient.
Another important thing to understand is the binomial theorem which is again an extension of the above concept. It basically states that any number can be expressed as consisting of two parts such that:
(a+b)n = nC0 an * b0 + nC1 an-1 * b1 + nC2 an-2 * b2 + … + nCn a0 * bn
Remember that nCr = nC(n-r) and so, the equation would be symmetrical.
In simpler words, if you have say a number 133 you can write it as either (12+1)3 or (11+2)2 or (10+3)3 and so on. The beauty of the theorem is that, you will get all terms containing some form of ‘a’ except the last one in the above expansion and so, you can use it to your benefit.
A number in the form ab can be understood to consist of a base ‘a’ and a power ‘b’. To reduce the base, you need to use the binomial theorem and to reduce the power, you need to use the Euler’s totient function. Many people get confused in these two operations and end up doing one thing in the place of other. You can take the example of a simple concept to understand this. If you have to find the remainder of say 533 when divided by 7, you would not worry about the remainder and keep on reducing the dividend, right? This is nothing but a variant of the binomial theorem. We get the remainder as 1 in this case and so, we ignore the quotient*divisor part of it. We will do a similar operation for reducing the base of the number.
In simple words it states that if there is a number say p which divides another number of the form ab where a and p are co-prime then the remainder is always 1 if b = x*E(p) where x is a whole number. As you can see, the above operation has got nothing to do with the base of the expression and so, it is used to reduce the power only.
Example: As the Euler’s function for 6 is 2, any number in the form of a2x (where x is a whole number) will give remainder of 1 when divided by 6 given that ‘a’ and 6 are co-prime.
Fermat’s little theorem
This simply takes the case of prime numbers and used the Euler theorem. As seen in the previous article, E(prime number) will always be (prime number – 1). And so, ax(p-1) mod p (where ‘ p’ is a prime number, ‘a’ and ‘p’ are co-prime and ‘x’ is a whole number) will always be 1.
Finding the remainder when a dividend of the form ab is divided by a divisor ‘p’
Case I: ‘a’ and ‘p’ are co-prime
This is easy stuff and can be expected in CAT. You have to simply reduce the base ‘a’ using binomial theorem such that it gives you a remainder when divided by ‘p’ and then reduce the power ‘b’ by finding the remainder when it is divided by E(p).
Example: Remainder when 2357 is divided by 18
18 and 23 are co-prime and so, we can directly use Case I here.
Step I: We will need to find E(18) first which comes out to be 6.
Step II: Reduce base. Base is 23 in this case which gives a remainder of 5 when divided by 18. So, the new base becomes 5.
Step III: Reduce power. Power is 57 in this case which gives a remainder of 3 when divided by E(18). So, new power becomes 3.
Step IV: New expression becomes 53 divided by 18 which can be easily simplified to 125 mod 18 which will give you 17 as the remainder.
Example: Remainder when 47785952 is divided by 23
4778 and 23 are co-prime and so, we can directly use Case I here. (Can be found using division or from the calculator)
Step I: We will need to find E(23) first which comes out to be 22.
Step II: Reduce base. Base is 4778 in this case which gives a remainder of 17 when divided by 23. So, the new base becomes 17.
Step III: Reduce power. Power is 5952 in this case which gives a remainder of 12 when divided by E(23). So, new power becomes 12.
Step IV: New expression becomes 1712 divided by 23. As this is again not very straightforward, we will expand 1712 as (289)6 and apply the base reduction binomial theorem again. Which will give us the new base as 13 and the new expression as 136. Still not friendly? Again expand the base to (169)3 and reduce the base which gives us 83 mod 23 which would become 512 mod 23 which gives us 6 as the remainder.
Case II: ‘a’ and ‘p’ are not co-prime
While the Euler function holds true for many cases, it cannot be said to be universal. The easier way to do this would be to visualize a small example. Say you are dividing 324 by 24 and want to find the remainder. You can see that 324 and 24 share a few factors. One way to do this would be to simply divide the entire thing by 24 and find the remainder. The other way is as follows:
324/24 = (27*12)/(2*12). Cancelling 12 from both the numerator and the denominator, we get 27/2, the remainder of which is 1. But, because you had cancelled 12, you will have to multiply the remainder by 12 in the final step and so, your ‘true’ remainder will be 1*12=12. If you solve it using the conventional method, you will get the same remainder. Try it out.
So, in expressions where ‘a’ and ‘p’ are not co-prime, we take a few powers of ‘a’ out and cancel off the common factor from the denominator. Once we get the form where ‘a’ and ‘p’ are co-prime, we can simply proceed as we did in case I. Just that we have to multiply the cancelled factor with the remainder that we get to find the ‘true’ remainder.
Example: 32243 mod 36
As 32 and 36 are not co-prime, we will try to factorize the denominator and cancel off the common factor.
Step I: 36 is nothing but 4*9 whereas, 32 is nothing but 4*8. As, the HCF is 4, we take one 32 out of the base and cancel the common term i.e. 4. So, new expression becomes:
32*32242 mod 36 which becomes 8*32242 mod 9
Once we get this, we will proceed using the same method we did in case I. We will keep 8 aside and find the remainder of 32242 mod 9
Step II: We will need to find E(9) first which comes out to be 6.
Step III: Reduce base. Base is 32 in this case which gives a remainder of 5 when divided by 9. So, the new base becomes 5.
Step IV: Reduce power. Power is 242 in this case which gives a remainder of 2 when divided by E(9). So, new power becomes 2.
Step IV: New expression becomes 52 divided by 9 which gives us 7 as the remainder.
Step V: The answer is not 7 though as we have an 8 pending from step I. So, we get the expression as 8*7 mod 9 which is nothing but 2.
Step VI: Multiply the derived remainder by the cancelled factor to get the ‘true’ remainder. So, the final remainder is nothing but 2*4 = 8
Note: There are a couple more ways at least to solve this. I have mentioned it here. Just see if you were able to figure out the logic behind the same.
Alternative method I:
32243 mod 36
21215 mod 36
21213 mod 9
2, which gives final remainder as 2*4=8
Alternative method II:
32243 mod 36
(-4)243 mod 36
(-1) * 4242 mod 9
The cyclicity you get of the remainders is 4, 7, 1, 4, 7, 1 and so on for the powers of 4 when divided by 9. So, remainder will be -1*7 = -7 which is 2. So, final remainder will be 2*4 = 8
Corollary: If the remainder of ‘a’ divided by ‘b’ is ‘p’, it is also equal to ‘(p-b)’
You can try out a few easy questions on your own to understand the working better. Once you are well-versed with the concept, you will be able to reduce the base and power in one step and can solve the questions in 30-45 seconds flat. If lucky, you might get a maximum of a couple of questions from this sub-topic.
Word of caution
Preparing questions from this areas does not take much effort and so, you might end up solving extremely cryptic questions involving around 12-15 steps. A sincere bit of advice, stay away from such questions. If CAT wanted to test your calculation speed and technique, they would not get into Euler theorem and Fermat theorem but simply give you multiplication of long numbers. Any question that takes more than 3 minutes to solve does not merit an attempt in the first go and so, you might have to sacrifice a few questions which are indeed doable but take up a lot of time.
Historically, CAT has asked questions that can be solved in a couple of steps and as far as we can understand it is solely to test your awareness of the topic and not your calculation skills.
In case you have requests for any specific article, write to us. And we hope you have already enrolled for our free mock CAT series and have taken the first mock. If not, you can check out the same here.