Prove: $(n-1)! \equiv -1 \pmod{n}$

Question

I'm trying to self-learn some number theory. Currently, I'm trying to prove the following:

$$(n-1)! \equiv -1 \pmod{n}$$

However, I'm a bit stumped on this one. Honestly, I'm not sure where's a good place to start.

Answer 1

This is false for general $n$. For example, $5!=120\equiv 0\pmod 6$, not $-1$. In fact, $(n-1)!\equiv 0\pmod{n}$ for all composite $n\geq 6$.

Answer 2

This is not true for $n=4$. It is true iff $n$ is prime (Wilson's theorem). The proofs in Wikipedia are not completely elementary (use fields and Lagrange's theorem, Fermat's little theorem of Sylow theorem). Here is an elementary proof I learned in the middle school.

If $n$ is not prime then it is divisible by a prime $p<n$. Then $(n-1)!\equiv 0 (\mod p)$, hence cannot be $\equiv -1 (\mod n)$.

Suppose now that $n$ is prime. Then every number $0<k<n$ is relatively prime with $n$. Therefore there exist integers $u,v$ such that $uk+vp=1$ or $uk\equiv 1 (\mod n)$. Moreover we can replace $u$ by $u\pm pl$ for a suitable $l$ and assume $0<u=u_k<n$.

If $u_k=k$ then $k^2\equiv 1 (\mod n)$, so $(k-1)(k+1)\equiv 0 (\mod n)$. This can happen only if $k=1$ or $n-1$ (recall that $n$ is prime). Thus with every $k\ne 1, n-1$ we associate $1<u_k<n-1$ (clearly $u_k$ satisfies this) such that $ku_k\equiv 1 (\mod n)$. But then

$$(n-1)!=1(n-1)(2u_2)...(ku_k)...\equiv 1(-1)*1 =-1 (\mod n).$$