The concept of negative remainders
If the remainder of a mod b is n, the remainder can also be written as (n-b). For e.g. Remainder of 100 divided by 7 is 2 but it can also be written as (2 – 7) = -5. This is called the negative remainder.
This is not just useful for solving problems involving Wilson’s theorem but also while solving problems based on Euler’s theorem, Fermat’s little theorem and Chinese remainder theorem.
Wilson’s theorem
It simply states that for a prime number ‘p’, (p-1)! will give a remainder of (p – 1) when it is divided by p. In other words, let’s say we consider the prime number 5. Then, 4! when divided by 5 will give a remainder of 24 mod 5 or 4. Similarly, when 6! is divided by 7, we get the remainder to be 6.
A few other examples
40! mod 41 will be 40
42! mod 43 will be 42
96! mod 97 will be 96
and so on.
Remember that the denominator (or the divisor) should be a prime number and so, it would not completely divide the numerator.
Corollary of the Wilson’s theorem for CAT
Extending the Wilson’s theorem further, we can see that for a prime number ‘p’, (p – 2)! will give a remainder of 1 when it is divided by p. This can be proved by simply using the concept of negative remainders.
Let us say that the remainder of (p – 2)! mod p is r.
We know that, using Wilson’s theorem,
(p – 1)! mod p is (p – 1)
So, (p – 1) * (p – 2)! mod p is (p – 1)
Using the property of remainders of a product, we can say that
[(p – 1) mod p] * [(p – 2)! mod p] is (p – 1)
Now, if p is a prime number, (p – 1) mod p will always be (p – 1)
So, for LHS = RHS to happen, the second part of the expression should give the remainder equal to 1.
(p – 2)! mod p will be equal to 1.
While it has not really been useful in CAT over the last many years now, the concept is pretty easy to digest and so, is important.
The direct questions could be in the form of:
What is the value of 71! mod 73?
What is the value of 87! mod 89?
Moderate level questions involving Wilson’s theorem
Taking things a bit further, we can get questions which are almost direct but involve an additional level of solving. Something like this:
What is the value of 40! mod 43?
Now, we know that 42! mod 43 is 42 and 41! mod 43 is 1. So, let’s see how to proceed.
The way we derived the remainder of (n – 2)! mod n is particularly useful here. So, we already know that:
41! mod 43 = 1
41 * 40! mod 43 = 1
41 mod 43 * (40! mod 43) = 1
(-2) * (40! mod 43) = 1
Let 40! mod 43 be r
-2r mod 43 = 1
-2r = 43k + 1
If k = 1, r = -22
Using the concept of negative remainders, if -22 is the remainder of 40! mod 43, it will also be 43 – 22 = 21. So, the remainder will be 21.
Try out a few similar examples and let us know your answers in the comments section:
1) 94! mod 97 = ?
2) 98! mod 101 = ?
3) 70! mod 73 = ?
See a trend?
The remainder, for n! mod (n+3) where (n+3) is prime will be half of the even number immediately greater than n.
Taking it another level further, can we calculate the remainders of the following expressions?
4) 93! mod 97 = ?
5) 97! mod 101 = ?
6) 69! mod 73 = ?
Tough questions from Wilson’s theorem
The final type of questions involve a mix of Wilson’s theorem and the Chinese remainder theorem. Sample questions would be:
195! mod 394 will be equal to = ?
We see that 394 = 2 * 197 and that 197 and 2 are co-prime. So, presence of a factorial and a composite divisor should strongly hint towards this particular type.
Using the Wilson’s theorem, we can say that:
195! mod 197 is 1 and
195! mod 2 is 0
Using the Chinese remainder theorem, we can say that the remainder will be equal to:
197k + 1 = 2m
It gets satisfied for k = 1 and so, the remainder will be 198.
Try these questions out using similar logic
7) 95! mod 485 = ?
8) 39! mod 164 = ?
Do share your answers and solutions with us in the comments section. Also, let us know if you want us to explain certain topics on the blog. You can join our Facebook group here: CAT preparation with Learningroots
Also, if you are from Mumbai, there is some good news for you following the CAT notification as seats are filling up for our CAT intensive batch 2. Do fill up the form and we would get in touch with you.
Do check out our new Free downloads page for CAT 2016.
Happy learning!
