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.