Wilson's theorem

Wilson's theorem states that an integer n greater than one is prime exactly when (n − 1)! is congruent to −1 modulo n.

Modular arithmetic: Arithmetic in which integers are identified when they have the same remainder upon division by a fixed modulus. The theorem expresses factorials as congruences modulo n.
Congruence relation: An equivalence relation stating that two integers differ by a multiple of a specified modulus. Wilson's theorem compares the factorial and −1 through congruence modulo n.
John Wilson: An English mathematician whose name is attached to a theorem characterizing prime numbers by factorial congruences. The theorem bears his name, though its first known proof came from Lagrange.
Primality test: A procedure for determining whether a given integer is prime. Wilson's congruence gives a deterministic primality criterion with very high computational cost.
Multiplicative group of integers modulo n: The group of invertible residue classes modulo n under multiplication. For prime n, every nonzero residue is invertible and can be paired with its inverse.
Fermat's little theorem: For prime p and integer a, a^p is congruent to a modulo p. It is a related prime-modulus result, though Wilson's criterion is an exact factorial test.
Joseph-Louis Lagrange: An Italian-French mathematician who made foundational contributions to number theory, mechanics, and analysis. Lagrange published the first known proof of Wilson's theorem in 1771.
Trial division: A primality-testing method that checks divisibility by integers up to the square root of the candidate. Trial division is far more practical than computing the factorial in Wilson's test.
Multiplicative inverse: An element that multiplies another element to produce the identity element. Inverse pairs in the nonzero residues multiply to 1, except self-inverse residues.
Euclid's lemma: If a prime divides a product of integers, it divides at least one factor. The composite case uses prime divisors to rule out the required factorial congruence.

Linked from 5 pages