More
AlgorithmsWilson's Theorem | Mathematics

# 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.

Subscribe Today

Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.