Theorem. Given an integer $n > 1$ , if $(n - 1)! \equiv -1 \mod n$ 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 $\displaystyle \frac{n}{2} < (n - 1)$ 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 2 \mod n$ is satisfied. For all larger composite $n$ , the congruence $(n - 1)! \equiv 0 \mod n$ 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 \neq 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.

Bibliography

1

Thomas Kochy, ''Elementary Number Theory with Applications'', 2nd Edition. London: Elsevier (2007): 324 - 325