Wilson Remainder Theorem

Negative remainders are an idea that has been around for a long time. If a mod b’s residual is n, it can alternatively be represented as (n-b). For example, the remainder of 100 times 7 is 2, but it may alternatively be represented as (2 – 7) = -5. The negative remainder is the term for this. This is useful not only when using Wilson’s theorem to solve issues, but also when using Euler’s theorem, Fermat’s little theorem, and the Chinese remainder theorem.

The theorem of Wilson

When a prime number ‘p’ is divided by p, (p-1)! will result in a remainder of (p – 1). Let’s use the prime number 5 as an example. The remainder of 24 mod 5 or 4 is obtained by dividing 4! by 5. When we divide 6! by 7, we get 6.

Some further examples

40! mod 41 will be 40

96! mod 97 will be 96, and so forth.

Remember that the denominator (or divisor) must be a prime number, else the numerator will not be divided entirely.

Wilson’s theorem Corollary

By extending Wilson’s theorem, we can see that when a prime number ‘p’ is divided by p, (p – 2)! will result in a remainder of 1. Negative remainders can be used to demonstrate this.

Let’s say the rest of (p – 2) is! mod p is r.

(p – 1)! mod p is (p – 1)

So, (p – 1) * (p – 2)! mod p is (p – 1)

We can say that [(p – 1) mod p] * [(p – 2)! mod p] is (p – 1) using the property of remainders of a product.

If p is a prime number, then (p – 1) mod p will always be (p – 1) mod p.

So, in order for LHS to equal RHS, the residual in the second part of the statement must equal 1.

(p – 2)! The value of mod p will be one.

While it hasn’t been particularly useful in CAT for a long time, the principle is simple to grasp and therefore significant.

What is the value of 71! mod 73?

87! mod 89 has what value?

Moderate level questions involving Wilson’s theorem

Taking things a step further, we can get problems that are almost direct yet require a second level of thought to solve. As follows:

40! mod 43 has what value?

42! mod 43 is now 42, and 41! mod 43 is now 1. Let’s see what we can do now.

This is where the method we used to get the remainder of (n – 2)! mod n comes in handy. So far, we’ve established:

(-2) * (40! mod 43) = 1

Let r -2r mod 43 = 1 -2r = 43k + 1 be the value of 40! mod 43.

If k = 1, r = -22

If -22 is the residual of 40! mod 43, 43 – 22 = 21 can be calculated using the idea of negative remainders. So there will be 21 remaining.

Try out a few such scenarios and post your results in the comments section:

1) 94! mod 97 = ?

2) 98! mod 101 = ?

3) 70! mod 73 = ?

Are you noticing a pattern?

The remainder will be half of the even integer immediately greater than n for n! mod (n+3), where (n+3) is prime.

Can the remainder of the following phrases be calculated?

4) 93! mod 97 = ?

5) 97! mod 101 = ?

6) 69! mod 73 = ?

Tough questions from Wilson’s theorem

Wilson’s theorem and the Chinese remainder theorem are combined in the last type of question. 195! mod 394 =?

394 = 2 * 197, and 197 and 2 are coprime. The factorial and composite divisors should strongly suggest this kind.

195! mod 195! mod 2 is 0 and 197 is 1.

The residual will be equal to 197k + 1 = 2m, according to the Chinese remainder theorem.

The remaining will be 198 if k = 1.

Conclusion

Consider the task of finding the factorial of a prime number that is close to the input number, i.e., we want to discover the value of “n! percent p” such that n p, p is a prime, and n is close to p. For instance, (25!% 29). We know 28! is -1 according to Wilson’s theorem. We must therefore get [(-1) * inverse(28, 29) * inverse(27, 29) * inverse(26)]. percent 29. inverse(x, p) yields the modulo p inverse of x.