For example, if , then . If , then
But if , then
so is composite. Thus Wilson's theorem could be viewed as a primality test, though, from a computational point of view, it is probably one of the world's least efficient primality tests since computing takes so many steps.
has a unique solution . If , then , so , so or , so . We can thus pair off the elements of , each with their inverse. Thus
Multiplying both sides by proves that .
Next we assume that and prove that must be prime. Suppose not, so that is a composite number. Let be a prime divisor of . Then , so . Also, by assumption,
This is a contradiction, because a prime can not divide a number and also divide , since it would then have to divide .
where we have paired up the numbers for which .
sage: for n in range(1,10): ... print n, factorial(n-1) % n, -1 % n 1 0 0 2 1 1 3 2 2 4 2 3 5 4 4 6 0 5 7 6 6 8 0 7 9 0 8
William 2007-06-01