group theory - Prove that $(n-1)! equiv -1 pmod{n}$ iff $n$ is prime [Wilson's Theorem]

How can I show that $(n-1)!$ is congruent to $-1 \pmod{n}$ if and only if $n$ is prime?

Thanks.

Answer

$$n\text{ is prime if }(n-1)! \equiv -1 \pmod n$$

This direction is easy. If $n$ is composite, then there exists $k|n$ and $k\lt n$. So $k|(n-1)!$ and $k \equiv 1 \pmod n$. This means $k$ needs to divide $1$. So $n$ must be prime (or $1$, but we can eliminate this by substitution).

$$(n-1)! \equiv -1\text{ if }n\text{ is prime}$$

Wikipedia contains two proofs of this result known as Wilson's theorem. The first proof only uses basic abstract algebra and so should be understandable with a good knowledge of modular arithmetic. Just in case, I prove below that each element $1, 2, ... n-1$ has a unique inverse $\mod n$.

They use the fact that integers $\mod p$ form a group and hence that each element $x$ not congruent $0$ has a multiplicative inverse (a number $y$ such that $xy \equiv 1 \mod n$.
We show this as follows. Suppose $n \nmid x$, for $n$ prime. From the uniqueness of prime factorisations, $xn$ is the first product of $x$, after $0x$, divisible by $n$ (use prime factorisation theorem). If we look at the series $kn \mod n$, this cycles and must have cycle length $n$. Therefore, each element $x, 2x,... nx$ must be different modulo $n$, including one, $y$, with $xy \equiv 1 \mod n$. Furthermore, due to the cycle length being $n$, each only one of those elements will be an inverse. So every element has a unique inverse (although 1 and -1 are their own inverses).