Multiply all the nonzero residues mod a prime. Mod 5: $1 \cdot 2 \cdot 3 \cdot 4 = 24 \equiv -1$. Mod 7: $6! = 720 \equiv -1$. It is always $-1$, and the reason is a pretty pairing argument with modular inverses.
Wilson's theorem. An integer $p > 1$ is prime exactly when $$(p - 1)! \equiv -1 \pmod{p}.$$
Por qué funciona
Primes. Mod a prime $p$, every $x$ from $1$ to $p - 1$ has an inverse. Which are their own inverses? $x^{2} \equiv 1$ means $p \mid (x - 1)(x + 1)$, so by Euclid's lemma $x \equiv 1$ or $x \equiv -1$. Every other number from $2$ to $p - 2$ pairs off with a different partner, and each pair multiplies to $1$. So $(p - 1)! \equiv 1 \cdot (p - 1) \equiv -1$.
Composites. If $n = ab$ with $1 < a < b < n$, both $a$ and $b$ appear in $(n - 1)!$, so $n \mid (n - 1)!$. If $n = a^{2}$ with $a > 2$, then $a$ and $2a$ both appear, so again $n \mid (n - 1)!$. Either way $(n - 1)! \equiv 0$, not $-1$. The lone exception $n = 4$ gives $3! = 6 \equiv 2$, still not $-1$.
Composites. If $n = ab$ with $1 < a < b < n$, both $a$ and $b$ appear in $(n - 1)!$, so $n \mid (n - 1)!$. If $n = a^{2}$ with $a > 2$, then $a$ and $2a$ both appear, so again $n \mid (n - 1)!$. Either way $(n - 1)! \equiv 0$, not $-1$. The lone exception $n = 4$ gives $3! = 6 \equiv 2$, still not $-1$.
Ejemplo resuelto: Checking the theorem
Find $12! \bmod 13$ without computing $12!$.
- Pair each number with its inverse mod 13: $2 \cdot 7 = 14$, $3 \cdot 9 = 27$, $4 \cdot 10 = 40$, $5 \cdot 8 = 40$, $6 \cdot 11 = 66$ are all $\equiv 1$.
- $12! \equiv 1 \cdot 12 \cdot 1^{5} = 12 \equiv -1 \pmod{13}$.
Respuesta: $12$, that is, $-1$.
Ejemplo resuelto: One factor short
Find $15! \bmod 17$.
- Wilson: $16! \equiv -1 \pmod{17}$. And $16! = 15! \cdot 16$ with $16 \equiv -1$.
- So $15! \cdot (-1) \equiv -1$, which gives $15! \equiv 1 \pmod{17}$.
Respuesta: $1$.
Ejemplo resuelto: Two factors short
Find $20! \bmod 23$.
- $22! = 20! \cdot 21 \cdot 22 \equiv 20! \cdot (-2)(-1) = 2 \cdot 20! \pmod{23}$, and $22! \equiv -1$.
- So $2 \cdot 20! \equiv -1$. The inverse of 2 mod 23 is 12, so $20! \equiv -12 \equiv 11 \pmod{23}$.
Respuesta: $11$.
| $n$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|
| $(n-1)! \bmod n$ | 1 | 2 | 2 | 4 | 0 | 6 | 0 | 0 | 0 | 10 |
Error común
Expecting $(n - 1)! \equiv -1 \pmod{n}$ for every $n$. For $n = 6$: $5! = 120 = 6 \cdot 20 \equiv 0$. The theorem is about primes, and for composites the value is $0$ (or $2$ when $n = 4$). That difference is exactly why Wilson's theorem characterizes primes.
As a primality test Wilson's theorem is perfect and useless: it never errs, but computing $(n - 1)! \bmod n$ takes about $n$ multiplications, far slower than trial division. Its value is the pairing idea, which comes back in quadratic residues.
Idea clave
$p$ is prime exactly when $(p - 1)! \equiv -1 \pmod{p}$: the residues $2, \dots, p - 2$ pair up with their inverses, leaving $1 \cdot (p - 1)$.