El Teorema de Wilson

El teorema y su enunciado

El Teorema de Wilson establece: un entero $n > 1$ es primo si y solo si $(n-1)! \equiv -1 \pmod n$.

Esto es notablemente bello: tenemos una caracterización perfecta de los primos mediante congruencias. Nótese que es una doble implicación: $(n-1)! \equiv -1 \pmod n$ ocurre exactamente cuando $n$ es primo, y $(n-1)! \not\equiv -1 \pmod n$ cuando $n$ es compuesto.

El resultado fue enunciado por Ibn al-Haytham (siglo XI) y redescubierto por Edward Waring en 1770, quien lo atribuyó a John Wilson. La primera demostración publicada fue de Lagrange en 1773.

Demostración: la dirección $p$ primo implica $(p-1)! \equiv -1$

Sea $p$ primo. Consideramos los elementos de $\{1, 2, \ldots, p-1\}$. Cada uno tiene un inverso multiplicativo módulo $p$ (pues son coprimos con $p$), y ese inverso también pertenece a $\{1, \ldots, p-1\}$.

Los elementos que son su propio inverso satisfacen $a^2 \equiv 1 \pmod p$, es decir $p \mid (a-1)(a+1)$, lo que da $a \equiv 1$ o $a \equiv -1 \equiv p-1 \pmod p$. Solo $1$ y $p-1$ son sus propios inversos.

Los demás $p - 3$ elementos (para $p \ge 5$) se agrupan en pares $(a, a^{-1})$ con $a \ne a^{-1}$. El producto de cada par es $a \cdot a^{-1} \equiv 1 \pmod p$. Por lo tanto:

$(p-1)! = 1 \cdot \underbrace{2 \cdot 3 \cdots (p-2)}_{\text{pares con producto } 1} \cdot (p-1) \equiv 1 \cdot 1 \cdot (p-1) \equiv p-1 \equiv -1 \pmod p$.

Para $p = 2$: $(2-1)! = 1 \equiv -1 \equiv 1 \pmod 2$. Correcto. Para $p = 3$: $(3-1)! = 2 \equiv -1 \pmod 3$. Correcto.

Demostración: la dirección $(n-1)! \equiv -1$ implica $n$ primo

Probamos el contrapositivo: si $n$ es compuesto, entonces $(n-1)! \not\equiv -1 \pmod n$.

Si $n$ es compuesto, existe $1 < d < n$ con $d \mid n$. Entonces $d$ aparece como factor en $(n-1)! = 1 \cdot 2 \cdots (n-1)$. Pero también $d \mid n$. Si $(n-1)! \equiv -1 \pmod n$, entonces $n \mid (n-1)! + 1$. En particular $d \mid (n-1)! + 1$. Pero $d \mid (n-1)!$, así que $d \mid 1$, lo que es imposible para $d > 1$.

Hay que tener cuidado con el caso $n = p^2$: aquí $d = p$ y $2d = 2p < p^2 = n$, así que tanto $p$ como $2p$ aparecen entre $1, \ldots, n-1$, y $n \mid p \cdot 2p = 2p^2 \mid 2(n-1)!$, haciendo $(n-1)! \equiv 0 \pmod n$ directamente para $n \ge 9$. En cualquier caso, $(n-1)! \not\equiv -1 \pmod n$.

Aplicaciones en olimpiadas

El Teorema de Wilson tiene aplicaciones directas en congruencias con factoriales módulo un primo.

Ejemplo 1: calcular $(p-2)! \pmod p$ para $p$ primo. Sabemos $(p-1)! = (p-1) \cdot (p-2)! \equiv -1 \pmod p$. Como $p - 1 \equiv -1 \pmod p$, tenemos $(-1)(p-2)! \equiv -1 \pmod p$, y cancelando $-1$: $(p-2)! \equiv 1 \pmod p$.

Ejemplo 2: calcular $(p-3)! \pmod p$ para $p$ primo impar $\ge 5$. Tenemos $(p-1)! \equiv -1$, $(p-1)(p-2)(p-3)! \equiv -1$. Como $p-1 \equiv -1$ y $p-2 \equiv -2$, esto da $(-1)(-2)(p-3)! = 2(p-3)! \equiv -1 \pmod p$. Entonces $(p-3)! \equiv -1 \cdot 2^{-1} \pmod p$. El inverso de $2$ módulo $p$ es $(p+1)/2$ para $p$ impar (pues $2 \cdot (p+1)/2 = p+1 \equiv 1$). Así $(p-3)! \equiv -(p+1)/2 \pmod p$.

Ejemplo 3: si $p$ es primo con $p \equiv 1 \pmod 4$, demostrar que $\left(\frac{p-1}{2}\right)!^2 \equiv -1 \pmod p$. Esto se sigue de Wilson agrupando los factores $(p-1)! = \prod_{k=1}^{(p-1)/2} k \cdot \prod_{k=(p+1)/2}^{p-1} k$. El segundo producto es $\prod_{k=1}^{(p-1)/2}(p-k) \equiv \prod_{k=1}^{(p-1)/2}(-k) = (-1)^{(p-1)/2}\left(\frac{p-1}{2}\right)!$. Como $p \equiv 1 \pmod 4$, $(p-1)/2$ es par y $(-1)^{(p-1)/2} = 1$. Entonces $(p-1)! \equiv \left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv -1 \pmod p$.

Wilson como criterio de primalidad y sus límites prácticos

Teóricamente, el Teorema de Wilson ofrece un criterio perfecto para determinar si $n$ es primo: basta calcular $(n-1)! \pmod n$ y verificar si es $\ equiv -1$. Pero en la práctica, calcular $(n-1)!$ para $n$ grande es computacionalmente inviable (el factorial crece más rápido que cualquier potencia).

En olimpiadas, Wilson se usa principalmente en módulos pequeños (primos $p \le 20$ o así) o en argumentos teóricos que involucran factoriales módulo primos arbitrarios.

Una identidad útil relacionada: para $p$ primo y $0 \le k \le p-1$, $\binom{p-1}{k} \equiv (-1)^k \pmod p$. Esto se demuestra escribiendo $\binom{p-1}{k} = \frac{(p-1)(p-2)\cdots(p-k)}{k!}$ y notando que $p - j \equiv -j \pmod p$ para $j = 1, \ldots, k$.