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