Wilson’s Theorem | Mathematics

Wilson’s theorem states that a natural number p > 1, is a prime number, if and only if,

(p - 1) ! is congruent to (-1)      mod p

That is,

(p - 1) ! ≡ -1      mod p

Or,

(p - 1) ! ≡ (p -1)      mod p

Examples:

Example 1:
Let p = 11
(p - 1) ! ≡ (p -1)      mod p
(11-1) ! = 10 ! = 3628800
3628800 % 11 = 10
(-1) % 11 = 10
Hence, LHS and RHS are congruent, as p = 11 is a prime number.

Example 2:
Let p = 7
(p - 1) ! ≡ (p -1)      mod p
(7-1) ! = 6 ! = 720
720 % 7 = 6
(-1) % 7 = 6
Hence, LHS and RHS are congruent, as p = 7 is a prime number.

Example 3:
Let p = 4
(p - 1) ! ≡ (p -1)      mod p
(4-1) ! = 3 ! = 6
6 % 4 = 2
(-1) % 4 = 3
Hence, LHS and RHS are not congruent, as p = 4 is not a prime number.

How can it be used practically in solving competitive programming or algorithmic questions?

Consider the problem of computing factorial under modulo of a prime number which is close to input number, i.e., we want to find value of “n! % p” such that n < p, p is a prime and n is close to p. For example (67! % 71). From Wilson’s theorem, we know that 70! is -1. So we basically need to find [ (-1) * inverse(70, 71) * inverse(69, 71) * inverse(68, 71) ] % 71. The inverse function inverse(x, p) returns inverse of x under modulo p.

You can compute the Multiplicative Modulo Inverse using the Extended Euclidean Algorithm. Read more applications of the Extended Euclidean Algorithm.