## Half of Wilson’s Theorem

Let $n$ be a natural number. Prove that if $(n-1)! \equiv -1 \mod n$, then $n$ is prime.

Suppose $n$ is composite; say $n = p_1p_2 \cdots p_k$, where the $p_i$ are pairwise coprime and greater than 1. (Say each $p_i$ is the highest power of some prime dividing $n$.) If $k \geq 2$, each of the $p_i$ is represented in the set $\{1,2,\ldots,n-1\}$. Thus we have $(n-1)! \equiv 0 \mod n$. If on the other hand $n = q^t$ is a prime power, and $t \geq 3$, then $q$ and $q^{t-1}$ are in the set $\{1,2,\ldots,n-1\}$, so that $(n-1)! \equiv 0$. If $n = q^2$ and $q > 2$, then $q,2q \in \{1,2,\ldots,n-1\}$, and $(n-1)! \equiv 0 \mod n$. If $n = 4$, then $(4-1)! = 6 \equiv 2 \mod 4$.

So $n$ must be prime.