TOPICS
Search

Wilson's Theorem

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Wilson's theorem states that, for a positive integer p>1, (p-1)!+1 is a multiple of p iff p is prime, that is

(p-1)!=-1 (mod p).
(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 n, (n-1)!=0 (mod n) except when n=4.

For an odd prime p, a corollary states that the square of [(p-1)/2]! is congruent to -1 modulo p iff p is of the form 4k+1. For such a prime, k=(p-1)/4 is a positive integer and

[(2k)!]^2=-1 (mod p).
(2)

The first few primes of the form p=4k+1 are p=5, 13, 17, 29, 37, 41, ... (OEIS A002144), corresponding to k=1, 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 P(n) the product of integers that are less than or equal to and relatively prime to an integer n. For n=1, 2, ..., the first few values are 1, 1, 2, 3, 24, 5, 720, 105, 2240, 189, ... (OEIS A001783). Then defining

P(n)=product_(k=1; (k,n)=1)^nk
(3)

gives the congruence

P(n)={0 (mod 1) for n=1; -1 (mod n) for n=4,p^alpha,2p^alpha; 1 (mod n) otherwise
(4)

for p an odd prime and alpha a positive integer. When n=2, this reduces to P=1 (mod 2) which is equivalent to P=-1 (mod 2). The first few values of P(n) (mod n) are 0, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, ... (OEIS A103131, using -1 at n=2 instead of the congruent representative 1).

For a nonnegative integer n, Szántó (2005) notes that defining

S(n)=2product_(k=1)^(n)sum_(i=1)^(k)i
(5)
=2^(1-n)n!(n+1)!,
(6)

then, taking the minimal residue,

S(n)={(-1)^((n+2; 2)) (mod 2n+1) for 2n+1 prime; 0 (mod 2n+1) otherwise.
(7)

For n=0, 1, ..., the first terms are then 0, -1, 1, 1, 0, -1, 1, 0, -1, -1, 0, ... (OEIS A112448).

See also

Fermat's Little Theorem, Prime Formulas, Wilson Prime

Explore with Wolfram|Alpha

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 61, 1987.Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 142-143 and 168-169, 1996.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, p. 167, 2003.Hilton, P.; Holton, D.; and Pedersen, J. Mathematical Reflections in a Room with Many Mirrors. New York: Springer-Verlag, pp. 41-42, 1997.Nagell, T. "Wilson's Theorem and Its Generalizations." Introduction to Number Theory. New York: Wiley, pp. 99-101, 1951.Ore, Ø. Number Theory and Its History. New York: Dover, pp. 259-261, 1988.Séroul, R. "Wilson's Theorem." §2.9 in Programming for Mathematicians. Berlin, Germany: Springer-Verlag, pp. 16-17, 2000.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 37-38, 1993.Sloane, N. J. A. Sequences A001783/M0921, A002144/M3823, A005098, A103131, and A112448 in "The On-Line Encyclopedia of Integer Sequences."Szántó, S. "The Proof of Szántó's Note." http://www.dkne.hu/Proof.html.Waring, E. Meditationes Algebraicae. Cambridge, England: University Press, 1770.

Referenced on Wolfram|Alpha

Wilson's Theorem

Cite this as:

Weisstein, Eric W. "Wilson's Theorem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/WilsonsTheorem.html

Subject classifications