converse of Wilson’s theorem

Theorem. Given an integer $n>1$, if $(n-1)!\equiv -1modn$ then $n$ is prime.

To prove the converse of Wilson’s theorem it is enough to show that a composite number can’t satisfy the congruence. A number that does satisfy the congruence, then, would be not composite, and therefore prime.

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 proper divisors. In fact, for composite $n>4$, it is the case that $(n-1)!$ not only has all the same proper divisors of $n$ as a subset of its own proper divisors, but has them with greater multiplicity than $n$ does. For the special case of $n=4$, the congruence $(n-1)!\equiv 2modn$ is satisfied. For all larger composite $n$, the congruence $(n-1)!\equiv 0modn$ is satisfied instead of the congruence stated in the theorem. ∎

The special case of $n=4$ deserves further special attention, as it is an exception which proves the rule. With any other semiprime $n=pq$, with either $p$ or $q$ being a prime greater than 2, the product $(n-1)!$ contains, in addition to $p$ and $q$, both $(p-1)q$ and $p(q-1)$ (which are distinct numbers if $p\ne q$). So if $p$ and $q$ are distinct, then $(n-1)!$ has both prime factors $p$ and $q$ with a multiplicity of at least 2, which is greater than the multiplicity of 1 in the semiprime $pq$. But with 4, the numbers $(p-1)q$ and $p(q-1)$ are both 2, and so 3! includes 2 as a factor with only a multiplicity of 1, which is less than that factor’s multiplicity in 4.

Title	converse of Wilson’s theorem
Canonical name	ConverseOfWilsonsTheorem
Date of creation	2013-03-22 17:58:55
Last modified on	2013-03-22 17:58:55
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	7
Author	PrimeFan (13766)
Entry type	Theorem
Classification	msc 11-00