Wilson's Theorem - Applications

Applications

Wilson's theorem is useless as a primality test in practice, since computing (n − 1)! modulo n for large n is hard, and far easier primality tests are known (indeed, even trial division is considerably more efficient).

Using Wilson's Theorem, for any odd prime p = 2m + 1 we can rearrange the left hand side of

to obtain the equality

This becomes

We can use this fact to prove part of a famous result: for any prime p such that p ≡ 1 (mod 4) the number (−1) is a square (quadratic residue) mod p. For suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that

Wilson's theorem has been used to construct formulas for primes, but they are too slow to have practical value.