This site is supported by donations to The OEIS Foundation.
Wilson's theorem
Wilson's theorem concerns a relationship between factorials and prime numbers. Gottfried W. Leibniz knew of it before John Wilson and Edward Waring came along.
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.[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. □ [2]
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).
There are of course many ways to prove the theorem. Decades ago, Bolker gave a proof using the algebra of polynomials and invoking Fermat's little theorem.[3]
See also
References
- ↑ 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.