Teorema de Wilson

Teoría

El Teorema de Wilson es un resultado fundamental en la teoría de números que establece una condición necesaria y suficiente para la primalidad basándose en aritmética modular con factoriales. Específicamente, dice que un entero $p > 1$ es un número primo si y solo si $(p-1)! \equiv -1 \pmod p$. Mientras que el Pequeño Teorema de Fermat da una condición que todos los primos cumplen (pero que algunos compuestos, llamados números de Carmichael, también cumplen), el Teorema de Wilson te da una prueba definitiva de primalidad. Sin embargo, como la función factorial crece muy rápido, casi no se utiliza como una prueba computacional; su mayor utilidad está en demostraciones teóricas y para resolver problemas de residuos en competencias como el AIME y la USAMO.

La intuición detrás del Teorema de Wilson viene de la estructura algebraica de los enteros módulo $p$. Cuando $p$ es primo, cada entero $a$ distinto de cero en el conjunto ${1, 2, \dots, p-1}$ tiene un único inverso multiplicativo módulo $p$. En el producto $(p-1)!$, puedes emparejar a la mayoría de los elementos con sus respectivos inversos para que el producto de cada pareja sea $1$. Los únicos elementos que no puedes emparejar con un número distinto son los que son sus propios inversos (autoinversos). Si resuelves la congruencia $x^2 \equiv 1 \pmod p$, verás que los únicos autoinversos son $1$ y $p-1$ (que es equivalente a $-1$). Por lo tanto, todo el producto del factorial se reduce al producto de estos autoinversos, lo que te da $-1$.

En cambio, si $n$ es un número compuesto mayor a $4$, el producto $(n-1)!$ contiene suficientes divisores de $n$ para que el producto sea divisible entre $n$. Específicamente, si $n$ es compuesto, lo puedes escribir como $n = ab$ con $1 < a, b < n$. Como $a$ y $b$ aparecen en la secuencia $1, 2, \dots, n-1$, su producto contribuye al factorial, haciendo que $(n-1)! \equiv 0 \pmod n$. Esta clara diferencia hace que el Teorema de Wilson sea una herramienta poderosa para encontrar residuos de factoriales grandes.

Fórmulas Clave

Teorema de Wilson Para un primo $p$: $$(p-1)! \equiv -1 \pmod p$$

Recíproco de Wilson (Prueba de Primalidad) Para un entero $n > 1$: $$n \text{ es primo} \iff (n-1)! \equiv -1 \pmod n$$

Caso Compuesto Para un entero compuesto $n > 4$: $$(n-1)! \equiv 0 \pmod n$$ (Nota: Para el caso compuesto especial $n=4$, $(4-1)! = 6 \equiv 2 \pmod 4$.)

Generalización (Gauss) Sea $P$ el producto de todos los enteros positivos menores a $n$ que son primos relativos con $n$. Entonces: $$P \equiv \begin{cases} -1 \pmod n & \text{si } n = 4, p^k, 2p^k \text{ donde } p \text{ es un primo impar} \ 1 \pmod n & \text{en cualquier otro caso} \end{cases}$$

Demostración

Teorema: Si $p$ es un primo, entonces $(p-1)! \equiv -1 \pmod p$.

Demostración: Considera el conjunto de residuos distintos de cero módulo $p$: $S = {1, 2, \dots, p-1}$. Como $p$ es primo, los enteros módulo $p$ forman un campo (específicamente $\mathbb{Z}_p$). Esto implica que para cada $a \in S$, existe un único inverso $a^{-1} \in S$ tal que: $$a \cdot a^{-1} \equiv 1 \pmod p$$

Puedes emparejar los elementos de $S$ con sus inversos multiplicativos. Sin embargo, hay que identificar qué elementos son sus propios inversos (autoinversos). Un elemento $x$ es su propio inverso si: $$x \cdot x \equiv 1 \pmod p$$ $$x^2 - 1 \equiv 0 \pmod p$$ $$(x-1)(x+1) \equiv 0 \pmod p$$

Como $p$ es primo, aplica el Lema de Euclides: $p$ debe dividir a $(x-1)$ o a $(x+1)$.

1. $x - 1 \equiv 0 \implies x \equiv 1 \pmod p$
2. $x + 1 \equiv 0 \implies x \equiv -1 \equiv p-1 \pmod p$

Así que, en el conjunto $S$, los elementos $1$ y $p-1$ son los únicos que son sus propios inversos. Los $p-3$ elementos restantes los puedes agrupar en $\frac{p-3}{2}$ parejas disjuntas, donde el producto de cada pareja es congruente a $1 \pmod p$.

Ahora, evalúa $(p-1)!$ módulo $p$: $$(p-1)! = 1 \cdot 2 \cdot \dots \cdot (p-1)$$

Reacomoda los términos para agrupar los inversos: $$(p-1)! \equiv 1 \cdot (p-1) \cdot \prod_{\substack{a \in S \ a \neq 1, p-1}} a \pmod p$$

Como los elementos en el término del producto están emparejados con sus inversos: $$\prod_{\substack{a \in S \ a \neq 1, p-1}} a \equiv 1 \cdot 1 \cdot \dots \cdot 1 \equiv 1 \pmod p$$

Sustituyendo esto de nuevo en la expresión del factorial: $$(p-1)! \equiv 1 \cdot (p-1) \cdot 1 \pmod p$$ $$(p-1)! \equiv p-1 \pmod p$$ $$(p-1)! \equiv -1 \pmod p$$

$\square$