Theorem W1. (Wilson) The congruence holds true if and only if is prime. Put another way, the number is a multiple of only when is prime.
Proof. If is composite, then it has at least one prime factor . For , we see that . For all higher composite , we see that the number is a product that runs through every prime factor of as well as other composite numbers repeating a lot of those same prime factors, and therefore not –1.
The case of the prime number 2 is disposed of easily enough by examination, leaving us only the odd primes to concern ourselves with. We can also dispose of 3 by examination. The only divisors of an odd prime are 1 and itself, hence for all . For each , there is precisely one integer such that . This means that each integer from 2 to can be paired off such that their product is 1 more than a multiple of , and therefore . This falls short of the factorial, as it leaves out the pair consisting of 1 and , and we see that , and therefore satisfies the congruence specified by the theorem. □ 
So if we take a prime number, such as 7, we will find that the factorial of the number one less than that prime is one less than a multiple of that prime, such as is the case with 6! + 1 = 721, which is 103 times 7 (see A060371 and A007619).
- Some textbooks state the theorem in reference to prime numbers only, and thus don't bother to prove the relationship doesn't hold for composite .
- Ivan Niven & Herbert S. Zuckerman, An Introduction to the Theory of Numbers. New York: John Wiley & Sons (1980): p. 34, Theorem 2.10. The proof given concerns itself only with prime.
- Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications (1969, reprinted 2007): p. 28, Theorem 13.1.