Let $n \in \mathbb{Z}$ with $n > 1$. Show that $n$ is prime if and only if $(n − 1)! \equiv −1 \pmod n$.

$\implies$

Based on Wilson's theorem, we know that $(n − 1)! \equiv −1 \pmod n$ if $n$ is an odd prime. Clearly, this also holds when $n = 2$, since $(2-1)! \equiv 1 \equiv -1 \pmod 2$. Therefore, if $n$ is prime, $(n − 1)! \equiv −1 \pmod n$.

$\impliedby$

Suppose $n$ is not prime, and $(n − 1)! \equiv −1 \pmod n$. Observe that $(n − 1) \equiv −1 \pmod n$ and $gcd(n-1,n) = 1$. Therefore,

$$\begin{aligned} \frac{(n − 1)!}{(n-1)} &\equiv \frac{−1}{-1} \pmod n \\ (n − 2)! &\equiv 1 \pmod n \\ \end{aligned}$$

Since $n$ is not prime, there must exist an integer $i$ in $[1, n-2]$ such that $i$ has no multiplicative inverse in $\mathbb{Z_n}$. Let $ij = (n-2)!$ for some integer $j$. We know $j$ exists, since $i$ divides $(n-2)!$. So $(n - 2)! = ij \equiv 1 \pmod n$. But this means $j$ is a multiplicative inverse of $i$ - a contradiction. Therefore, if $(n − 1)! \equiv −1 \pmod n$, $n$ must be prime.

# posted by rot13(Unafba Pune) @ 1:58 PM