Iff is a prime, then is a multiple of , that is
(1)
|
This theorem was proposed by John Wilson and published by Waring (1770), although it was previously known to Leibniz. It was proved by Lagrange in 1773. Unlike Fermat's little theorem, Wilson's theorem is both necessary and sufficient for primality. For a composite number, except when .
A corollary to the theorem states that iff a prime is of the form , then
(2)
|
The first few primes of the form are , 13, 17, 29, 37, 41, ... (OEIS A002144), corresponding to , 3, 4, 7, 9, 10, 13, 15, 18, 22, 24, 25, 27, 28, 34, 37, ... (OEIS A005098).
Gauss's generalization of Wilson's theorem considers the product of integers that are less than or equal to and relatively prime to an integer . For , 2, ..., the first few values are 1, 1, 2, 3, 24, 5, 720, 105, 2240, 189, ... (OEIS A001783). Then defining
(3)
|
gives the congruence
(4)
|
for an odd prime. When , this reduces to which is equivalent to . The first few values of are 0, , , , , , , 1, , , , ... (OEIS A103131).
Szántó (2005) notes that defining
(5)
| |||
(6)
|
then, taking the minimal residue,
(7)
|
For , 1, ..., the first terms are then 0, , 1, 1, 0, , 1, 0, , , 0, ... (OEIS A112448).