Wilson's theorem states that a positive integer \( n > 1 \) is a prime if and only if \( (n-1)! \equiv -1 \pmod {n} \). In other words, \( (n-1)! \) is 1 less than a multiple of \(n\). This is useful in evaluating computations of \( (n-1)! \), especially in Olympiad number theory problems. For example, since we know that 101 is a prime, we can conclude immediately that \( 100! = 101 k - 1 \text{ for some integer } k. \)

Explanation of Wilson's Theorem

\(\quad \text{(1)}\) For a positive integer \(n\ (> 1)\), if \((n-1)!\equiv -1\pmod n,\) then \(n\) is a prime.
\(\quad \text{(2)}\) If \(p\) is a prime number, then \((p-1)!\equiv -1\pmod p\) holds.

Notice how \((1)\) provides us with a way to check if a number is prime. But this is really inefficient as factorials grow really fast. So it's hard to compute the modulus for sufficiently large \(n\) even on a computer. Fortunately, we've got better primality tests to save the world! But \((2)\) is helpful in easing out computations and cracking several Olympiad number theory problems.

Proof of Wilson's Theorem

A positive integer \(n\ (>1)\) is a prime if and only if \((n-1)!\equiv -1\pmod n. \ _\square\)

At first glance it seems that proving \((1)\) is a really difficult job, but proving \((2)\) shouldn't be that hard. Surprisingly, the situation is exactly opposite. Proofs of \((1)\) and \((2)\) are included separately below.

\((1):\) Assuming \(n\) a composite number, we show a contradiction. If \(n\) is a composite number then it has at least one divisor \(d\) less than \(n\), that is \(d\le n-1\). But since \((n-1)!\) is the product of all positive integers from \(1\) to \(n-1\), the product must contain \(d\) and thus be divisible by \(d\). So we have \((n-1)!\equiv 0\pmod d\). Also \((n-1)!\equiv 0\not\equiv -1\pmod d\) since \(d\mid n\), contradicting the hypothesis. So \(n\) can't be composite, hence prime. \(_\square\)

\((2):\) Consider the field \(\mathbb{Z}_p\). This is just the set of integers modulo \(p\), i.e. contains all integers from \(0\) to \(p-1\). All the operations are done in modulo \(p\). For example, in this field \(5+(p-2)=3\) since \[5+(p-2)=p+3\equiv 3\pmod p.\] Now consider the polynomial \(f(x)=x^{p-1}-1\), which clearly has \(p-1\) roots by the fundamental theorem of algebra. Also \(x^{p-1}-1\equiv 0\pmod p\) for all \(1\le x\le p-1\) by Fermat's little theorem (See worked example 3 here) since \(p\) is a prime. So in \(\mathbb{Z}_p\), these must be the \(p-1\) roots of \(f\). Hence we can write