Remainder theorem - Atreya Roy
Content & PR team - MBAtious
Author: Atreya Roy is pursuing his BTech From Kalyani Government Engineering College, Bengal.
Remainders is a vast area when the MBA entrance examinations are considered. Everytime we get fair number of questions from this chapter. So, to ace in this topic, today we will learn some important concepts from this area.
According to the Wilson’s Theorem, If there is any Prime Number p, (p-1) ! When divided by p will always yield (p-1) as the remainder
- 36! Mod 37 can be expressed as: (37-1)! Mod 37 where p=37. Hence 36! Mod 37 =p-1 = 36
- 12! Mod 13 = 13-1 = 12
There is another very important application of Wilson Theorem.
For any prime number p, When (p-2)! Is divided by p , the remainder yield is always equal to 1.
This can be illustrated using a very simple example. Let us take 9! Mod 11
Multiply 10 in both numerator and denominator, hence now we need to find our remainder for 9!*10/ 10*11. 9!*10 is nothing but 10!. So, our expression becomes 10!/10*11. Using Wilson Theorem, we can say (p-1)! Mod p = (p-1) where p is a prime number. Hence 10! Mod 11 = 10. So now our expression becomes 1*10/10 = 1. Hence the remainder in this case is always “1”.
1) 15! Mod 17 : Can be written as (17-2)! Mod 17 where p = 17. Hence the remainder in this case = 1
2) 11! Mod 13 = 1. Where p = 13
These two concepts of Wilson theorem are very important and will help you solve sums at a faster rate. Applying Euler’s Theorem to co-prime numbers may also work, but with the help of Wilson’s Theorem, you will save a lot of time while solving. Hope the Theory of Wilson’s Theorem for Remainders is clear now. In our Next Concept explanation, we will talk about Fermat’s Theorem, which is another very important theorem used in the field of remainder calculations.
Fermat’s Little Theorem
According to Fermat’s Little Theorem, for any prime number p and any interger k, k(p-1) -1 is always divisible by p
Can also be written as : k(p-1) = 1 (mod p)
Fermat’s Theorem is an application of Euler’s Theorem
What is the remainder then 56 -1 is divided by 7 ?
Solution: Let p = 7, hence (p-1)=6.
So we can write it in k(p-1) -1 form.
From this, 56 -1 mod 7 = 0.
Since 56 -1 is divisible by p. (p=7 in this case).
What is the remainder when 7^41 is divided by 41 ?
Solution : 741 = 740 * 7. Hence 740 * 7 mod 41 = 740 mod 41 * 7 mod 41 = 7* (740 mod 41)
We apply Fermat’s Theorem here to get : 7(p-1) mod p = 1. Hence Remainder = 7
Note : Fermat’s Theorem can also be used to minimize calculations in case of large Remainder problems and chip in other theorems to get the problem done. So, the applications are wide.