proof of Wilson’s theorem using the Wilson quotient

Theorem. An integer $n>1$ is prime only if the Wilson quotient ${\displaystyle \frac{(n-1)!+1}{n}}$ is an integer.

Proof.

If $n$ is composite, then its greatest prime factor is at most ${\displaystyle \frac{n}{2}}$, and as long as $n>2$ (and the smallest positive composite number is 4). Therefore, $(n-1)!$ being the product of the numbers from 1 to $n-1$ includes among its divisors the greatest prime factor of $n$, and indeed all its divisors. Since two consecutive integers are always coprime, it is the case that $\gcd ((n-1)!,(n-1)!+1)=1$. Therefore $n$ will divide $(n-1)!$ evenly but not $(n-1)!+1$. So the Wilson quotient will be a rational number but not an integer.

If we only meant to prove the converse of Wilson’s theorem we’d be done at this point. But we set out to prove that not only is the stated relation false for composite numbers, but that it is true for primes. Proving the former is quite easy. Proving the latter is harder, and in fact neither Edward Waring nor John Wilson left a proof. (Koshy, 2007)

If $n$ is prime, then obviously its greatest prime factor is itself, and $(n-1)!$ will have only 1 as a divisor in common with $n$. But how do we prove that the next number after $(n-1)!$ is a multiple of $n$ without having to factorize several values of $(n-1)!$ and hoping the proof makes itself apparent thus? Modular multiplication comes to the rescue. Since $n$ is prime, we can multiply any number from 2 to $n-2$ by another of the same range and the product will be congruent to 1 modulo $n$.

For example, $n=7$. We verify that $2\times 4=8\equiv 1mod7$ and $3\times 5=15\equiv 1mod7$. Since $1\times 1=1$, multiplying the range 2 to 5 will give a number that satisfies the same congruence.

So in general multiplying the range 2 to $n-2$ gives a number that is congruent to 1 modulo $n$ if $n$ is prime. (With $n$ composite, modular multiplication causes a zeroing out of the range’s overall product). $n-1$ is different, satisfying $(n-1)\equiv (n-1)modn\equiv -1modn$. And since $1\times -1=-1$, modular multiplication of the range 2 to $n-1$ gives $-1$. Thus $(n-1)!\equiv -1modn$ when $n$ is prime, so $(n-1)!+1\equiv 0modn$. Therefore, $(n-1)!+1$, which is greater than $n$, is also divisible by it, and thus dividing it by $n$ yields an integer. ∎

Title	proof of Wilson’s theorem using the Wilson quotient
Canonical name	ProofOfWilsonsTheoremUsingTheWilsonQuotient
Date of creation	2013-03-22 17:58:57
Last modified on	2013-03-22 17:58:57
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	5
Author	PrimeFan (13766)
Entry type	Proof
Classification	msc 11A51
Classification	msc 11A41