Modular Arithmetic/Wilson's Theorem

Wilson's theorem

A natural number $\alpha \neq 1$ is a prime number if and only if:

$(\alpha -1)!\equiv -1{\pmod {\alpha }}$

$\alpha !$ denotes the factorial of $\alpha$ . For all natural numbers, it gives the product of all numbers less than or equal to $\alpha$ .

Examples

5 is a prime number because,

$4!=24$

and

$24\equiv -1{\pmod {5}}\implies 25|5$

which is true. 6, on the other hand, is not, as

$5!=120$

and

$120\equiv -1{\pmod {6}}\implies 121|6$

which is false.